這兩天看了下某位大神的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 < 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種走
*/
總結
這個算法其實可以應用到某類游戲中去,當兩個物體之前的距離一定的話,對所有的可能進行業務處理,當然也可以應用到別的地方,雖然大部分前端工程師對算法的實踐比較少,不過它還是有存在的價值的,很多UI細節方面其實都運用了算法,以后有空還會貼更多關于算法相關的文章,歡迎大家多提些寶貴意見.
