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

复制代码 代码如下:

    [ 1, 3 ]
        [ 4 ]
    [ 1, 1, 2 ]
        [ 2, 2 ]
    [ 1, 1, 1, 1 ]

复制代码 代码如下:

// 计算数组内的值
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种走
*/