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)).