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.
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
Anda dapat membuat fungsi sendiri f(x) = (A*x2 + B*x + C) % M di sini.
- Acak: Fungsi yang digunakan adalah f(x) = (x2 - 1) % M dan hanya M dan x0 yang diambil secara acak.
- 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 x0 (nilai diantara 0 hingga M-1).
Anda juga dapat mengeset nilai x0 anda sendiri, yang harus berada dalam ∈ [0..M-1].
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
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.
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
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).
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
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)).
Kita mengembalikan kelinci kembali ke x0 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 μ.
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 λ.
Anda dapat menggunakan/memodifikasi kode implementasi algoritma Floyd Cycle-Finding kami:
UVa00350.cpp
UVa00350.java
UVa00350.py
UVa00350.ml
You have reached the last slide. Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.
Acak
Custom(a, b, c, m, z0)