Masalah Pencarian Siklus

1. Introduction

Misalkan anda memiliki sebuah fungsi f: S → S dan nilai awal apapun x₀ ∈ S
(dalam visualisasi ini, kita terbatas ke f(x) = (A*x^2 + B*x + C) % M dan x₀ % M maka fungsi f memiliki domain dan range ∈ [0..M-1]).

Barisan dari nilai-nilai fungsi iterasi:
{x₀, x₁ = f(x₀), x₂ = f(x₁), ..., x_i = f(x_i-1), ...}
harus pada akhirnya menggunakan nilai yang sama dua kali (siklus), yaitu a ≠ b dimana x_a = x_b.
Sejak saat itu, barisan tersebut akan berlanjut dengan mengulang nilai-nilai siklus dari x_a ke x_b-1.

Biarkan mu (μ) menjadi indeks terkecil dan biarkan lambda (λ) (panjang siklus) menjadi bilangan bulat positif terkecil dimana x_μ = x_μ+λ.

Masalah pencarian-siklus: Temukan μ dan λ, diberikan f dan x₀.

2. Masukan Sendiri

Anda dapat membuat fungsi sendiri f(x) = (A*x² + B*x + C) % M di sini.

1. Acak: Fungsi yang digunakan adalah f(x) = (x² - 1) % M dan hanya M dan x₀ yang diambil secara acak.
2. Unik: Anda dapat menyediakan koefisien A, B, C dari f(x) (nilai diantara -999 hingga 999), nilai modulo M (nilai diantara 10 hingga 1000) dan nilai awal x₀ (nilai diantara 0 hingga M-1).

Anda juga dapat mengeset nilai x₀ anda sendiri, yang harus berada dalam ∈ [0..M-1].

3. Algoritma Floyd Kelinci-Penyu

Pencarian-Siklus Penyu-Kelinci oleh Floyd adalah salah satu algoritma yang dapat menyelesaikan masalah ini secara efisien baik dari segi kompleksitas waktu dan ruang.

Algoritma ini hanya membutuhkan waktu O(μ+λ) dan ruang O(1) untuk melakukan tugasnya.

3-1. Visualisasinya

Ini adalah visualisasi dari algoritma Pencarian-Siklus Penyu-Kelinci oleh Floyd.

Bentuk dari rho (ρ) dari barisan nilai-nilai fungsi iterasi yang didefinisikan oleh f(x) dan x₀ secara jelas memvisualisasikan μ dan λ.

VisuAlgo menggunakan simpul-simpul hijau untuk merepresentasikan penyu (t) dan simpul-simpul oranye untuk merepresentasikan kelinci (h).

3-2. Mencari kλ (kelipatan dari λ)

Kita mulai dari x₀.

Ketika penunjuk penyu != penunjuk kelinci, kita memajukan penyu/kelinci sebesar satu langkah/dua langkah ke nilai-nilai mereka yang berikutnya dengan memanggil f(penyu)/f(f(kelinci)).

3-3. Mencari μ (awal dari siklus)

Kita mengembalikan kelinci kembali ke x₀ dan membiarkan penyu berada di posisinya yang sekarang.

Lalu, kita secara iteratif memajukan kedua penunjuk ke nilai-nilai mereka yang berikutnya sebesar satu langkah karena ini menjaga gap dari penyu dan kelinci sebesar kλ.

Pertama kalinya kedua penujuk sama memberitahukan kita nilai dari μ.

3-4. Mencari λ (panjang dari siklus)

Sekali lagi, kita biarkan penyu berada tetap pada posisinya dan set kelinci tepat disebelahnya.

Lalu, kita secara iteratif memindahkan kelinci ke nilai berikutnya sebesar satu langkah.

Pertama kalinya kedua penunjuk sama memberitahukan kita nilai dari λ.

4. Cobalah Animasinya

5. Implementasi

Anda dapat menggunakan/memodifikasi kode implementasi algoritma Floyd Cycle-Finding kami:
UVa00350.cpp
UVa00350.java
UVa00350.py
UVa00350.ml