JavaScript implementation of an algorithm to calculate the number of steps Shared

These two days, I saw some github of a great god, and I knew that he was interested in algorithms. I saw one of the algorithms for calculating the number of steps, and found it interesting, so I implemented one by myself.

Algorithm description and implementation principle

Given an integer number, count the number of possible ways to get to the target, such as a number 4

    [ 1, 3 ]

        [ 4 ]

    [ 1, 1, 2 ]

        [ 2, 2 ]

    [ 1, 1, 1, 1 ]

In fact, the following conclusion can be drawn from the above combination.

1. List all the combinations of 1 first
2. The combination of left to right terms is 1
3. Recurse the above set, find the index of 1 in the item, then calculate the value of 2 items from the left, the result recurses the operation
Rule out 1 and 2

Here are three utility functions:

//Evaluates 
 in the array
function calculate(arg){

    return eval(arg.join('+'));

}
//The value of the output array is 

function print(arg){

    for(var i = 0; i < arg.length; i++){

        console.log(arg[i]);

    }

}
//Check for positive and negative moves 

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;

}

The implementation of the algorithm is posted below:

function countSteps(n){

    var counts = 0,i,j = 0;

    var result = [];

    var newresult = [];

    var source = [];

    var temparg = [];

    //Generate an array of items all 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){

                //Generates an array 
 that increments from left to right by 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));

                //Recurse the contents of the array until there is no 1 in the item 

                combine(temparg.slice(0));

            }

        }

    }

    //Combination of array items containing 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;

                }

            }

        }

    }

    //If it's 2, there's one more term than 1 

    if(n == 2){

        result.push([2]);

    }

    //Add all ones 

    result.push(source);

    //Output all steps 

    print(result);

    console.log(' A total of :' + result.length + ' The motorway ');

}
//Run < br / >
countSteps(4);
//Output the following 

/*

    [ 1, 3 ]

    [ 4 ]

    [ 1, 1, 2 ]

    [ 2, 2 ]

    [ 1, 1, 1, 1 ]

     A total of :5 Kind of go 

*/

conclusion

This algorithm can be applied to the actually some kind of game, when two objects before a certain distance, business processing, to all of the possible, of course, can also be applied to other places, though most front end engineer for the practice of the algorithm is less, but it still has the value of existence, many UI details are actually using the algorithm, free later will post more about algorithms related articles, welcome everybody to give some valuable advice.