Partage d'un algorithme de calcul du nombre d'étapes numériques implémentées dans les compétences JavaScript_javascript

Au cours des deux derniers jours, j'ai regardé le github d'un certain maître et j'ai découvert qu'il s'intéressait davantage aux algorithmes. J'ai vu un des algorithmes de comptage de pas pour calculer des nombres que j'ai trouvé intéressant, alors j'ai implémenté. un moi-même.

Description de l'algorithme et principe de mise en œuvre

Étant donné un nombre entier, comptez combien de mouvements peuvent atteindre l'objectif. Par exemple, un chiffre 4 peut avoir les mouvements suivants

Copier le code Le code est le suivant :

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

En fait, la conclusion suivante peut être tirée de la combinaison ci-dessus.

1. Commencez par lister toutes les combinaisons dont les éléments sont 1
2. De gauche à droite, les combinaisons dont les éléments sont 1
3. Récursez l'ensemble ci-dessus, recherchez l'indice 1 dans l'élément, puis calculez les valeurs des 2 éléments à partir de la gauche. Le résultat est une opération récursive
. 4. Exclure les situations 1 et 2

Les trois fonctions d'outils suivantes sont fournies :

Copier le code Le code est le suivant :

// Calcule la valeur dans le tableau
fonction calculer(arg){
Retour eval(arg.join(' '));
>

//Afficher la valeur du tableau
fonction print(arg){
pour(var je = 0; je < arg.length; je ){
console.log(arg[i]);
>
>

// Vérifiez s'il s'agit d'un mouvement avant ou arrière
fonction hasRepeat(src, dist){
Si (dist.length != 2) renvoie false ;
pour(var je = 0, len = src.length; je < len ; je ){
Si(dist.length == src[i].length){
Si(dist[0] == src[i][1]){
                    return true ;
            }
>
>
Renvoie faux ;
>

L'implémentation de l'algorithme est publiée ci-dessous :

Copier le code Le code est le suivant :

fonction countSteps(n){
var compte = 0,i,j = 0;
var résultat = [];
var nouveau résultat = [];
var source = [];
var temparg = [];
// Génère un tableau avec tous les éléments valant 1
pour(je = 1; je <= n ; je ){
          source.push(1);
>
Si(n > 2){
pour(j = 1; j < n - 1; j ){
Temparg.longueur = 0;
                 if(j < n - 1){
// Génère un tableau avec des éléments augmentant de 1 de gauche à droite
                                                     // 1.. 11.. 111..
                  Array.prototype.push.apply(temparg, source.slice(0, j));
                temparg.push(calculate(source.slice(j,n)));
                   result.push(temparg.slice(0));
                           // Récurse le contenu du tableau jusqu'à ce qu'il n'y ait pas de 1 dans l'élément
                   combiner(temparg.slice(0));
            }
>
>
// Combine les éléments du tableau contenant 1
// 111->21->3
fonction combiner(arg){
var linéaire = [];
pour(var je = 0; je < arg.length; je ){
Si(arg[i] == 1){
Si(je ==0 || je == 1){
Linearg.push(calculate(arg.slice(0,2)));
                      Array.prototype.push.apply(linearg, arg.slice(2, arg.length));
Si(!hasRepeat(result, Linearg)){
                              result.push(linearg);
                          combiner(linearg.slice(0));
                 }
                    revenir ;
                }
            }
>
>
//Quand il est 2, il y a un élément de plus que 1
Si(n == 2){
         result.push([2]);
>
// Ajoute le cas où tous valent 1
résultat.push(source);
// Afficher toutes les étapes
Imprimer(résultat);
console.log('Un total de :' result.length 'nombre de coups');
>

//Courir
countSteps(4);

// Afficher le contenu suivant
/*
[ 1, 3 ]
[ 4 ]
[ 1, 1, 2 ]
[ 2, 2 ]
[ 1, 1, 1, 1 ]
Il existe au total : 5 types de marche
*/

Résumé

Cet algorithme peut en fait être appliqué à certains types de jeux. Lorsque la distance entre deux objets est constante, toutes les possibilités peuvent être traitées. Bien sûr, il peut également être appliqué à d'autres endroits. Je suis familier avec l'algorithme. Il y a relativement peu de pratique, mais il a toujours de la valeur. Les algorithmes sont en fait utilisés dans de nombreux détails de l'interface utilisateur. Je publierai plus d'articles sur les algorithmes lorsque j'aurai le temps de me donner des avis plus précieux. 🎜>