PureBoard

Verfasst: **04.06.2005 22:33**

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

Verfasst: **04.06.2005 22:39**

Hm erkennt das Zyklen beliebiger länge?

Verfasst: **04.06.2005 22:41**

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.

Verfasst: **04.06.2005 22:51**

Genial einfach

Ist aber wohl nicht auf deinem Misst gewachsen

Verfasst: **04.06.2005 22:55**

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.

Verfasst: **10.07.2020 23:34**

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

PureBoard

Rho-Algorithmus

Rho-Algorithmus

Re: Rho-Algorithmus