Sharing an algorithm for calculating the number of digital steps implemented in JavaScript_javascript skills

In the past two days, I looked at the github of a certain master and found out that he is more interested in algorithms. I saw one of the step counting algorithms for calculating numbers. I thought it was interesting, so I implemented one myself.

Algorithm description and implementation principle

Given an integer number, count how many moves can reach the goal. For example, a number 4 can have the following moves

Copy code The code is as follows:

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

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

1. First list all combinations whose items are 1
2. From left to right, the combinations whose items are 1
3. Recurse the above set, find the index of 1 in the item, and then calculate the values ​​of the 2 items from the left. The result is recursive operation
4. Exclude situations 1 and 2

The following three tool functions are provided:

Copy code The code is as follows:

// Calculate the value in the array
function calculate(arg){
Return eval(arg.join(' '));
}

//Output the value of the array
function print(arg){
for(var i = 0; i < arg.length; i ){
console.log(arg[i]);
}
}

// Check whether it is a forward or reverse move
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:

Copy code The code is as follows:

function countSteps(n){
var counts = 0,i,j = 0;
var result = [];
var newresult = [];
var source = [];
var temparg = [];
// Generate an array with all items being 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){
// Generate an array with items increasing by 1 from left to right
                                                      // 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));
            }
}
}
// Combine 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;
                }
            }
}
}
//When it is 2, there is one more item than 1
If(n == 2){
         result.push([2]);
}
// Add the case where all are 1
result.push(source);
// Output all steps
Print(result);
console.log('A total of:' result.length 'number of moves');
}

//Run
countSteps(4);

// Output the following content
/*
[ 1, 3 ]
[ 4 ]
[ 1, 1, 2 ]
[ 2, 2 ]
[ 1, 1, 1, 1 ]
There are a total of: 5 types of walking
*/

Summary

This algorithm can actually be applied to certain types of games. When the distance between two objects is constant, all possibilities can be processed. Of course, it can also be applied to other places. Although most front-end engineers are not familiar with the algorithm. There is relatively little practice, but it still has value. Algorithms are actually used in many UI details. I will post more articles about algorithms when I have time in the future. Welcome to give me more valuable opinions.