週期檢測算法：龜和兔子是否有條件進入循環？

最近我參加了一個採訪，並討論了以下我無法弄清楚的問題。週期檢測算法：龜和兔子是否有條件進入循環？

問題-1：

按照我讀龜移動1步和野兔移動2步在時刻證明。我明白這一點，他們會在兔子以兩倍於烏龜的速度移動之後的某個時候見面。他們不能有任何像2和3或3和5或2和4這樣的隨機值。如果是這樣，他們是否會知道這個循環？選擇龜和野兔值的條件是什麼？我們可以選擇任何隨機值嗎？

問題2：

是否有烏龜和野兔進入循環的情況？假設如果烏龜和兔子有以下值說2和4分別。而鏈表是像

如果龜在循環節點3進入和野兔進入環路節點2然後他們都永不滿足對方的循環中。那麼龜龜和野兔是否有條件進入循環？

是否有任何限制值應該選擇，以便他們見面？

來源

2016-02-03 Amarnath

請詳細解釋一下_「龜龜和野兔的值是否只有1和2？他們不能有任何像2和3或3和5或2和4這樣的隨機值。」_應該是指。 – Codor

@Codor更新了問題，要點是「我們可以爲烏龜和野兔選擇任何數值，如果這樣他們將滿足進入循環的條件」 – Amarnath

RE Q1：烏龜和野兔速度的最大公約數不能是環路長度的除數（1除外）。所以例如如果是gcd(vTortoise, vHare)=2，它將檢測奇數長度的循環，但可能會出現偶數長度的循環失敗。 Q2涉及失敗的情況。

RE Q2：檢測一個循環時，上述限制不成立時，即當環長度是由M = gcd(vTortoise, vHare)整除，環不會被檢測到，如果烏龜和野兔進入循環在從一開始就用不同的模M位置的循環。所以在上面的例子中，如果兔子和烏龜都進入M模的相等位置，例如M=2和loop將被檢測到。 0和2，0和4,2和4,1和3等。但是，如果它們進入環路，則環路將不被檢測到（因此，龜和兔子將無限地移動），例如，在位置0和1，或0和3，圖1和2等

來源

2016-02-03 08:38:01

兩者的移動速率必須相對較高，才能捕捉任何長度的循環。我認爲這是一個充分的條件。

來源

2016-02-03 08:03:43 Sneftel

第二個問題呢？他們是否有條件進入循環？ – Amarnath

是的，這不知何故是有道理的，但相對原素與圖形無關，我認爲它是輸入的一部分。圖表是輸入的一部分還是固定的？ – Codor

@Codor它是固定的輸入。上面顯示的輸入是固定的。 – Amarnath

說龜開始在點編號T並採取步驟S1_噸和野兔開始在H並採取步驟S1 _ħ。

讓他們滿足的充分必要條件是

| T - H | = K X滿足gcd（S _噸，S _ħ）

即它們的起始位置應的它們的步驟gcd所述多個差值。

來源

2016-02-03 08:39:24

週期檢測算法：龜和兔子是否有條件進入循環？

回答

相關問題