萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 實現約瑟夫問題:自定義數組指針操作(reset/current/next/prev/search/end/unset)

問題描述

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

現代簡潔實現(數學解法 / 模擬優化)

數學遞推公式 O(m log n) / O(m)

// 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

ES6 模擬版(可視化過程)

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++、理解迭代器模式。

copyright © 萬盛學電腦網 all rights reserved