Алгоритм обнаружения цикла Флойда: почему черепаха делает не более одного круга?

Question

Почему алгоритм обнаружения цикла Флойд предполагает, что черепаха сделает максимум один круг вокруг цикла, прежде чем встретится с зайцем? Почему он не может сделать несколько кругов? И интуитивное, и формальное объяснение будет с благодарностью.

Answer 1

Я думаю, что могу дать интуитивное объяснение.

У нас может быть два случая: либо есть цикл, либо нет.

Если цикла нет: hare дойдет до конца списка раньше, чем tortoise, и мы закончим.

Если есть цикл: Он должен иметь длину n, и мы помним, что «скорость» hare в два раза больше, чем tortoise's. Как только tortoise входит в l oop, hare находится где-то в цикле (возможно, уже обошел его несколько раз). В любом случае, это x узлов позади tortoise (помните, что x <= n-1, потому что если бы они были на одном узле, мы бы закончили здесь). Поскольку «скорость» hare в два раза выше, чем у tortoise, он «догонит» ее за x «шагов». EQD.