假设你有一个函数 f: S → S 和任何初始值 x0 ∈ S
(在这个可视化中,我们限制为 f(x) = (A*x^2 + B*x + C) % M 和 x0 % M,因此函数 f 的定义域和值域 ∈ [0..M-1])。
迭代函数值的序列:
{x0, x1 = f(x0), x2 = f(x1), ..., xi = f(xi-1), ...}
必须最终使用两次相同的值(循环),即 a ≠ b 使得 xa = xb。
之后,序列必须通过重复从 xa 到 xb-1 的值的循环来继续。
设 mu (μ) 是最小的索引,设 lambda (λ)(循环长度)是最小的正整数,使得 xμ = xμ+λ。
寻找循环问题:给定 f 和 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.
您可以在此处定义自定义函数 f(x) = (A*x2 + B*x + C) % M。
- 随机:函数将为 f(x) = (x2 - 1) % M,只有 M 和 x0 是随机生成的。
- 自定义:您可以指定 f(x) 的系数 A、B、C(范围从 -999 到 999),模数值 M(范围从 10 到 1000)和初始值 x0(范围从 0 到 M-1)。
您还可以设置自定义 x0,必须 ∈ [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.
Floyd的乌龟-兔子循环查找是一种可以在时间和空间复杂度上都能有效解决这个问题的算法。
它只需要O(μ+λ)的时间和O(1)的空间就能完成任务。
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.
这是 Floyd's Tortoise-Hare Cycle-Finding 算法的可视化。
由f(x)和x0定义的迭代函数值序列的rho (ρ)形状,很好地可视化了μ和λ。
VisuAlgo 使用绿色顶点代表乌龟 (t)和橙色顶点代表兔子 (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.
我们从 x0 开始。
当 乌龟的指针 != 兔子的指针 时,我们通过调用 f(乌龟)/f(f(兔子)) 将 乌龟/兔子 向前推进一步/两步到他们的下一个值。
我们将 hare 重置回 x0,并保持 tortoise 在其当前位置。
然后,我们将两个指针迭代地向前移动一步,因为这样可以保持 tortoise 和 hare 的间隔为 kλ。
两个指针第一次相等时,就告诉我们 μ 的值。
再次,我们让乌龟保持在其当前位置,并将兔子设置在它旁边。
然后,我们通过一步一步地将兔子移动到下一个值。
两个指针第一次相等告诉我们λ的值。
我们将扩展此讲座的幻灯片,以便稍后加入更多有关此算法的信息
您可以使用/修改我们的Floyd Cycle-Finding Algorithm实现代码:
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.
随机
Custom(a, b, c, m, z0)