GEHNIO
Gesamtschule Duisburg-Hamborn/Neumühl
Informatik in der Oberstufe

> Home
> Algorithmen
> Datenstrukturen
> Probleme
> Highlights
> Themen
> Mindmaps
> Aufgaben
> Programmierung
> Facharbeit
> Abitur
> Projekte
> Informatik-AG
> News
> Impressum
> email

Ein offenes Problem: Die Ulam-Folge

Die Ulam-Folge beginnt mit einer beliebigen natürlichen Zahl a. Ist a gerade, so erhält man die nächste Zahl b durch Halbierung; ist a ungerade, so erhält man b dadurch, dass man a verdreifacht und 1 hinzuaddiert. Die Folge endet, wenn ein Glied den Wert 1 hat.

Es gilt also:

Eingabe: Startwert uÎ N

Ausgabe: Glieder unÎ N , nÎ N der Ulam-Folge

un+1 = un/2, falls un gerade

un+1 = 3un + 1, falls un ungerade und un ¹ 1

Die Folge endet, wenn un = 1 ist.

 

Aufgabe1:

Berechnen Sie die Ulam-Folge mit den Startwerten 3, 5 und 23. Was beobachten Sieu dabei?

 

Es stellt sich die Frage, ob die Ulam-Folge für alle natürlichen Zahlen als Startwert endlich ist. Man vermutet, daß dies tatsächlich so ist, da bis heute kein Startwert bekannt ist, für den die Folge nicht endlich ist.

Ein Beweis ist den Mathematikern aber bisher noch nicht gelungen (Stand 1989). Die Ulam-Folge gehört deshalb zu den sogenannten "offenen Problemen".

Aufgabe 2:

Gib einen Algorithmus an, der zu einem beliebigen Startwert alle Glieder der Ulam-Folge berechnet und ausgibt.


Algorithmus: Ulam-Folge iterativ:

Beschreibung der Objekte: Startzahl und Folgenglieder: positive ganze Zahlen

Algorithmus:

Eingabe der Startzahl.

Wiederhole

Falls der Wert von Zahl (beim ersten Mal Startzahl) gerade ist,
dann setze NeueZahl := Zahl DIV 2,
sonst setze NeueZahl := 3 * Zahl + 1

Gib die NeueZahl aus.

Setzte Zahl := NeueZahl.

bis NeueZahl = 1.

PASCAL-Programm:

PROGRAM ulam_foge;
VAR zahl : integer;
BEGIN write ('Gib den Startwert an : ');
readln (zahl);
writeln (zahl,' ');
REPEAT IF zahl MOD 2 = 0
THEN zahl := zahl DIV 2
ELSE zahl := 3 * zahl + 1;
write (zahl,' ');
UNTIL zahl = 1;
END.

Algorithmus: Ulam-Folge rekursiv:

Falls n gerade ist: Wende Ulams Verfahren auf n/2 an.

Fall n ungerade ist:

Falls n¹1: Wende Ulams Verfahren auf 3n +1 an.

Falls n=1: Beende das Verfahren mit dem Wert 1.

PASCAL-Programm:

PROGRAM ULAM_FOLGE_REKURSIV;
USES Crt;
VAR zahl : integer;

FUNCTION ulam (u:integer):integer;
BEGIN
Write (u,' '); {hier wird der Startwert der Funktion ulam ausgegeben};
IF NOT odd(u) {u ist gerade}

THEN ulam := ulam(u DIV 2)
ELSE {u ist ungerade}
IF u<>1
THEN ulam := ulam (3*u+1)
ELSE ulam := 1
END;

BEGIN {Hauptprogramm}
Write ('Bitte Startwert eingeben: ');
Readln (zahl);
Writeln (ulam(zahl));
REPEAT {tue nichts} UNTIL keypressed;
END.

Anmerkungen: Entfällt die erste Anweisung der Funktion ulam, so wird der jeweilige Wert des Funktionsaufrufs nicht ausgegeben. Dadurch wird nicht die ganze Ulam-Folge ausgegeben, sondern nur der letzte Funktionswert (d.h. die "1", wenn die Ulan-Folge gegen 1 läuft).

Obwohl wir nicht wissen, ob diese Funktion für jede natürliche Zahl als Wert eines aktuellen Parameters einen Funktionswert liefert, ist die Deklaration natürlich durchaus zulässig. Die wie angegeben deklarierte Funktion darf in einem Programm für beliebige zu den formalen Parametern passende aktuelle Parameter aufgerufen werden. Es ist jedoch die (zumindest theoretische) Möglichkeit nicht auszuschließen, daß ein Aufruf der Funktion ulam für bestimmte natürliche Zahlen als Argumente eine nicht abbrechende Folge von rekursiven Aufrufen in Gang setzt.

Dies ist zugleich ein Beispiel für den Fall, daß eine formal zulässige Funktionsdeklaration nicht auch inhaltlich vernünftig sein muß: Man sollte sich stets vergewissern, ob der durch eine Funktionsdeklaration beschriebene Berechnungsprozeß für beliebige Argumente schließlich abbricht, also auch für solche, an die man vielleicht zunächst nicht gedacht hat.

Zurück zur Hauptseite

 

 

 

 

 

 

 

 

  © 2001 Gesamtschule Duisburg-Hamborn/Neumühl.  
Hosted by www.Geocities.ws

1