DIV CSS 佈局教程網

約瑟夫問題實作:用自製指標函式操作 JavaScript 陣列
編輯:關於JavaScript     

約瑟夫問題(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;
};

主程式: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);   // 數到 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 可以一步算出,但那就失去了練習指標操作的意思了。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved