約瑟夫問題是經典的循環淘汰模型:n 個人圍成一圈,從某個位置開始數到 m 的人出列,剩下的人繼續,最終求最後留下的位置。本文換一個角度,用「數組內部指針」的方式來模擬這個過程。
JavaScript 沒有內置 reset、current、next、prev、search 這類指針函數,所以得先自己造。好處是這個抽象層一旦寫好,後面的主邏輯會非常清爽。
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;
};
// n 隻猴子,數到 m 的出列
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);
}
} else {
// 已到末尾,回到頭部重新開始數
reset(a);
if (counter == m) {
unset(search(end(a), a), a);
reset(a);
}
}
}
}
return current(a);
}
alert("猴子大王的編號為:" + getKingMonkey(100, 17));
關鍵在於 next() 到達末尾時返回 false,此時把指針重置到頭部繼續循環,這樣就用一維數組模擬出了環形結構。每淘汰一人就 splice 掉一個元素,數組變短後指針自然對應新的排列。
這種寫法的教學價值大於工程價值——它逼迫你動手實現底層操作,從而真正理解指針與下標的關係。實際項目中,用雙向鏈表實現會更直觀,時間複雜度也更優。