I looked at the github of a certain master in the past two days and knew that he was more interested in algorithms. After reading one of the step algorithms for calculating numbers, I felt that this was a bit interesting, so I realized one by myself.
Algorithm description and implementation principle
Given an integer number, count how many ways to move can reach the goal, such as a number 4, there are the following ways to move
The code copy is as follows:
[ 1, 3 ]
[ 4 ]
[ 1, 1, 2 ]
[ twenty two ]
[ 1, 1, 1, 1 ]
In fact, the following conclusions can be drawn through the above combination.
1. First list all the items are combinations of 1
2. Combination of 1 from left to right
3. Recursively find the index of 1 in the item, and then calculate the value of 2 items from the left, and recursively this operation
4. Exclude situations of 1 and 2
Here are three tool functions:
The code copy is as follows:
// Calculate the values 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 the right or wrong way
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 following is an implementation of the algorithm:
The code copy 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 of 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 1 increments 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));
// The contents in the recursive 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 more than 1
if(n == 2){
result.push([2]);
}
// Add all 1
result.push(source);
// Output all steps
print(result);
console.log('There are ' in total:' + result.length + 's way of walking');
}
// Run
countSteps(4);
// Output the following content
/*
[ 1, 3 ]
[ 4 ]
[ 1, 1, 2 ]
[ twenty two ]
[ 1, 1, 1, 1 ]
There are 5 types of walking in total
*/
Summarize
This algorithm can actually be applied to certain types of games. When the distance between two objects is certain, all possible business processing can be performed, and of course it can also be applied to other places. Although most front-end engineers have less practices with algorithms, it still has value. Many UI details actually use algorithms. I will post more articles about algorithms when I have time. Everyone is welcome to give me some valuable opinions.