谁能用布伦特的周期检测算法来帮助我。我不完全理解为什么“搜索两个大于λ和μ的2 ^ i的最小幂”？ 2的幂如何在周期的检测中发挥作用。它与Floyd的循环检测算法有某种关系吗？我无法从基础上得到它。请帮忙 !
最佳答案
此方法使用增加的步骤(1、2、4、8 ...)尽快进入循环内部。当P = 2 ^ k大于λ和μ时，乌龟(T)就在回路中，而野兔(H)只需要P步就能再次遇到(站立)乌龟。似乎有些模拟会很有用。让我们列出0-1-2-3-4-5-6-7-3
P=1 T=0 H=0; H makes 1 step and doesn't meet T
P=2 T=1 H=1; H makes 2 steps and doesn't meet T
P=4 T=3 H=3; H makes 4 steps and doesn't meet T
P=8 T=7 H=7; H makes 5 steps and meets T !!!!!
注意:在P = 4的情况下，T处于循环内，但野兔并未经历整个周期(P> =μ但P
因此我们发现μ
T=0 H=0; H makes 5 steps; H=5
while T <> H
move both
T=1 H=6
T=2 H=7
T=3 H=3 !!!!!!!
我们刚刚发现μ= 3