Drei JavaScript-Methoden zur Lösung des Joseph-Ring-Problems

Überblick

Das Joseph-Ring-Problem, auch bekannt als Joseph-Mordproblem oder Problem des verlorenen Taschentuchs, ist ein klassisches algorithmisches Problem. Es gibt viele Variationen in der Problembeschreibung, aber die Grundidee zur Lösung des Problems ist dieselbe. Dieser Artikel löst das Joseph-Ring-Problem auf drei Arten: zirkuläre verknüpfte Liste, geordnetes Array und mathematische Rekursion.

Problembeschreibung

Sehen wir uns zunächst an, was das Joseph-Ring-Problem ist.

Nachdem die Römer Chotapater besetzt hatten, versteckten sich 39 Juden mit Josephus und seinen Freunden in einer Höhle. Die 39 Juden beschlossen, lieber zu sterben, als sich vom Feind fangen zu lassen, und entschieden sich daher für eine Selbstmordmethode. Die 41 Personen standen im Kreis und die erste Person begann zu zählen. Jedes Mal, wenn die dritte Person gezählt hatte, musste diese Person Selbstmord begehen, und dann zählte die nächste Person erneut, bis alle Selbstmord begangen hatten. Josephus und seine Freunde wollten dem jedoch nicht nachkommen. Beginnen Sie mit einer Person, überspringen Sie k-2 Personen (weil die erste Person übersprungen wurde) und töten Sie die k-te Person. Überspringen Sie dann k-1 Personen und töten Sie die k-te Person. Dieser Prozess wiederholt sich kreisförmig, bis schließlich nur noch eine Person übrig ist, die weiterleben kann. Die Frage ist, wo man bei gegebenem und zu Beginn stehen muss, um der Hinrichtung zu entgehen.

Heute lautet die Beschreibung des Joseph-Ring-Problems im Allgemeinen:

Es befinden sich N Personen in einem Raum. Alle sitzen im Kreis und beginnen im Uhrzeigersinn zu zählen. Jedes Mal, wenn die Person M zählt, verlässt sie das Spiel. Die nächste Person, die das Spiel verlässt, beginnt erneut zu zählen, und die Person, die M meldet, verlässt das Spiel erneut, und dieser Zyklus wird fortgesetzt, bis nur noch eine Person im Spiel ist. Wie lautet die Nummer der letzten Person?

Zirkuläre verknüpfte Liste

Die Lösung des Problems der zirkulären verknüpften Liste ist relativ einfach. Sie müssen lediglich die Problembeschreibung in Code umwandeln. Die N Personen im Raum bilden eine verknüpfte Liste der Länge N, die Ende an Ende miteinander verbunden sind und so eine zirkuläre verknüpfte Liste bilden. Der Wert jedes Elements in der Liste ist die Nummer jeder Person. Wenn die Nummer M erreicht, wird das Element (als x bezeichnet) entfernt, d. h. das nächste des vorherigen Elements des Elements zeigt nicht mehr auf x, sondern auf x.next. Durchlaufen Sie die verknüpfte Liste auf diese Weise, bis nur noch ein Element darin übrig ist.

Werfen wir einen Blick auf die Codeimplementierung.

Funktion Listeerstelle(Anzahl) {
    //Datenstruktur der verknüpften Listenknoten Funktion createNode(value) {
        zurückkehren {
            Wert: Wert,
            nächste: ''
        }
    }
    //Kopfknoten auflisten let head = createNode(1);
    sei Knoten = Kopf;
    //Erstelle Assoziationen zwischen Knoten nach dem Kopfknoten for (let i = 2; i <= num; i++) {
        node.next = Knoten erstellen(i);
        Knoten = Knoten.nächster;
    }
    //Der letzte Knoten zeigt auf den Kopfknoten und bildet eine zirkuläre verknüpfte Liste node.next = head;
    Rücklaufkopf;
}
Funktion deleteListNode(num, nth) {
    //Erstellen Sie eine zirkuläre verknüpfte Liste mit der Datenlänge num let node = createList(num);
    //Wenn die Länge der verknüpften Liste > 1 ist, fahren Sie mit der nächsten Runde fort, während (num > 1) {
        für (lass i = 1; i <= n-te - 1; i++) {
            wenn (i == n-te - 1) {
                //Wenn i n-1 ist, dann ist node.next der n-te Knoten. node.next eliminieren
                Knoten.nächster = Knoten.nächster.nächster;
                // Länge der Linkliste --
                Nummer--;
            }
            Knoten = Knoten.nächster;
        }
    }
    //Der Wert des letzten verbleibenden Knotens ist die Nummer der letzten Person. return node.value
}
//deleteListNode(m,n), um das Endergebnis zu erhalten

Geordnetes Array

Verwenden Sie ein geordnetes Array, um eine zirkuläre verknüpfte Liste zu simulieren. Nach der ersten Durchquerung und Eliminierung des Arrays werden die verbleibenden Array-Elemente zu einem neuen Array zusammengefasst. Anschließend wird eine neue Runde der Durchquerung und Eliminierung für das neue Array ausgeführt und dieser Zyklus wird wiederholt, bis die Array-Länge 1 beträgt.

Werfen wir einen Blick auf die Codeimplementierung.

Funktion jhonRing(num, nth) {
    sei arr = [];
    //Erstelle ein geordnetes Array für (let i = 1; i <= num; i++) {
        arr[i - 1] = i;
    }
    //Wenn die Arraylänge größer als nth ist, kann das Array gefunden werden, ohne die zu entfernenden Daten in einer Schleife zu durchlaufen, while (arr.length >= nth) {
        lass newArr = [];
        //Verschiebe die verbleibenden Daten am Ende des Arrays an den Anfang des neuen Arrays und starte eine neue Durchlaufrunde mit den generierten Daten. let times = arr.length – arr.length % nth;
        newArr = arr.slice(Zeiten)
        arr.slice(0, mal).map((Element, Index) => {
            //Alle Daten außer den entfernten Daten zum neuen Array hinzufügen if ((index + 1) % nth !== 0) {
                newArr.push(Artikel)
            }
        })
        arr = neuesArr;
    }
    //Wenn die Arraylänge kleiner als n ist, muss das Array in einer Schleife durchlaufen werden, um die zu entfernenden Daten zu finden. Die Modulo-Operation kann die Anzahl der Durchläufe reduzieren, während (arr.length > 1) {
        // Nehmen Sie den Rest, um den Index der zu entfernenden Daten zu erhalten let index = nth % arr.length - 1;
        //Entferne die zweite Hälfte der Daten und kombiniere sie mit der ersten Hälfte, um ein neues Array zu bilden. let newArr = arr.slice(index + 1).concat(arr.slice(0, index));
        arr = neuesArr;
    }
}
//jhonRing(num, nth), um das Endergebnis zu erhalten

Der Vorgang zum Simulieren einer verknüpften Liste mit einem geordneten Array scheint dem einer verknüpften Liste zu ähneln, die zeitliche Komplexität scheint dieselbe zu sein und sogar der Code ist nicht so prägnant wie der einer verknüpften Liste. Warum schlagen wir diese Methode dennoch vor? Der Vorteil dieser Methode besteht darin, dass bei M>>N die geordnete verknüpfte Liste durch Übernahme des Rests die Anzahl der Durchläufe des Arrays effektiv verringert. Wenn wir N als 3 und M als 100 annehmen, muss die verknüpfte Liste 100/3+1-mal durchlaufen werden, während das geordnete Array basierend auf dem Ergebnis der Modulo-Operation 100/3-1=0 direkt den Index der zu entfernenden Daten als 0 erhält.

Mathematische Rekursion

Bei der Lösung des Joseph-Ring-Problems mit mathematischen Problemen kann es leicht passieren, dass man keine effektive Methode zum Zusammenfassen der Regeln findet. Im Folgenden verwenden wir M=3 als Beispiel, um die Umwege zu veranschaulichen, die wir beim Zusammenfassen der Regeln gemacht haben. (Sie können die ungültigen Ideen überspringen und unten die gültigen Ideen lesen.)

Vergleichen Sie mehrere Ergebnisse mit kleineren Datenmengen (❌)

Wenn N=1, f(1,3)=1;
Wenn N=2, f(2,3)=2;
Wenn N=3, f(3,3)=2;
Wenn N=4, f(4,3)=1;
Wenn N=5, f(5,3)=4;
Wenn N=6, ist f(6,3)=1;
Wenn N=7, f(7,3)=4;
Wenn N=8, f(8,3)=7;
Wenn N=9, f(9,3)=1;
Wenn N=10, f(10,3)=4;

Anhand von Beispielen können wir feststellen, dass das Endergebnis nicht immer zwischen bestimmten Zahlen liegt. Neben 1, 2 und 4 kommt auch 7 vor, und die nachfolgenden Ergebnisse können ähnliche Situationen aufweisen, d. h. das Endergebnis ist nicht immer auf eine bestimmte Zahl beschränkt. f(3,3) f(6,3) f(9,3) usw., wenn N ein Vielfaches von M ist, führen nicht zu denselben Ergebnissen, was zeigt, dass kein besonderer Zusammenhang zwischen dem Endergebnis und dem Vielfachen von 3 besteht. Daher ist es nicht sinnvoll, Muster durch Sammeln und Vergleichen der Ergebnisse zu finden, wenn die Datenmenge gering ist.

Vergleichen Sie die Beziehung zwischen den vorherigen Eliminierungsdaten (❌)

//Anzahl N Personen von 1 bis N
1, 2, 3, 4........N-2, N-1, N
//Die erste Eliminierungszahl ist M oder M%N, was als M%N zusammengefasst und als K aufgezeichnet werden kann. Dann wird die Sequenz für die zweite Eliminierung zu
K+1,K+2,.......N,1,2......K-1
//Die Nummer der zweiten Eliminierung ist K+M%(N-1) || M%(N-1)-(NK-1)
Nach dieser Regel gilt: Wenn N-(K+1)>M%(N-1), dann ist f(n)=f(n-1)+M%(N-(n-1)).
Wenn N-(K+1)<M%(N-1), f(n)=M%(N-(n-1))-(Nf(n-1)-1)

Durch Berechnung nach dieser Regel können wir feststellen, dass das vor der zweiten Durchlaufrunde erzielte Ergebnis korrekt ist, das Ergebnis nach der zweiten Durchlaufrunde jedoch falsch ist. Der grundlegende Grund besteht darin, dass die Daten nach dem Eintritt in die zweite Runde nicht mehr kontinuierlich sind. Die während der ersten Durchquerungsrunde eliminierten Daten wirken sich auf die Ergebnisse der zweiten Durchquerungsrunde aus, sodass diese Lösung nicht geeignet ist.

Probleme von oben nach unten analysieren und von unten nach oben lösen (✅)

Verwenden Sie rekursives Denken, um das Joseph-Ring-Problem zu analysieren. Nehmen Sie N=10 und M=3 als Beispiel für die Analyse.

//Nummeriere die 10 Personen beginnend bei 0 (ich werde später erklären, warum wir nicht bei 1 mit der Nummerierung beginnen können)
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
// Notieren Sie die Nummer der letzten Person, die die Warteschlange verlässt, als f(10,3)
//Nachdem 10 Personen nummeriert wurden, verlässt die erste Person die Warteschlange und erhält eine neue Warteschlange und Nummer
3, 4, 5, 6, 7, 8, 9, 0, 1
//Um die Nummer der neuen Warteschlange fortlaufend zu machen, können wir die neue Warteschlange als A aufzeichnen und schreiben
3, 4, 5, 6, 7, 8, 9, 10%10, 11%10
// Wenn eine normale Warteschlange von 9 Personen als B aufgezeichnet wird und das Endergebnis des Schreibens von 0,1,2,3,4,5,6,7,8 als f (9,3) aufgezeichnet wird, kann das Ergebnis der neuen Warteschlange A als (f (9,3) + 3)% 10 ausgedrückt werden.
//Die 9-Personen-Warteschlange A wird erhalten, indem eine Person aus der 10-Personen-Warteschlange entfernt wird. Dann muss das Ergebnis der 9-Personen-Warteschlange, die das Spiel gemäß den Regeln N = 9, M = 3 und Anfangsnummer 3 spielt, dasselbe sein wie das Ergebnis der letzten Person, die die Warteschlange mit N = 10, M = 3 und Anfangsnummer 0 verlässt.
//Daher besteht eine Beziehung zwischen der Nummer der letzten Person, die die Warteschlange von 10 verlässt, und der Nummer der Person, die die Warteschlange A von 9 Personen verlässt f(10,3)=(f(9,3)+3)%10

Aus dem oben Gesagten können wir schlussfolgern, dass f(N,M)=(f(N-1,M)+M)%N. Das endgültige Nummerierungsergebnis ist f(N,M)+1.
Warum kann die Nummerierung nicht bei 1 beginnen? Weil das Rückgabeergebnis der Restoperation bei 0 beginnt.

Funktion Josephus(Anzahl, n-te){
    wenn(num==1){
        gebe 0 zurück;
    }anders{
        Rückgabewert (Josephus(Zahl-1,n-ter)+n-ter)%Zahl
    }
}
//Josephus(N,M)+1 ist die Endzahl

Optimieren Sie die rekursive Funktion

Funktion JosephusR(num,nth){
    lass Wert = 0;
    für (lass i = 1; i <= num; i++) {
        //Hier ist der Modul von i. In der obigen Rekursion wird auch num allmählich kleiner, also ist hier i statt num
        Wert=(Wert+n-ter)%i;
    }
    Rückgabewert+1;
}
//JosephusR(N,M) ist die letzte Zahl

Zusammenfassen

Durch mathematische rekursive Optimierung wird die Zeitkomplexität des Joseph-Ring-Problems von ursprünglich O(mn) auf O(n) reduziert. Die Lösung des Problems über eine zirkuläre verknüpfte Liste ist zwar die schnellste und einfachste Denkweise, aber diese mathematische rekursive Methode ist für die Lösung solcher algorithmischer Probleme wertvoller.

Damit ist der Artikel über drei JavaScript-Methoden zur Lösung des Joseph-Ring-Problems abgeschlossen. Weitere JavaScript-Inhalte zum Joseph-Ring finden Sie in früheren Artikeln auf 123WORDPRESS.COM oder in den folgenden verwandten Artikeln. Ich hoffe, Sie werden 123WORDPRESS.COM auch in Zukunft unterstützen!