n 個猴子圍圈,從 1 開始報數,報到 m 的猴子出列,剩下的繼續報數,求最後剩下的猴子編號(大王)。
Array.prototype.pointer = 0; // 掛載指針屬性
function reset(arr) { arr.pointer = 0; }
function current(arr) { return arr[arr.pointer]; }
function end(arr) { arr.pointer = arr.length - 1; return current(arr); }
function next(arr) {
arr.pointer++;
if (arr.pointer >= arr.length) { arr.pointer--; return false; }
return true;
}
function prev(arr) {
arr.pointer--;
if (arr.pointer < 0) { arr.pointer++; return false; }
return arr[arr.pointer];
}
function search(val, arr) {
for (var i in arr) if (arr[i] === val) return i;
return false;
}
function unset(index, arr) {
if (index >= arr.length) return false;
arr.splice(index, 1);
return true;
}
function getKingMonkey(n, m) {
var a = [];
for (var i = 1; i <= n; i++) a[i] = i;
a[0] = 0; unset(0, a); reset(a); // 去掉佔位 0
while (a.length > 1) {
for (var counter = 1; counter <= m; counter++) {
if (next(a)) {
if (counter === m) {
unset(search(prev(a), a), a); // 刪除前一個(當前報到 m)
}
} else {
reset(a); // 循環到頭重置指針
if (counter === m) {
unset(search(end(a), a), a);
reset(a);
}
}
}
}
return current(a);
}
console.log('猴子大王編號:', getKingMonkey(100, 17)); // 46
// f(1)=0; f(i) = (f(i-1)+m) % i
function josephusMath(n, m) {
var pos = 0;
for (var i = 2; i <= n; i++) pos = (pos + m) % i;
return pos + 1; // 1-based 編號
}
console.log(josephusMath(100, 17)); // 46
function josephusSimulate(n, m) {
let monkeys = Array.from({length: n}, (_, i) => i + 1);
let idx = 0;
while (monkeys.length > 1) {
idx = (idx + m - 1) % monkeys.length;
console.log('出局:', monkeys.splice(idx, 1)[0]);
}
return monkeys[0];
}
| 方法 | 時間 | 空間 | 適用 |
|---|---|---|---|
| 指針模擬 (原文) | O(n×m) | O(n) | 教學演示指針操作 |
| 數學遞推 | O(n) | O(1) | 單純求結果、大數據 |
| 隊列/數組模擬 | O(n×m) | O(n) | 需記錄出局順序 |
原文通過手寫指針操作展示了底層數據結構思想,但在 JS 中**直接操作數組索引或使用數學公式**效率高得多。理解指針概念有助於學習 C/C++、理解迭代器模式。