布倫特週期檢測算法

任何人都可以請布倫特週期檢測算法幫助我。我不明白爲什麼「尋找比λ和μ都大的兩個2^i的最小冪」？ 2的權力如何在循環檢測中發揮作用。它與弗洛伊德的週期檢測算法有什麼關係？我無法從基礎知識中獲得它。請幫忙！布倫特週期檢測算法

2012-05-29 SlashGeek

@WillNess這是什麼都與素數呢？我認爲素數標籤應該被刪除。 – gsingh2011

@ gsingh2011它用於素分解算法。也許素數分解標籤應該被添加/替換質數... :) –

此方法使用增加步驟（1，2，4，8 ...）儘快在循環內得到的。當P = 2^k變得大於λ和μ時，龜（T）在循環中，並且兔子（H）不超過P個步驟再次與（站立）龜相遇。似乎有些模擬會很有用。讓我們有列表0-1-2-3-4-5-6-7-3

P=1 T=0 H=0; H makes 1 step and doesn't meet T 
P=2 T=1 H=1; H makes 2 steps and doesn't meet T 
P=4 T=3 H=3; H makes 4 steps and doesn't meet T 
P=8 T=7 H=7; H makes 5 steps and meets T !!!!!

注意：隨着P = 4，T是內循環，但野兔不經過整個週期（P> =μ但是P<λ）

所以我們發現了μ< 8和λ= 5。然後，我們希望找到μ（環入口點）

T=0 H=0; H makes 5 steps; H=5 
while T <> H 
    move both 
T=1 H=6 
T=2 H=7 
T=3 H=3 !!!!!!!

我們剛剛發現μ= 3

來源

2012-05-29 12:47:28 MBo

Thanx ...那幫了很多:) – SlashGeek

你能解釋爲什麼這裏使用「兩個冪」？如果我們的目標是儘快讓兔子進入圈內，爲什麼不使用「3的冪」或「5的冪」？如果使用「5的冪」，該算法是否仍然有效？最後，爲什麼λ等於在遇到烏龜之前做的最後一步兔子的數量？我們必須把這個數字作爲循環的長度來證明什麼？謝謝。 – carawan

@carawan，我猜想3的權力和5的權力也工作，雖然我沒有證據。我做了一些簡單的測試。
如果較慢的迭代器根本沒有移動，那麼該算法會被破壞，因爲較慢的迭代器可能在循環之外。
如果較慢迭代後擋板越快迭代和下面的距離總是始終低於固定限制（如99），則該算法被打破，因爲環的大小可以超過99
如果下面的距離逐漸增大，以及追隨者確實移動，那麼我認爲他們最終會見面。 –

布倫特週期檢測算法

回答

相關問題