Nim dan Nombor Grundy
Selesaikan permainan tidak berat sebelah dengan XOR.
Nim dan Nombor Grundy ialah pelajaran Competitive Programming Academy percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Competitive Programming Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Competitive Programming Academy merangkumi sejumlah 4 pelajaran.
Kenali Permainan Nim
Dalam Nim terdapat beberapa longgokan batu. Pada giliran anda, keluarkan sebarang bilangan batu daripada satu longgokan, dan pemain yang mengambil batu terakhir menang. 🪨
Kuantiti Ajaib: XOR
Keseluruhan permainan ditentukan oleh XOR bagi saiz semua longgokan. Satu nombor itu memberitahu anda siapa yang akan menang.
Peraturan Jumlah Nim
Jika XOR bagi longgokan, yang dipanggil jumlah Nim, ialah sifar, pemain yang mendapat giliran kalah. Jika nilainya bukan sifar, pemain itu menang.
piles = [3, 4, 5]
nim_sum = 0
for p in piles:
nim_sum ^= pMengapa Sifar Membawa Masalah
Daripada jumlah Nim sifar, setiap gerakan memecahkan keseimbangan dan memberikan lawan jumlah bukan sifar yang sentiasa boleh dipulihkan olehnya.
Mencari Gerakan Menang
Apabila jumlah Nim bukan sifar, sentiasa ada gerakan yang mengembalikannya kepada sifar. Gerakan itu meletakkan lawan dalam kedudukan kalah.
Melangkaui Nim: Nombor Grundy
Untuk permainan tidak berat sebelah yang lain, kami menggunakan satu nombor Grundy bagi setiap keadaan. Ia memperluas idea jumlah Nim kepada hampir semua permainan mengambil-batu.
Operasi mex
Nilai Grundy bagi sesuatu keadaan ialah mex: integer bukan negatif terkecil yang tiada dalam nilai Grundy bagi gerakan-gerakannya.
def mex(s):
i = 0
while i in s:
i += 1
return iMengira Grundy dengan Rekursi
Lakukan rekursi pada semua keadaan yang boleh dicapai, kumpulkan nilai Grundy dan kemudian ambil mex bagi himpunan tersebut.
def grundy(n):
return mex({grundy(n - k) for k in (1, 2, 3) if k <= n})Grundy Sifar Bererti Kalah
Satu keadaan permainan dengan Grundy 0 ialah kedudukan kalah, sama seperti jumlah Nim sifar. Nilai bukan sifar bermaksud menang.
Teorem Sprague-Grundy
Untuk permainan bebas yang dimainkan serentak, lakukan XOR terhadap nombor Grundy masing-masing. Keputusan Sprague-Grundy ini menukarkan sebarang jumlah permainan kepada Nim. ✨
Bila Ia Terpakai
Teori Grundy memerlukan permainan tidak berat sebelah: kedua-dua pemain mempunyai gerakan yang sama dan pemain yang bergerak terakhir menang. Semak perkara itu sebelum menggunakannya.
Semakan Pantas
Anda memulakan permainan Nim dengan longgokan 1, 2 dan 3. Adakah anda akan menang?
Rumusan
Nim bergantung pada XOR bagi longgokan: sifar bermaksud kalah, manakala bukan sifar bermaksud menang. Nombor Grundy dan mex memperluas idea ini kepada banyak permainan tidak berat sebelah. 🏆
Pelajari Python dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 30
- Pelajaran
- 120
Soalan Lazim
Adakah pelajaran “Nim dan Nombor Grundy” percuma?
Ya — teks penuh “Nim dan Nombor Grundy” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Competitive Programming Academy, tingkat taraf kepada CoddyKit PRO. Kursus Competitive Programming Academy merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Nim dan Nombor Grundy”?
Selesaikan permainan tidak berat sebelah dengan XOR. Anda berlatih Competitive Programming Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Competitive Programming Academy?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Competitive Programming Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 2 daripada 4.
Berapa lamakah pelajaran “Nim dan Nombor Grundy” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Keadaan Menang dan Kalah dalam Permainan
- Nim dan Nombor Grundy
- Bertemu di Tengah
- Nyahpepijat dengan Pantas: Ujian Tekanan dan Triage