Masalah Pencarian Siklus

1. Introduction

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


Barisan dari nilai-nilai fungsi iterasi:
{x0, x1 = f(x0), x2 = f(x1), ..., xi = f(xi-1), ...}
harus pada akhirnya menggunakan nilai yang sama dua kali (siklus), yaitu a ≠ b dimana xa = xb.
Sejak saat itu, barisan tersebut akan berlanjut dengan mengulang nilai-nilai siklus dari xa ke xb-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 x0.

2. Masukan Sendiri

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

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

Anda juga dapat mengeset nilai x0 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 x0 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 x0.


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