State Menang & Kalah dalam Permainan
Menalar siapa yang menang dengan permainan optimal
State Menang & Kalah dalam Permainan adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 1 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 Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Dua Pemain, Permainan Sempurna
Dalam permainan kombinatorial, dua pemain bergantian melakukan langkah, keduanya bermain secara sempurna, dan pemain yang tidak dapat bergerak kalah. Tugas Anda hanyalah memprediksi pemenangnya. 🎯
Setiap Posisi Memiliki Label
Setiap posisi permainan adalah sebuah keadaan. Tugas Anda adalah memberi label pada setiap keadaan sebagai menang atau kalah bagi pemain yang akan melangkah.
Makna Keadaan Menang
Sebuah keadaan merupakan keadaan menang jika pemain yang akan melangkah memiliki setidaknya satu langkah yang menuju keadaan kalah bagi lawannya.
Makna Keadaan Kalah
Sebuah keadaan merupakan keadaan kalah jika setiap langkah yang Anda lakukan memberikan keadaan menang kepada lawan. Anda akan tetap terjebak apa pun yang dilakukan.
Kasus Dasar
Posisi ketika Anda sama sekali tidak dapat bergerak adalah kasus dasar. Pemain yang menghadapinya sudah kalah, jadi tandai posisi itu sebagai kalah.
Membangun dari Bawah
Mulailah dari kasus dasar dan lanjutkan ke luar. Label setiap keadaan baru hanya bergantung pada keadaan yang dituju oleh langkahnya.
Satu Langkah Baik Sudah Cukup
Untuk menang, Anda hanya membutuhkan satu langkah menuju keadaan kalah bagi lawan. Menemukan satu jalan keluar saja sudah cukup.
Contoh Kecil
Ambil 1 atau 2 batu dari tumpukan; pemain yang mengambil batu terakhir menang. Dengan 0 batu, pemain yang melangkah kalah, jadi itu adalah keadaan kalah.
Menulis Pemeriksaan Kemenangan
Rekursi ini memberi label pada suatu keadaan dengan mencoba setiap langkah dan melakukan rekursi pada hasilnya. ⚙️
def win(n):
if n == 0:
return False
return any(not win(n - k) for k in (1, 2))Gunakan Memo agar Tetap Cepat
Keadaan yang sama muncul kembali di berbagai cabang, jadi simpan setiap hasil. Sebuah memo sederhana mengubah pekerjaan eksponensial menjadi waktu linear.
from functools import lru_cache
@lru_cache(None)
def win(n):
return n != 0 and any(not win(n - k) for k in (1, 2))Simetri adalah Jalan Pintas
Jika suatu posisi benar-benar simetris, pemain kedua sering kali dapat meniru langkah lawan dan menang. Perhatikan trik peniruan ini.
Pemeriksaan Singkat
Anda menghadapi suatu keadaan. Kapan keadaan itu menjadi keadaan kalah bagi Anda?
Rangkuman
Sekarang Anda memberi label pada keadaan: sebuah win memiliki satu langkah menuju kekalahan lawan, sedangkan keadaan kalah tidak memilikinya. Bangun dari kasus dasar dan gunakan memo. 🧠
Pertanyaan yang Sering Diajukan
Apakah pelajaran “State Menang & Kalah dalam Permainan” gratis?
Ya — teks lengkap “State Menang & Kalah dalam Permainan” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “State Menang & Kalah dalam Permainan”?
Menalar siapa yang menang dengan permainan optimal Kamu berlatih Competitive Programming Academy 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 Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy 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 1 dari 4.
Berapa lama pelajaran “State Menang & Kalah dalam Permainan” 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 Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy 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