約瑟夫問題(Josephus problem)是經典的循環淘汰題型:n 個人圍成一圈,從某人開始數到 m 就出圈,剩下的人繼續數,最後留下的是誰?本文刻意不用遞迴公式,而是走「陣列 + 指標」的路子,順便把 JavaScript 缺少的鏈式指標操作自己補上。
JavaScript 陣列沒有內建的 reset()、current()、next()、prev() 這些指標操作,所以我們先掛一個 pointer 屬性到 Array.prototype,再逐一實作:
Array.prototype.pointer = 0; // 模擬陣列內部指標
// 將指標歸位到第一個元素
var reset = function (arrayObj) {
if (!(arrayObj instanceof Array)) {
alert("Reset() 函數參數類型錯誤!請檢查輸入!");
return;
}
arrayObj.pointer = 0;
};
// 回傳指標目前指向的元素
var current = function (arrayObj) {
if (!(arrayObj instanceof Array)) {
alert("Current() 函數參數類型錯誤!請檢查輸入!");
return;
}
return arrayObj[arrayObj.pointer];
};
// 將指標移到最後一個元素並回傳該元素
var end = function (arrayObj) {
if (!(arrayObj instanceof Array)) {
alert("End() 函數參數類型錯誤!請檢查輸入!");
return;
}
arrayObj.pointer = arrayObj.length - 1;
return arrayObj[arrayObj.pointer];
};
// 指標下移一位;已在末尾則回退並回傳 false
var next = function (arrayObj) {
if (!(arrayObj instanceof Array)) {
alert("Next() 函數參數類型錯誤!請檢查輸入!");
return;
}
arrayObj.pointer++;
if (typeof arrayObj[arrayObj.pointer] == 'undefined') {
arrayObj.pointer--;
return false;
}
return true;
};
// 指標上移一位;已在開頭則回退並回傳 false
var prev = function (arrayObj) {
if (!(arrayObj instanceof Array)) {
alert("Prev() 函數參數類型錯誤!請檢查輸入!");
return;
}
arrayObj.pointer--;
if (typeof arrayObj[arrayObj.pointer] == 'undefined') {
arrayObj.pointer++;
return false;
}
return arrayObj[arrayObj.pointer];
};
// 刪除指定索引的元素
var unset = function (index, arrayObj) {
if (!(arrayObj instanceof Array)) {
alert("Unset() 函數參數類型錯誤!請檢查輸入!");
return;
}
if (typeof arrayObj[index] == 'undefined') {
alert("Unset() 函數參數 index 錯誤!不存在此元素!");
return false;
}
arrayObj.splice(index, 1);
return true;
};
// 依值回傳對應的鍵名(索引)
var search = function (value, arrayObj) {
if (!(arrayObj instanceof Array)) {
alert("Search() 函數參數類型錯誤!請檢查輸入!");
return;
}
for (var index in arrayObj) {
if (arrayObj[index] == value) {
return index;
}
}
return false;
};
function getKingMonkey(n, m) {
var a = new Array();
for (var i = 1; i <= n; i++) {
a[i] = i;
}
a[0] = 0;
unset(0, a); // 去掉佔位用的 0
reset(a);
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);
}
alert("猴子大王的編號為:" + getKingMonkey(100, 17));
這版實作的價值在「把鏈式指標操作抽象出來」——next 走到尾端會自動回傳 false,主程式再據此把指標繞回頭, circular 的語意就很清楚了。
不過直接把 pointer 掛在 Array.prototype 上是危險示範:它會污染所有陣列,也容易被 for...in 掃到。實務上請改用閉包變數或 WeakMap 保存指標狀態。另外本版的 search 是線性搜尋,每次淘汰都要掃一輪,整體複雜度約 O(n·m);若只是要答案,用遞迴式 J(n,m) = (J(n-1,m)+m) % n 可以一步算出,但那就失去了練習指標操作的意思了。