使用 JavaScript 高效计算约瑟夫斯排列
javascriptweb developmentfront end technologyobject oriented programming
该问题的名称来源于古代历史学家约瑟夫斯一生中最重要的事件 − 根据他的故事，他和他的 40 名士兵在一次围攻中被罗马人困在一个山洞里。
他们拒绝向敌人投降，而是选择集体自杀，但结局却有所不同 −他们围成一圈，每三个人杀一个人，直到剩下最后一个人(而且应该自杀来结束这一行为)。
约瑟夫和另一个人是最后两个人，由于我们现在知道了故事的每一个细节，你可能已经猜到了他们并没有完全按照原来的想法去做。
我们需要编写一个返回约瑟夫排列的 JavaScript 函数。
将要排列的初始数组/项目列表作为参数，就好像它们在一个圆圈里，每 k 个位置计数一次，直到没有剩余的元素。
例如，当 n=7 和 k=3 时，josephus(7,3) 应该这样做。
[1,2,3,4,5,6,7] − 初始序列 [1,2,4,5,6,7] => 3 被算出并计入结果 [3] [1,2,4,5,7] => 6 被算出并计入结果 [3,6] [1,4,5,7] => 2 被算出并计入结果 [3,6,2] [1,4,5] => 7 被算出并计入结果 [3,6,2,7] [1,4] => 5 被算出并计入结果 [3,6,2,7,5] [4] => 1 被算出并计入结果 [3,6,2,7,5,1] [] => 4 被算出并计入结果 [3,6,2,7,5,1,4]
因此，我们的最终结果是 −
josephus([1,2,3,4,5,6,7],3)==[3,6,2,7,5,1,4];
示例
其代码为 −
const arr = [1, 2, 3, 4, 5, 6, 7];
const num = 3;
const helper = (n, k, i, map) => {
if (map.hasOwnProperty([n, k, i]))
return map[[n, k, i]];
if (i === 1)
return map[[n, k, i]] = (k − 1) % n;
return map[[n, k, i]] =
(k + helper(n − 1, k, i − 1, map)) % n;
}
const josephus = (arr, k) => {
let n = arr.length;
let result = new Array(n);
let map = {};
for (let i=1; i<=n; i++)
result[i − 1] = arr[ helper(n, k, i, map) ];
return result;
};
console.log(josephus(arr, num));
输出
控制台中的输出将是 −
[ 3, 6, 2, 7, 5, 1, 4 ]
