Zyklen in Simulationen erkennen
Überspringen Sie Schritte, wenn sich der Zustand wiederholt
Zyklen in Simulationen erkennen ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Wenn sich Schritte wiederholen
Manche Simulationen fragen nach dem Zustand nach einer riesigen Anzahl von Schritten, etwa einer Billion. Ein Schritt nach dem anderen würde niemals rechtzeitig fertig werden. ⏳
Zustände sind endlich
Wenn die Anzahl möglicher Zustände begrenzt ist, muss die Simulation irgendwann einen Zustand erneut erreichen. Ab diesem Punkt wiederholt sie sich für immer in einem Zyklus.
Wie ein Zyklus aussieht
Der Pfad hat einen Vorlauf, der in eine Schleife führt, und danach einen sich wiederholenden Zyklus. Wenn Sie die Schleife erkennen, können Sie Milliarden von Schritten überspringen.
Merken Sie sich, wo Sie gewesen sind
Speichern Sie jeden Zustand in einem Dictionary, das ihn auf die Schrittzahl abbildet, bei der Sie ihn zum ersten Mal gesehen haben. Wenn er erneut auftaucht, erkennen Sie den Zyklus.
seen = {}Erkennen Sie die Wiederholung
Prüfen Sie vor jedem Schritt, ob der aktuelle Zustand bereits in seen enthalten ist. Falls ja, haben Sie gerade die Schleife geschlossen.
if state in seen:
start = seen[state]Messen Sie die Zykluslänge
Die Länge ist die aktuelle Schrittzahl minus der Schrittzahl, bei der Sie diesen Zustand zum ersten Mal gesehen haben. Genau so viele Schritte führen zum Zustand zurück.
length = step - seen[state]Mit Modulo vorspringen
Ziehen Sie den Vorlauf ab und nehmen Sie für die verbleibenden Schritte den Modulo der Zykluslänge. Nun müssen Sie nur noch einen winzigen Rest simulieren.
rem = (N - start) % lengthSimulieren Sie die verbleibenden Schritte
Führen Sie die Simulation nur für diese verbleibenden Schritte ab dem Zyklusbeginn aus. Der Endzustand entspricht dann exakt dem Zustand nach Schritt N.
for _ in range(rem):
state = step_fn(state)Halten Sie den Zustand hashbar
Dictionary-Schlüssel müssen hashbar sein. Wandeln Sie daher Listen vor dem Speichern in Tupel um. Ein veränderlicher Zustand kann kein Schlüssel sein.
key = tuple(row)Floyd ohne Speicher
Wenn Zustände zu groß zum Speichern sind, findet Floyds Schildkröten-und-Hasen-Verfahren mit zwei Zeigern und nahezu keinem zusätzlichen Speicher einen Zyklus.
Warum das den Tag rettet
Die Zykluserkennung verwandelt eine unmögliche Schleife mit einer Billion Schritten in einige Tausend Schritte. Die Wiederholung zu erkennen, ist der gesamte Trick.
Schnelltest
Sie haben den aktuellen Zustand erstmals bei Schritt s gesehen und befinden sich jetzt bei Schritt t.
Zusammenfassung
Wenn sich Zustände wiederholen, speichern Sie jeden in einer Map, bestimmen Sie die Zykluslänge, springen Sie mit Modulo voraus und simulieren Sie nur die verbleibenden Schritte. 🚀
Häufig gestellte Fragen
Ist die Lektion „Zyklen in Simulationen erkennen“ kostenlos?
Ja — der vollständige Text von „Zyklen in Simulationen erkennen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Zyklen in Simulationen erkennen“?
Überspringen Sie Schritte, wenn sich der Zustand wiederholt Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Zyklen in Simulationen erkennen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Zustand modellieren und voranschreiten
- Rasterbewegungen und Richtungsvektoren
- Zyklen in Simulationen erkennen
- Knifflige Sonderfälle beherrschen