循环检测算法：龟兔赛跑是否有进入循环的条件？
Cycle Detection Algorithm: Is there a condition for Tortoise and Hare to enter into cycle?
最近参加一个面试，遇到了下面这个问题，一直想不通
问题一：
根据我读到的证明，乌龟一次移动 1 步，兔子一次移动 2 步。我明白这一点，他们会在某个时候相遇，因为兔子的移动速度是乌龟的两倍。他们不能有任何随机值，例如 2 和 3 或 3 和 5 或 2 和 4。如果是这样，他们会找出循环吗？选择龟兔赛跑值的条件是什么？我们可以选择任何随机值吗？
问题2：
龟兔赛跑有什么条件可以进入循环吗？
假设 Tortoise 和 Hare 是否具有以下值分别为 2 和 4。链表就像
3
/ \
1 - 2 4
\ /
5
如果乌龟在节点 3 进入循环，而兔子在节点 2 进入循环，那么它们在循环内永远不会相遇。那么龟兔赛跑是否有进入循环的条件呢？
是否应该选择任何限制值以使它们彼此相遇？
两者的运动速率必须互质，才能捕捉任何长度的周期。我认为这是一个充分条件。
RE Q1：龟兔速度的最大公约数不能是环路长度的约数（1除外）。所以例如如果 gcd(vTortoise, vHare)=2，它将检测奇数长度的循环，但对于偶数长度的循环可能会失败。 Q2涉及失败的情况。
RE Q2: 当上述限制条件不成立时检测循环，即当循环长度被M = gcd(vTortoise, vHare)整除时，如果龟兔在不同的位置进入循环，则不会检测到循环从循环开始取模 M。所以在上面的例子中，如果兔子和乌龟都进入模数 M 相等的位置，则 M=2 和循环将被检测到，例如0和2，0和4，2和4，1和3，等等。但是如果他们进入循环，则不会检测到循环（因此龟兔会无限旅行）例如在位置 0 和 1，或 0 和 3、1 和 2 等
假设乌龟从编号 T 开始并采取步骤 St 并且兔子从 H 开始并采取步骤 Sh .
他们满足的充要条件是
|T - H| = k X gcd (St , Sh)
即他们起始位置的差异应该是他们步数 gcd 的倍数。
最近参加一个面试，遇到了下面这个问题，一直想不通
问题一：
根据我读到的证明，乌龟一次移动 1 步，兔子一次移动 2 步。我明白这一点，他们会在某个时候相遇，因为兔子的移动速度是乌龟的两倍。他们不能有任何随机值，例如 2 和 3 或 3 和 5 或 2 和 4。如果是这样，他们会找出循环吗？选择龟兔赛跑值的条件是什么？我们可以选择任何随机值吗？
问题2：
龟兔赛跑有什么条件可以进入循环吗？ 假设 Tortoise 和 Hare 是否具有以下值分别为 2 和 4。链表就像
3 / \ 1 - 2 4 \ / 5
如果乌龟在节点 3 进入循环，而兔子在节点 2 进入循环，那么它们在循环内永远不会相遇。那么龟兔赛跑是否有进入循环的条件呢？
是否应该选择任何限制值以使它们彼此相遇？
两者的运动速率必须互质，才能捕捉任何长度的周期。我认为这是一个充分条件。
RE Q1：龟兔速度的最大公约数不能是环路长度的约数（1除外）。所以例如如果 gcd(vTortoise, vHare)=2，它将检测奇数长度的循环，但对于偶数长度的循环可能会失败。 Q2涉及失败的情况。
RE Q2: 当上述限制条件不成立时检测循环，即当循环长度被M = gcd(vTortoise, vHare)整除时，如果龟兔在不同的位置进入循环，则不会检测到循环从循环开始取模 M。所以在上面的例子中，如果兔子和乌龟都进入模数 M 相等的位置，则 M=2 和循环将被检测到，例如0和2，0和4，2和4，1和3，等等。但是如果他们进入循环，则不会检测到循环（因此龟兔会无限旅行）例如在位置 0 和 1，或 0 和 3、1 和 2 等
假设乌龟从编号 T 开始并采取步骤 St 并且兔子从 H 开始并采取步骤 Sh .
他们满足的充要条件是
|T - H| = k X gcd (St , Sh)
即他们起始位置的差异应该是他们步数 gcd 的倍数。