DIV CSS 佈局教程網

用數組指針操作求解約瑟夫問題
編輯:JavaScript綜合知識     

約瑟夫問題是經典的循環淘汰模型: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 掉一個元素,數組變短後指針自然對應新的排列。

這種寫法的教學價值大於工程價值——它逼迫你動手實現底層操作,從而真正理解指針與下標的關係。實際項目中,用雙向鏈表實現會更直觀,時間複雜度也更優。

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