龟兔赛跑算法

Ra1*_*den 4 algorithm

我正在阅读wikipedia 中的Tortoise and Hare 算法。我想知道python伪代码是否有误。数组似乎失败了:[1, 2, 2, 3, 4, 5, 6, 7, 8, 9, ....]在最开始时,两个值相遇,算法继续寻找注定失败的循环的开始。
我知道有条件i ? ?,是否应该将此约束添加到代码中以找到循环的开始?
如果添加此约束,算法是否应该终止并在失败时返回未找到的循环,还是继续进行另一次迭代?因为如果输入是[1, 2, 2, 3, 4, 5, 3, 4, 5, 3, 4, 5, ....]
这个算法如何保证在第一个交汇点,两个指针都在一些循环内?

pax*_*blo 8

龟兔赛跑算法运行两个指针,一个在 offset i,另一个在 offset 2i,两者都是基于一个的,所以最初12,旨在检测链表样式数据结构中的循环。

而且,为了清楚起见,它比较的是指针而不是它们指向的数据值,我不确定你是否理解,如果你没有理解,我只是想我会提到它。

最初的起点是将乌龟放在第一个元素上,将兔子放在第二个元素上(假设它们当然存在 - 如果它们不存在,则不可能有循环),因此声明它们在第一个元素上相等是不正确的开始。只有当兔子循环并因此从后面抓住乌龟时,指针值才会变得相等。