JavaScript實作的一個計算數字步數的演算法分享_javascript技巧

這兩天看了下某位大神的github,知道他對算法比較感興趣,看了其中的一個計算數字的步數算法,感覺這個有點意思,所以就自己實現了一個。

演算法描述與實作原理

給出一個整數數字,統計出有多少種走法可以到達目標,比如一個數字4,可以有下面幾種走法

複製程式碼 程式碼如下:

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

其實透過上面的組合可以得出下面的結論。

1.先列出所有項是1的組合
2.依序由左至右項為1的組合
3.遞歸上面的集合,找出項裡1的索引,然後計算左起2項的值,結果遞歸此操作
4.排除1和2的情況

下面先提供三個工具函數：

複製程式碼 程式碼如下:

// 計算數組內的值
function calculate(arg){
    return eval(arg.join(' '));
}

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

// 檢查是否為正反的走法
function hasRepeat(src, dist){
    if (dist.length != 2) return false;
    for(var i = 0, len = src.length; 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         source.push(1);
    }
    if(n > 2){
        for(j = 1; j             temparg.length = 0;
            if(j                 // 產生由左至右項為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             if(arg[i] == 1){
                if(i ==0 || i == 1){
                    linearg.push(calculate(arg.slice(0,2)));
                    中.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種走
*/

總結

這個演算法其實可以應用在某類遊戲中去,當兩個物體之前的距離一定的話,對所有的可能進行業務處理,當然也可以應用到別的地方,雖然大部分前端工程師對算法的實踐比較少,不過它還是有存在的價值的,很多UI細節方面其實都運用了算法,以後有空還會貼更多關於算法相關的文章,歡迎大家多提些寶貴意見.