Кто-нибудь может помочь мне с алгоритмом обнаружения цикла Брента. Я не понимаю, почему "искать наименьшую степень двух 2 ^ i, которая больше, чем λ и μ"? Как полномочия 2 играют роль в обнаружении цикла. Это как-то связано с алгоритмом обнаружения цикла Флойда? Я не могу получить его из основ. Пожалуйста помоги!
Алгоритм обнаружения цикла Brent
Ответ 1
Этот метод использует все возможные шаги (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 < λ)
Итак, мы нашли μ < 8 и λ = 5. Затем мы хотим найти μ (точка входа петли)
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