前陣子翻某位前輩的 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 細節背後都是演算法在支撐。歡迎大家多提寶貴意見。