Nim dan Bilangan Grundy
Menyelesaikan permainan impartial dengan XOR
Nim dan Bilangan Grundy adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Berkenalan dengan Permainan Nim
Dalam Nim terdapat beberapa tumpukan batu. Pada giliran Anda, ambil sejumlah batu dari satu tumpukan, dan pemain yang mengambil batu terakhir menang. 🪨
Besaran Ajaib: XOR
Seluruh permainan ditentukan oleh XOR dari ukuran semua tumpukan. Satu bilangan itu memberi tahu siapa yang akan menang.
Aturan Jumlah Nim
Jika XOR semua tumpukan, yang disebut jumlah Nim, adalah nol, pemain yang akan melangkah kalah. Jika bukan nol, pemain tersebut menang.
piles = [3, 4, 5]
nim_sum = 0
for p in piles:
nim_sum ^= pMengapa Nol Berarti Masalah
Dari jumlah Nim nol, setiap langkah akan merusak keseimbangan dan memberikan jumlah tak nol kepada lawan, yang selalu dapat mengembalikannya.
Menemukan Langkah Kemenangan
Ketika jumlah Nim tidak nol, selalu ada langkah yang mengembalikannya menjadi nol. Langkah itu menempatkan lawan pada posisi kalah.
Melampaui Nim: Bilangan Grundy
Untuk permainan tidak memihak lainnya, kita menggunakan satu bilangan Grundy untuk setiap keadaan. Bilangan ini menggeneralisasi gagasan jumlah Nim ke hampir semua permainan pengambilan.
Operasi mex
Nilai Grundy suatu keadaan adalah mex: bilangan bulat tak negatif terkecil yang tidak terdapat di antara nilai Grundy dari langkah-langkahnya.
def mex(s):
i = 0
while i in s:
i += 1
return iMenghitung Grundy dengan Rekursi
Lakukan rekursi ke semua keadaan yang dapat dicapai, kumpulkan nilai Grundy-nya, lalu ambil mex dari himpunan tersebut.
def grundy(n):
return mex({grundy(n - k) for k in (1, 2, 3) if k <= n})Grundy Nol Berarti Kalah
Satu keadaan permainan dengan Grundy 0 merupakan posisi kalah, persis seperti jumlah Nim nol. Nilai tak nol berarti menang.
Teorema Sprague-Grundy
Untuk permainan independen yang dimainkan bersamaan, lakukan XOR pada bilangan Grundy-nya. Hasil Sprague-Grundy ini mengubah gabungan permainan apa pun menjadi Nim. ✨
Kapan Ini Berlaku
Teori Grundy memerlukan permainan yang tidak memihak: kedua pemain memiliki langkah yang sama dan pemain yang melangkah terakhir menang. Periksa hal itu sebelum menggunakannya.
Pemeriksaan Singkat
Anda memulai permainan Nim dengan tumpukan 1, 2, dan 3. Apakah Anda akan menang?
Rangkuman
Nim bergantung pada XOR tumpukan: nilai nol kalah, nilai tak nol menang. Bilangan Grundy dan mex memperluas gagasan ini ke banyak permainan yang tidak memihak. 🏆
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Nim dan Bilangan Grundy” gratis?
Ya — teks lengkap “Nim dan Bilangan Grundy” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Nim dan Bilangan Grundy”?
Menyelesaikan permainan impartial dengan XOR Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Nim dan Bilangan Grundy” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- State Menang & Kalah dalam Permainan
- Nim dan Bilangan Grundy
- Meet in the Middle
- Debug Cepat: Stress Test & Triage