为什么Floyd的循环查找算法在某些指针增量速度下失败？ [英] Why does Floyd's cycle finding algorithm fail for certain pointer increment speeds?

问题描述

请考虑以下链接列表：

1->2->3->4->5->6->7->8->9->4->...->9->4.....

上面的列表具有如下循环：

The above list has a loop as follows:

[4->5->6->7->8->9->4]

在白板上绘制链表，我尝试针对不同的指针步骤手动解决它，以查看指针如何移动-

Drawing the linked list on a whiteboard, I tried manually solving it for different pointer steps, to see how the pointers move around -

（slow_pointer_increment，fast_pointer_increment）

因此，不同情况的指针如下：

So, the pointers for different cases are as follows:

(1,2), (2,3), (1,3)

前两对增量-（1,2）和（2,3）正常工作，但是当我使用（1,3）对时，算法似乎没有在这对上工作。对于我需要搜索多少步数以使该算法成立，是否存在规则？

The first two pairs of increments - (1,2) and (2,3) worked fine, but when I use the pair (1,3), the algorithm does not seem to work on this pair. Is there a rule as to by how much we need to increment the steps for this algorithm to hold true?

尽管我搜索了越来越慢的各种递增步长指针，到目前为止，我还没有找到一个相关的答案，说明为什么它不能为列表中的增量（1,3）工作。

Although I searched for various increment steps for the slower and the faster pointer, I haven't so far found a single relevant answer as to why it is not working for the increment (1,3) on this list.

推荐答案

仅当指针增量与周期长度之间的差为互质数时（即，它们的最大公约数必须为1），才能保证算法在任意位置找到一个周期。

The algorithm is only guaranteed to find a cycle at any position if the difference between the pointer increments and the cycle length are coprimes (i.e. their greatest common divisor must be 1).

对于一般情况，这意味着增量之间的差必须为1（因为这是与所有其他正整数互质的唯一正整数）。

For the general case, this means the difference between the increments must be 1 (because that's the only positive integer that's coprime to all other positive integers).

对于（1,3），差异为 3-1 = 2 ，周期长度是 2 ， 2 和 2 不是互素的，因此不能保证算法无法找到循环。

For (1,3), the difference is 3-1=2, and the cycle length is 2, 2 and 2 are not coprimes, thus the algorithm is not guaranteed to find the cycle.

理解这一点的关键在于，至少出于检查指针是否相遇的目的，慢速指针和快速指针在周期内的位置仅相对彼此有关。也就是说，这两个可以视为等效：（两者之差均为1）

The key to understanding this is that, at least for the purposes of checking whether the pointers ever meet, the slow and fast pointers' positions within the cycle only matters relative to each other. That is, these two can be considered equivalent: (the difference is 1 for both)

slow fast             slow fast
   ↓ ↓                   ↓ ↓
 0→1→2→3→4→5→0     0→1→2→3→4→5→0

所以我们可以从慢保持不变而 fast 以 fastIncrement-slowIncrement 的增量移动，此时问题变为：

So we can think of this in terms of the position of slow remaining constant and fast moving at an increment of fastIncrement-slowIncrement, at which point the problem becomes:

从任何位置开始，我们能否以某个速度（模数循环长度）到达特定位置？

Starting at any position, can we reach a specific position moving at some speed (mod cycle length)?

或者，或更笼统地说：

我们可以到达每个以一定速度（模周期长度）移动的位置吗？

Can we reach every position moving at some speed (mod cycle length)?

仅当速度和循环长度为互质时，才为真。

Which will only be true if the speed and cycle length are coprimes.

例如速度为4，长度为6的循环-从0开始，我们访问：

0，4，8％6 = 2，6％ 6 = 0，4，2，0，... -GCD（4,6）= 2，我们只能访问第二个元素。

在动作，请考虑上面示例中的（1,5）增量（差= 4），并观察指针永远不会相遇。

For example, look at a speed of 4 and a cycle of length 6 - starting at 0, we visit:
0, 4, 8%6=2, 6%6=0, 4, 2, 0, ... - GCD(4,6) = 2, and we can only visit every second element.
To see this in action, consider increments of (1,5) (difference = 4) for the example given above and see that the pointers will never meet.

我应该注意，至少就我所知，（1,2）增量被认为是算法的基本部分。

I should note that, to my knowledge at least, the (1,2) increment is considered a fundamental part of the algorithm.

使用不同的增量（按照上述约束）可能会起作用，但这将与正式算法相去甚远，并且会涉及更多工作（由于指向链表的指针必须迭代地递增，因此您不能将其递增更多）单步执行大于1的操作），在一般情况下没有明显的优势。

Using different increments (as per the above constraints) might work, but it would be a move away from the "official" algorithm and would involve more work (since a pointer to a linked-list must be incremented iteratively, you can't increment it by more than 1 in a single step) without any clear advantage for the general case.

这篇关于为什么Floyd的循环查找算法在某些指针增量速度下失败？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！