Rho-Algorithmus

[remi_meier]

Noch ein ganz kleiner Beitrag.
Dieser Algorithmus ist extrem einfach und effizient zum erkennen von
Zyklen in Zahlenfolgen.

Code: Alles auswählen

; Rho-Algorithmus

Procedure.l F(x.l)
	If x & 1
		ProcedureReturn 3 * x + 1
	Else			
		ProcedureReturn x / 2
	EndIf	
EndProcedure


For z = 1 To 10
	z1 = z
	z2 = z	
	Debug "###"	
	Repeat
		z1 = F(z1)
		z2 = F(F(z2))
		Debug z1		
	Until z1 = z2 Or z2 = 1
Next

Das ist das 3n + 1 Problem, zum Testen, ob jede Zahl in einen Zyklus
gerät (hier sogar immer in 4, 2, 1).

greetz
Remi

[Norbie]

Hm erkennt das Zyklen beliebiger länge?

[remi_meier]

Jap, es geht manchmal einfach etwas länger. Ein Zähler (z2) läuft mit
doppelter Geschwindigkeit wie der normale Zähler (z1). Wenn beide in
den Zyklus geraten, kommt irgendwann z2 zum überrunden von z1,
überspringen kann er ihn jedoch nicht, deshalb sind die beiden Zähler
bei einem Zyklus irgendwann mal gleich.

[Norbie]

Genial einfach
Ist aber wohl nicht auf deinem Misst gewachsen

[remi_meier]

Ne, ich würde mich nie trauen einem Algorithmus selbst einen Namen zu
geben!
Ich habe gerade (im 2er-Team) vor ner Woche etwa einen Kreativpreis
bekommen, weil wir diesen Algorithmus verwendeten. Obwohl so simpel
ist er doch recht unbekannt.

[Jac de Lad]

https://de.wikipedia.org/wiki/Collatz-Problem