JavaScript实现的一个计算数字步数的算法分享_Javascript教程-查字典教程网
JavaScript实现的一个计算数字步数的算法分享
JavaScript实现的一个计算数字步数的算法分享
发布时间:2016-12-30 来源:查字典编辑
摘要:这两天看了下某位大神的github,知道他对算法比较感兴趣,看了其中的一个计算数字的步数算法,感觉这个有点意思,所以就自己实现了一个。算法描...

这两天看了下某位大神的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细节方面其实都运用了算法,以后有空还会贴更多关于算法相关的文章,欢迎大家多提些宝贵意见.

相关阅读
推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
  • 大家都在看
  • 小编推荐
  • 猜你喜欢
  • 最新Javascript教程学习
    热门Javascript教程学习
    编程开发子分类