DIV CSS 佈局教程網

用 JavaScript 枚舉數字的所有「走法」組合
編輯:關於JavaScript     

前陣子翻某位前輩的 GitHub,發現他對演算法頗有研究,其中一個「計算數字步數」的題目引起我的興趣,於是動手自己實作了一版。

題目與解題思路

給定一個整數,求出所有能加總成該數的組合(每項為正整數,且視同有序的分割)。以 4 為例:

   [ 1, 3 ]
   [ 4 ]
   [ 1, 1, 2 ]
   [ 2, 2 ]
   [ 1, 1, 1, 1 ]

觀察這些組合,可以歸納出幾個規則:

1. 先列出所有項皆為 1 的組合。
2. 依序從左到右,把連續的 1 逐步合併。
3. 對上一步產生的每個集合遞迴處理:找出其中 1 的位置,計算左起兩項之和,再遞迴下去。
4. 排除會造成重複(正反同一種)的情況。

三個工具函式

// 計算陣列內的值
function calculate(arg){
  return eval(arg.join('+'));
}

// 輸出陣列的值
function print(arg){
  for(var i = 0; i < arg.length; i++){
    console.log(arg[i]);
  }
}

// 檢查是否是正反的走法
function hasRepeat(src, dist){
  if (dist.length != 2) return false;
  for(var i = 0, len = src.length; i < len ; i++){
    if(dist.length == src[i].length){
      if(dist[0] == src[i][1]){
        return true;
      }
    }
  }
  return false;
}

主流程

function countSteps(n){
  var counts = 0,i,j = 0;
  var result = [];
  var newresult = [];
  var source = [];
  var temparg = [];
  // 生成項全為 1 的陣列
  for(i = 1; i <= n ; i++){
    source.push(1);
  }
  if(n > 2){
    for(j = 1; j < n - 1; j++){
      temparg.length = 0;
      if(j < n - 1){
        // 生成從左到右項為 1 遞增的陣列
        // 1.. 11.. 111..
        Array.prototype.push.apply(temparg, source.slice(0, j));
        temparg.push(calculate(source.slice(j,n)));
        result.push(temparg.slice(0));
        // 遞歸陣列裡的內容,直到項裡沒有 1 為止
        combine(temparg.slice(0));
      }
    }
  }
  // 組合包含 1 的陣列項
  // 111->21->3
  function combine(arg){
    var linearg = [];
    for(var i = 0; i < arg.length; i++){
      if(arg[i] == 1){
        if(i ==0 || i == 1){
          linearg.push(calculate(arg.slice(0,2)));
          Array.prototype.push.apply(linearg, arg.slice(2, arg.length));
          if(!hasRepeat(result, linearg)){
            result.push(linearg);
            combine(linearg.slice(0));
          }
          return;
        }
      }
    }
  }
  //為 2 的時候比 1 要多一項
  if(n == 2){
    result.push([2]);
  }
  // 添加全為 1 的情況
  result.push(source);
  // 輸出所有步
  print(result);
  console.log('總共有:' + result.length + '種走法');
}

// 運行
countSteps(4);

// 輸出下面內容
/*
   [ 1, 3 ]
   [ 4 ]
   [ 1, 1, 2 ]
   [ 2, 2 ]
   [ 1, 1, 1, 1 ]
   總共有:5種走
*/

這裡用 eval(arg.join('+')) 求和以簡化程式碼,實務上改成 reduce 累加會更安全可讀;而 hasRepeat 的去重邏輯只涵蓋兩項的情形,若輸入規模變大,建議改用「以字串鍵值記錄已產生的組合」這類通用去重策略。

小結

這類枚舉思路可以延伸到某些遊戲機制上——例如兩個物件距離固定時,把所有可能的路徑組合列出來做業務處理。前端工程師日常較少有機會碰演算法,但它其實無所不在,很多 UI 細節背後都是演算法在支撐。歡迎大家多提寶貴意見。

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