這不是使用Hare和Tortoise方法在鏈接列表中檢測循環的問題。鏈接列表中的循環檢測：窮舉理論
在野兔&烏龜方法我們有指針以1x和2x速度運行，以確定它們符合，我相信它的最有效的方式和該類型的搜索的順序是O（n）。
問題是我必須拿出一個證明（證明或反駁），當移動速度是Ax（A倍x）和Bx（B倍x）和A不等於B.其中A和B是在具有循環存在的鏈表上運行的兩個隨機整數。
這是在我最近參加的一次採訪中提到的，我無法全面證明自己是否有上述可能。任何幫助讚賞。
假設有一個循環，比如長度爲L。
容易出現的情況第一
爲了方便，首先考慮的情況下兩個粒子在同一時間整個循環。無論何時n*A = n*B (mod L)對於某個正整數n，這些粒子都處於相同位置，這是直到它們再次相遇的步數。以n=L給出一個解決方案（儘管可能有一個更小的解決方案）。因此，在L個單位時間之後，粒子A已使A周圍的行程回到開始位置，並且粒子B已使B周圍的行程返回到開始位置，在這裏他們愉快地發生碰撞。
一般情況
現在是什麼時，他們沒有在同一時間進入循環會發生什麼？假設A是較慢的粒子，即A<B，並且假設A在時間m進入循環，並且讓我們調用A進入循環0的位置（因爲它們在循環中，它們永遠不會離開它， m只是通過減去A*m來重新命名位置，距離A已經在m時間單位之後行進）。那麼，那時B已經在位置m*(B-A)（它在m時間單位之後的實際位置是B*m，因此它的重命名位置是B*m-A*m）。那麼我們需要證明有一段時間n這樣n*A = n*B+m*(B-A) (mod L)。也就是說，我們需要一個解決方案，以模塊化的方程
(n+m) * (A-B) = 0 (mod L)
以n = k*L-m爲k足夠k*L>m做的伎倆大，雖然再次，有可能是一個更小的解決方案。
因此，他們總是見面。
如果你的兩個步長有一個共同的因子x：假設步長是Ax和Bx，那麼考慮從原始序列中獲取的序列和每個第x個元素。當且僅當原始序列有效時，這個新序列纔有一個循環，並且在其上採取步長A和B相當於在原始序列上採用步長Ax和Bx。
這種降低意味着當A和B互相矛盾時，證明算法是有效的就足夠了。
該假設是錯誤的。例如，如果兩個指針都跳到一個偶數，那麼循環的大小也是一樣的，而指針之間的距離很奇怪，它們永遠不會相遇。
UPD這顯然是不可能的情況。由於這兩個指針始於同一點，它們之間的距離將始終是均勻的。
「這個新的序列有一個循環當且僅當原始序列」 - 這是錯誤的。 – 2011-12-17 08:38:45
@ n.m .:呃？對於鏈表來說，如果你逐步遍歷每個`x`項目，則循環返回的屬性不會改變。無論你是在兩種情況下（有一個循環）永遠踏着腳步，還是在'n`或`n/x`步驟（沒有循環）之後停下來。當然，如果原始週期的長度爲'k'，那麼週期長度不會是'k/x'......但這與論證無關。 – 6502 2011-12-17 08:48:47