Kennt einer obiges Problem? Wenn eine Zahl n gerade ist, wird sie durch 2 geteilt, solange bis sie ungerade ist. Dann wird sie mit 3 multipliziert, und 1 addiert. Irgendwann ist n = 1.
In Pseudo - Code notiert sieht das Ganze so aus:
Eingabe(n)
wiederhole
wenn n ungerade dann n:=(3*n)+1
sonst n:=n div 2;
solange bis n=1;
Das Ganze nennt sich Ulamsche Vermutung. Vermutet wird, das der Algorithmus für jeden Startwert irgendwann zur Eins zurückkehrt, und damit die Schleife terminiert. Soweit ich weiß, ist es noch nicht gelungen, diese Vermutung zu beweisen. Mit empirischen Untersuchungen konnte aber auch kein Gegenbeispiel gefunden werden. Es gibt also noch room for improvement :-)
Interessant ist folgendes: Wird über den natürlichen Zahlen die Anzahl der Schritte aufgetragen, die man braucht, um diese Zahl mit dem Algo auf eins "herunterzurechnen", ergibt sich ein sehr ungleichmäßiges (chaotisches?) Bild.
Ralf Wiebicke @ 2:249/3090.5
Erstellt von Ralf Wiebicke, letzte Änderung
27.03.97