Deteksi Siklus dalam Simulasi
Melompat ke depan saat state berulang
Deteksi Siklus dalam Simulasi adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 3 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.
Saat Langkah Berulang
Beberapa simulasi meminta keadaan setelah jumlah langkah yang sangat besar, misalnya satu triliun. Melangkah satu per satu tidak akan pernah selesai tepat waktu. ⏳
Keadaan Itu Terbatas
Jika jumlah keadaan yang mungkin terbatas, simulasi pada akhirnya pasti mengunjungi kembali salah satunya. Setelah itu, keadaan tersebut terus berulang dalam sebuah siklus.
Seperti Apa Siklus Itu
Lintasan memiliki ekor yang mengarah masuk, lalu sebuah perulangan yang terus berulang. Menemukan perulangan tersebut memungkinkan Anda melewati miliaran langkah dengan cepat.
Ingat Tempat yang Pernah Dikunjungi
Simpan setiap keadaan dalam kamus yang memetakannya ke nomor langkah saat pertama kali Anda melihatnya. Melihat keadaan itu lagi akan mengungkap siklusnya.
seen = {}Deteksi Pengulangan
Sebelum setiap langkah, periksa apakah keadaan saat ini sudah ada di telah_dilihat. Jika ada, berarti Anda baru saja menutup siklus.
if state in seen:
start = seen[state]Ukur Panjang Siklus
Panjang siklus adalah langkah saat ini dikurangi langkah ketika Anda pertama kali melihat keadaan tersebut. Sejumlah langkah itu akan membawa keadaan kembali tepat ke posisi semula.
length = step - seen[state]Lewati dengan Operasi Modulo
Kurangi bagian ekor, lalu ambil sisa langkah secara modulo panjang siklus. Kini Anda hanya perlu mensimulasikan sedikit langkah yang tersisa.
rem = (N - start) % lengthSelesaikan Langkah yang Tersisa
Jalankan simulasi hanya selama langkah-langkah tersisa tersebut, mulai dari awal siklus. Keadaan akhir akan sama persis dengan keadaan pada langkah N.
for _ in range(rem):
state = step_fn(state)Pertahankan Keadaan agar Dapat Di-hash
Kunci kamus harus dapat di-hash, jadi ubah daftar menjadi tupel sebelum menyimpannya. Keadaan yang dapat berubah tidak dapat dijadikan kunci.
key = tuple(row)Floyd Tanpa Memori
Jika keadaan terlalu besar untuk disimpan, algoritma kura-kura dan kelinci milik Floyd menemukan siklus menggunakan dua penunjuk dan hampir tanpa memori tambahan.
Mengapa Ini Menyelamatkan Anda
Deteksi siklus mengubah perulangan triliunan langkah yang mustahil menjadi beberapa ribu langkah. Mengenali pengulangan adalah satu-satunya triknya.
Pemeriksaan Singkat
Anda pertama kali melihat keadaan saat ini pada langkah s, dan sekarang berada pada langkah t.
Ringkasan
Saat keadaan berulang, catat setiap keadaan dalam sebuah pemetaan, temukan panjang siklus, lewati langkah dengan modulo, dan simulasikan hanya langkah yang tersisa. 🚀
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Deteksi Siklus dalam Simulasi” gratis?
Ya — teks lengkap “Deteksi Siklus dalam Simulasi” 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 “Deteksi Siklus dalam Simulasi”?
Melompat ke depan saat state berulang 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 3 dari 4.
Berapa lama pelajaran “Deteksi Siklus dalam Simulasi” 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
- Memodelkan State dan Melangkah Maju
- Perjalanan pada Grid dan Vektor Arah
- Deteksi Siklus dalam Simulasi
- Menaklukkan Kasus Tepi yang Rumit