这两天看了下某位大神的github,知道他对算法比较感兴趣,看了其中的一个计算数字的步数算法,感觉这个有点意思,所以就自己实现了一个。
算法描述与实现原理
给出一个整型数字,统计出有多少种走法可以到达目标,比如一个数字4,可以有下面几种走法
代码如下:
其实通过上面的组合可以得出下面的结论。
1.先列出所有项是1的组合 2.依次从左到右项为1的组合 3.递归上面的集合,找出项里1的索引,然后计算左起2项的值,结果递归此操作 4.排除1和2的情况
下面先提供三个工具函数：
代码如下:
// 输出数组的值 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; }
下面贴出算法的实现：
代码如下:
生成项全为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);
总结
这个算法其实可以应用到某类游戏中去,当两个物体之前的距离一定的话,对所有的可能进行业务处理,当然也可以应用到别的地方,虽然大部分前端工程师对算法的实践比较少,不过它还是有存在的价值的,很多UI细节方面其实都运用了算法,以后有空还会贴更多关于算法相关的文章,欢迎大家多提些宝贵意见.
