Kann mir bitte jemand helfen mit Brent Zyklus Erkennung Algorithmus. Ich verstehe nicht genau, warum "suche nach der kleinsten Potenz von zwei 2^i, die größer ist als sowohl λ als auch μ"? Wie Potenzen von 2 spielen Rolle bei der Erkennung von Zyklus. Ist es irgendwie mit Floyds Zyklus-Erkennungsalgorithmus verwandt? Ich bin nicht in der Lage, es von den Grundlagen zu bekommen. Bitte helfen Sie!Brent Zyklus Erkennung Algorithmus
Diese Methode verwendet zunehmende Schritte (1, 2, 4, 8 ...), um so schnell wie möglich in die Schleife zu gelangen. Wenn P = 2^k wird größer als sowohl λ als auch μ, dann ist Schildkröte (T) in der Schleife, und Hase (H) macht nicht mehr als P Schritte, um wieder zu Schildkröten zu treffen. Es scheint, dass eine Simulation nützlich wäre. Lassen Sie uns haben wir die Liste 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 !!!!!
Hinweis: Mit P = 4 T innerhalb der Schleife, aber Hase nicht durch den ganzen Zyklus geht (P> = μ, aber P < λ)
Wir haben also μ < 8 und λ = 5 gefunden. Dann wollen wir μ (Loop Einstiegspunkt)
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 !!!!!!!
Wir haben gerade μ = 3
Danke ... das hat viel geholfen :) – SlashGeek
Können Sie erklären, warum "Zweierpotenzen" hier verwendet werden? Wenn wir so schnell wie möglich versuchen, Hasen in die Schleife zu bekommen, warum verwenden wir nicht "Potenzen von 3" oder "Potenzen von 5"? Wenn "Potenzen von 5" verwendet werden, wird dieser Algorithmus noch gültig sein? Schließlich, warum ist λ gleich der Anzahl der letzten Schritte, die Hasen gemacht haben, bevor man Schildkröte trifft? Welchen Beweis müssen wir diese Zahl als die Länge des Zyklus nehmen? Vielen Dank. – carawan
@carawan, Ich denke, Power-of-3 und Power-of-5 funktionieren auch, obwohl ich keinen Beweis habe. Ich habe ein paar einfache Tests gemacht.
Wenn sich der langsamere Iterator überhaupt nicht bewegt, ist der Algorithmus fehlerhaft, weil der langsamere Iterator außerhalb der Schleife liegen könnte.
Wenn der langsamere Iterator den schnelleren Iterator tailgt und die folgende Distanz immer unter einer festen Grenze liegt (wie 99), dann ist der Algorithmus defekt, da die Schleifengröße 99 überschreiten könnte. Wenn der folgende Abstand allmählich wächst, UND Anhänger bewegt sich, dann denke ich, dass sie sich irgendwann treffen werden. –
@WillNess gefunden haben, finden, was diese mit Primzahlen zu tun? Ich denke, das Primes-Tag sollte entfernt werden. – gsingh2011
@ gsingh2011 es ist in Primfaktorzerlegung Algorithmus verwendet. vielleicht sollte ein Primfaktor-Faktor-Tag hinzugefügt werden/ersetzen Sie die Primzahlen ... :) –