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的情况
下面先提供三个工具函数：
//计算数组内的值
functioncalculate(arg){
returneval(arg.join('+'));
}
//输出数组的值 functionprint(arg){ for(vari=0;i<arg.length;i++){ console.log(arg[i]); } }
//检查是否是正反的走法 functionhasRepeat(src,dist){ if(dist.length!=2)returnfalse; for(vari=0,len=src.length;i<len;i++){ if(dist.length==src[i].length){ if(dist[0]==src[i][1]){ returntrue; } } } returnfalse; }