3

最近我参加了一次采访，遇到了以下我无法弄清楚的问题。

问题一：

根据我阅读的证明，乌龟一次移动 1 步，而野兔一次移动 2 步。我明白这一点，因为野兔的移动速度是乌龟的两倍，他们会在某个时候相遇。他们不能有任何随机值，比如 2 和 3 或 3 和 5 或 2 和 4。如果是这样，他们会弄清楚循环吗？选择 Tortoise 和 Hare 值的条件是什么？我们可以选择任何随机值吗？

问题2：

龟兔赛跑有没有条件进入循环？假设 Tortoise 和 Hare 是否具有以下值，分别为 2 和 4。而链表就像

            3   
          /   \
    1 -  2     4
          \   /
            5

如果乌龟在节点 3 处进入循环，而野兔在节点 2 处进入循环，那么它们在循环内永远不会相遇。那么龟兔赛跑有没有条件进入循环呢？

是否应该选择任何限制值以使它们彼此相遇？

4

3 回答 3

3

RE Q1：龟兔速度的最大公约数不能是循环长度的除数（除 1 之外）。因此，例如 if gcd(vTortoise, vHare)=2，它将检测奇数长度的循环，但对于偶数长度的循环可能会失败。Q2 与失败的情况有关。

RE Q2：当上述限制不成立时检测循环，即当循环长度被 整除时M = gcd(vTortoise, vHare)，如果龟兔进入循环的位置与循环开始的模数不同，则不会检测到M循环。所以在上面的例子中，M=2如果兔子和乌龟都进入模数相等的位置，例如0和2、0和4、2和4、1和3等，将检测到循环。但不会检测到循环（因此乌龟和野兔将无限旅行）如果它们进入循环，例如在位置 0 和 1、或 0 和 3、1 和 2 等。

于 2016-02-03T08:38:01.647 回答
2

假设乌龟从编号点开始T并采取步骤 S t和野兔从点开始H并采取步骤 S h。

它们满足的充要条件是

|T-H| = k X gcd (S t , S h )

即他们起始位置的差异应该是gcd他们步数的倍数。

于 2016-02-03T08:39:24.547 回答
1

为了捕捉任何长度的循环，两者的移动速率必须相对较高。我认为这是一个充分条件。

于 2016-02-03T08:03:43.633 回答