Teilen eines Algorithmus zur Berechnung der Anzahl der in JavaScript implementierten digitalen Schritte_Javascript-Kenntnisse

In den letzten zwei Tagen habe ich mir den Github eines bestimmten Meisters angesehen und festgestellt, dass er sich mehr für Algorithmen interessiert. Ich habe einen der Schrittzählalgorithmen zum Berechnen von Zahlen gesehen, also habe ich ihn implementiert selbst eins.

Algorithmusbeschreibung und Implementierungsprinzip

Zählen Sie bei einer gegebenen ganzen Zahl, wie viele Züge das Ziel erreichen können. Beispielsweise kann eine Zahl 4 die folgenden Züge haben

Code kopieren Der Code lautet wie folgt:

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

Tatsächlich kann aus der obigen Kombination die folgende Schlussfolgerung gezogen werden.

1. Listen Sie zunächst alle Kombinationen auf, deren Elemente 1 sind
2. Von links nach rechts die Kombinationen, deren Elemente 1 sind
3. Rekursieren Sie den obigen Satz, suchen Sie den Index 1 im Element und berechnen Sie dann die Werte der beiden Elemente von links. Das Ergebnis ist eine rekursive Operation
4. Schließen Sie die Situationen 1 und 2 aus

Die folgenden drei Werkzeugfunktionen stehen zur Verfügung:

Code kopieren Der Code lautet wie folgt:

// Berechne den Wert im Array
Funktion berechne(arg){
Gibt eval(arg.join(''));
zurück }

//Gib den Wert des Arrays aus
Funktion print(arg){
for(var i = 0; i < arg.length; i ){
console.log(arg[i]);
}
}

// Überprüfen Sie, ob es sich um eine Vorwärts- oder Rückwärtsbewegung handelt
Funktion hasRepeat(src, dist){
Wenn (dist.length != 2) false zurückgibt;
for(var i = 0, len = src.length; i < len ; i ){
If(dist.length == src[i].length){
If(dist[0] == src[i][1]){
                    return true;
            }
}
}
Gibt false zurück;
}

Die Implementierung des Algorithmus ist unten aufgeführt:

Code kopieren Der Code lautet wie folgt:

Funktion countSteps(n){
var counts = 0,i,j = 0;
var result = [];
var newresult = [];
var source = [];
var temparg = [];
// Erzeuge ein Array, bei dem alle Elemente 1 sind
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){
// Erzeuge ein Array mit Elementen, die von links nach rechts um 1 ansteigen
                                                     // 1.. 11.. 111..
                   Array.prototype.push.apply(temparg, source.slice(0, j));
              temparg.push(calculate(source.slice(j,n)));
                  result.push(temparg.slice(0));
                         // Den Inhalt des Arrays rekursieren, bis im Element
keine 1 mehr vorhanden ist                    kombinieren(temparg.slice(0));
            }
}
}
// Array-Elemente kombinieren, die 1 enthalten
// 111->21->3
Funktion kombinieren(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);
                          kombinieren(linearg.slice(0));
                 }
                    zurück;
                }
            }
}
}
//Wenn es 2 ist, gibt es ein Element mehr als 1
If(n == 2){
         result.push([2]);
}
// Füge den Fall hinzu, in dem alle 1 sind
result.push(source);
// Alle Schritte ausgeben
Drucken(Ergebnis);
console.log('Insgesamt:' result.length 'Anzahl der Züge');
}

//Ausführen
countSteps(4);

// Den folgenden Inhalt ausgeben
/*
[ 1, 3 ]
[ 4 ]
[ 1, 1, 2 ]
[ 2, 2 ]
[ 1, 1, 1, 1 ]
Insgesamt gibt es: 5 Arten des Gehens
*/

Zusammenfassung

Dieser Algorithmus kann tatsächlich auf bestimmte Arten von Spielen angewendet werden, wenn der Abstand zwischen zwei Objekten konstant ist. Natürlich kann er auch auf andere Orte angewendet werden Ich bin mit dem Algorithmus relativ wenig vertraut, aber er wird in vielen UI-Details verwendet. Ich werde in Zukunft weitere Artikel über Algorithmen veröffentlichen 🎜>