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

(0)

相关推荐

  • JavaScript对数字的判断与处理实例分析

    本文实例讲述了JavaScript对数字的判断与处理技巧.分享给大家供大家参考.具体分析如下: Javascript多态的属性是非常爽的,一个var就不用记这么多奇怪的变量,然而,有时候你会困惑,为何,我明明是对两个数进行相加处理,可是结果却被当作字符串加起来呢?这就是Javascript的var不好的地方,它不像php,用一个.来指明这是字符串的连接.这是你需要parseFloat来明确指明这个var是数.需要用isNaN来判断这是不是数.isNaN(一个被判断的var)的时候,结果为真那么它

  • javascript正则匹配汉字、数字、字母、下划线

    javascript正则检测只含有汉字.数字.字母.下划线不能以下划线开头和结尾 遇到一个用户名检测的的问题,查了一下,总结例子如下: 复制代码 代码如下: var reg = /^(?!_)(?!.*?_$)[a-zA-Z0-9_\u4e00-\u9fa5]+$/;if (!reg.test(实际取值的字符串)) {    alert('请输入5-24位字符:支持中文.英文.数字."_",推荐使用中文');}

  • JavaScript实现找出数组中最长的连续数字序列

    原始题目: 给定一个无序的整数序列, 找最长的连续数字序列. 例如: 给定[100, 4, 200, 1, 3, 2], 最长的连续数字序列是[1, 2, 3, 4]. 小菜给出的解法: function maxSequence(array,step){ var _array = array.slice(), //clone array _step = 1, _arrayTemp = [], i = 0; var parseLogic = { //result container parseRe

  • javascript将数字转换整数金额大写的方法

    本文实例讲述了javascript将数字转换整数金额大写的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: function digit_uppercase(n) { var digit = [ '零', '壹', '贰', '叁', '肆', '伍', '陆', '柒', '捌', '玖' ]; var unit = [ ['元', '万', '亿'], ['', '拾', '佰', '仟'] ]; var s = ''; for (var i = 0; i < unit[

  • javascript学习笔记--数字格式类型

    可能有人说这是什么个格式?其实还不止呢.1          //11.2       //1.21.2e3    //12001.2e+3  //12001.2e-3   //0.0012.12e+2  //12-.12e-2 //-0.0012 当然这些只是十进制.我们来说说 八进制 和 十六进制.0x00, 0x11, 0xff 这种格式是十六进制,他们的十进制值分别是 0, 17, 255. 01, 07, 010, 012 这个是 八进制.(这里的 0 是数字 0,不是字母o)可能有朋

  • javascript数字时钟示例分享

    代码很简单,直接上代码了,大家可以复制下面的代码保存成HTML文件运行看效果 复制代码 代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml">

  • javascript获取四位数字或者字母的随机数

    本章节通过代码实例介绍一下如何实现简单的四位随机数功能. 比较简单的一种实现方式就是从数字和字母中随机抽取四个不重复的字符. 代码实例如下: function only(ele,arr){ if(arr.length==0){ return true; } for(var j=0;j<arr.length;j++){ if(ele==arr[j]){ return false; }else{ return true; } } } var arr=[0,1,2,3,4,5,6,"a"

  • JavaScript数字和字符串转换示例

    1. 数字转换为字符串 a. 要把一个数字转换为字符串,只要给它添加一个空的字符串即可: 复制代码 代码如下: var n = 100; var n_as_string = n + ""; b. 要让数字更加显式地转换为字符串,可以使用String()函数: 复制代码 代码如下: var string_value = String(number); c. 使用toString()方法: 复制代码 代码如下: string_value = number.toString(); Numbe

  • JavaScript实现的一个计算数字步数的算法分享

    这两天看了下某位大神的github,知道他对算法比较感兴趣,看了其中的一个计算数字的步数算法,感觉这个有点意思,所以就自己实现了一个. 算法描述与实现原理 给出一个整型数字,统计出有多少种走法可以到达目标,比如一个数字4,可以有下面几种走法 复制代码 代码如下: [ 1, 3 ]         [ 4 ]     [ 1, 1, 2 ]         [ 2, 2 ]     [ 1, 1, 1, 1 ] 其实通过上面的组合可以得出下面的结论. 1.先列出所有项是1的组合 2.依次从左到右项

  • 又一个PHP实现的冒泡排序算法分享

    经典的冒泡排序法一直是许多程序沿用的其中一种排序法,话说冒泡排序法在效率上比PHP系统函数sort更高效.本章不讨论性能,所以就不拿它来跟系统性能做对比了. 冒泡排序大概的意思是依次比较相邻的两个数,然后根据大小做出排序,直至最后两位数.由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序.但其实在实际过程中也可以根据自己需要反过来用,大树往前放,小数往后放. <?php /** * PHP中的冒泡排序法使用 */ // 预先声明一个数组 $arr = array (1

  • Python使用当前时间、随机数产生一个唯一数字的方法

    本文实例讲述了Python使用当前时间.随机数产生一个唯一数字的方法.分享给大家供大家参考,具体如下: Python生成当前时间很简单,比Java的代码简短多了,Java产生时间可参考<Java获取当前系统事件System.currentTimeMillis()方法> 具体代码如下: #-*-coding:utf-8-*- import datetime now = datetime.datetime.now().strftime("%Y-%m-%d %H:%M:%S")

  • 超出JavaScript安全整数限制的数字计算BigInt详解

    JavaScript中的基本数据类Number是双精度浮点数,它可以表示的最大安全范围是正负9007199254740991,也就是2的53次方减一,在浏览器控制台分别输入Number.MAX_SAFE_INTEGER和Number.MIN_SAFE_INTEGER可查看对应的最大/小值 const max = Number.MAX_SAFE_INTEGER; // → 9_007_199_254_740_991 // 注意:为了便于阅读,我使用下划线作为分隔符将这些数字分组为千位数.数字文字分

  • JavaScript 网页中实现一个计算当年还剩多少时间的倒数计时程序

    看到网上这个程序 发现了处错误这里改正了一下: function counter() { var date = new Date(); var year = date.getFullYear(); var date2 = new Date(year, 11, 30, 23, 59, 59); /*转换成秒*/ var time = (date2 - date) / 1000; var day = Math.floor(time / (24 * 60 * 60)) var hour = Math.

  • javascript实现获取一个日期段内每天不同的价格(计算入住总价格)

    代码例子 最近在做酒店的小程序项目开发,遇到一个这样的问题. 酒店的房间价格是浮动的,每天每时或某个特殊的日期价格等都是浮动的不一样.如果用户选择了未来5天的住房的话,而这5天刚好价格还都不一样还有特殊日的价格,如何计算出一个5天的总价格呢? 下面的例子是根据入住的日期,和离店的日期来列出这一个日期段内的所有日期: 这个功能你会有几个地方用到,所以要封装下:单独建一个js文件 function Thedatefor(times,objroom){ // 日期段 objroom房间价格表,有星期和

  • JavaScript实现的可变动态数字键盘控件方式实例代码

    整理文档,搜刮出一个JavaScript实现的可变动态数字键盘控件方式实例代码,稍微整理精简一下做下分享. @sunRainAmazing JavaScript编写和实现的可变动态键盘密码输入控件,可以动态的生产数字键盘并显示,并且可以实现每次点击后密码键盘重新加载,可以手动刷新功能. 第一种方式,点击查看: <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8&qu

  • JavaScript数组的定义及数字操作技巧

    一.数组的介绍 数组中的元素类型可以是数字型.字符串型.布尔型等,甚至也可以是一个数组. 二.定义数组 1.通过数组的构造函数来定义数组: var arr=new Array(); var arr=new Array(size); var arr=new Array(element1,element2,...); 2.直接定义数组: var arr=["字符串",true,13]; ps: 和Object一样,此写法不会调用Array()构造函数. 三.数组元素 1.存取数组元素:通过

  • js实现一个猜数字游戏

    看你需要猜几次才能猜到那个正确的数字! 效果图: 代码如下: <!DOCTYPE html> <html> <head> <meta http-equiv="content-type" content="text/html; charset=utf-8" /> <title>猜数字游戏</title> <script type="text/javascript" cha

  • JavaScript仿支付宝6位数字密码输入框

    前几天,项目有个功能和某宝购物支付密码的输入框有点类似,就自己写了这篇博文,权当总结笔记吧. 啰嗦半天了,直接上代码: 结构层: <div> <div>请在下方输入6位数字</div> <div class="ipt-box-nick"> <input type="tel" maxlength="6" class="ipt-real-nick"/> <div c

随机推荐