Nim und die Grundy-Zahl
Lösen Sie unparteiische Spiele mit XOR
Nim und die Grundy-Zahl ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 2 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.
Lernen Sie das Nim-Spiel kennen
Bei Nim gibt es mehrere Steinhaufen. In Ihrem Zug entfernen Sie eine beliebige Anzahl von Steinen aus einem Haufen, und wer den letzten Stein nimmt, gewinnt. 🪨
Die magische Größe: XOR
Das gesamte Spiel wird durch das XOR aller Haufengrößen entschieden. Diese eine Zahl verrät, wer gewinnt.
Die Nim-Summen-Regel
Ist das XOR der Haufen, die sogenannte Nim-Summe, gleich null, verliert der Spieler am Zug. Ist sie ungleich null, gewinnt dieser Spieler.
piles = [3, 4, 5]
nim_sum = 0
for p in piles:
nim_sum ^= pWarum Null problematisch ist
Aus einer Null-Nim-Summe heraus zerstört jeder Zug das Gleichgewicht und überlässt dem Gegner eine von null verschiedene Summe, die dieser immer wieder auf null setzen kann.
Den Gewinnzug finden
Wenn die Nim-Summe ungleich null ist, gibt es immer einen Zug, der sie wieder auf null setzt. Damit bringen Sie den Gegner in eine Verluststellung.
Über Nim hinaus: Grundy-Zahlen
Für andere unparteiische Spiele verwenden wir pro Zustand eine Grundy-Zahl. Sie verallgemeinert die Idee der Nim-Summe auf fast jedes Spiel, bei dem Steine oder andere Objekte weggenommen werden.
Die mex-Operation
Der Grundy-Wert eines Zustands ist das mex: die kleinste nichtnegative ganze Zahl, die unter den Grundy-Werten seiner Züge fehlt.
def mex(s):
i = 0
while i in s:
i += 1
return iGrundy rekursiv berechnen
Berechnen Sie rekursiv alle erreichbaren Zustände, sammeln Sie deren Grundy-Werte und bestimmen Sie anschließend das mex dieser Menge.
def grundy(n):
return mex({grundy(n - k) for k in (1, 2, 3) if k <= n})Grundy 0 bedeutet Verlust
Ein einzelner Spielzustand mit Grundy 0 ist eine Verluststellung, genau wie eine Nim-Summe von null. Ein Wert ungleich null bedeutet einen Gewinn.
Der Satz von Sprague und Grundy
Bei mehreren unabhängigen Spielen, die gleichzeitig gespielt werden, verknüpfen Sie ihre Grundy-Zahlen mit XOR. Dieses Sprague-Grundy-Ergebnis macht aus jeder Summe von Spielen ein Nim-Spiel. ✨
Wann die Theorie anwendbar ist
Die Grundy-Theorie setzt ein unparteiisches Spiel voraus: Beide Spieler haben dieselben Züge und wer den letzten Zug macht, gewinnt. Prüfen Sie das, bevor Sie die Theorie verwenden.
Kurzer Check
Sie beginnen ein Nim-Spiel mit den Haufen 1, 2 und 3. Gewinnen Sie?
Zusammenfassung
Bei Nim kommt es auf das XOR der Haufen an: Null bedeutet Verlust, ein Wert ungleich null bedeutet Gewinn. Grundy-Zahlen und mex erweitern diese Idee auf viele unparteiische Spiele. 🏆
Häufig gestellte Fragen
Ist die Lektion „Nim und die Grundy-Zahl“ kostenlos?
Ja — der vollständige Text von „Nim und die Grundy-Zahl“ 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 „Nim und die Grundy-Zahl“?
Lösen Sie unparteiische Spiele mit XOR 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 2 von 4.
Wie lange dauert die Lektion „Nim und die Grundy-Zahl“?
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
- Gewinn- und Verlustzustände in Spielen
- Nim und die Grundy-Zahl
- Meet in the Middle
- Schnell debuggen: Stresstests und Triage