Programmierübungen zur Collatz-Folge

Die Collatz-Folge ist eine interessante Folge. Gewöhnlich erreicht sie irgendwann den Wert 1, aber es ist nicht bewiesen, dass dies in jedem Fall so ist.

 

Die folgenden zehn Aufgaben mit steigender Schwierigkeit beziehen sich alle auf die Collatz-Folge. Die ersten Aufgaben können Sie schon bald nach Beginn eines Programmierkurses lösen, die letzten am Ende eines einsemestrigen Kurses.

 

Ab Mitte des Sommersemesters 2011 werde ich nacheinander auch die Lösungen dazu einstellen.

 

 

 

Die Folge beginnt mit einer beliebigen natürlichen Zahl a0. Für die folgenden Glieder der Folge gilt:

                ai+1   =                   ai / 2                      falls ai eine gerade Zahl ist

                                              3 ai  + 1                 falls ai eine ungerade Zahl ist

 

Gewöhnlich lässt man die Folge mit der ersten auftretenden 1 enden. Für die Startzahl 6 ergibt sich demnach die Folge

6, 3, 10, 5, 16, 8, 4, 2, 1

Lässt man die Folge weiterlaufen, so wird sie nach der ersten 1 periodisch:

6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, ...

Bei den folgenden Aufgaben ist jeweils angegeben, wenn die Folge mit der ersten 1 enden soll.

 

 

Aufgaben

  1. Schreiben Sie eine Funktion, welche für ein beliebiges Element der Folge das darauf folgende Element liefert. Testen Sie die Funktion aus einem Tabellenblatt heraus und mit Hilfe einer selbst geschriebenen Prozedur.
  2. wie bei 1, mit dem Unterschied, dass die Funktion nun nicht den Wert des Folgeelements liefern soll, sondern feststellen soll, ob dieses eine gerade Zahl ist.
  3. Schreiben Sie eine Funktion, welche das n-te Element der Folge liefert. Das Anfangselement wird dabei mitgezählt. (Anmerkung: die Folge soll dabei über eine eventuell auftretende 1 hinaus fortgesetzt werden)
  4. Erfahrungsgemäß erreicht die Folge irgendwann den Wert 1. Schreiben Sie eine Funktion, welche für den Anfangswert z feststellt, beim wievielten Glied die 1 erreicht wird. Das Anfangsglied soll mitgezählt werden.
  5. Schreiben Sie eine Funktion, welche die Folge, vom Anfangswert bis zur ersten auftretenden 1, als Array liefert.
  6. wie 5, mit dem Unterschied, dass die Indexuntergrenze des zu liefernden Arrays variabel ist, d.h. der Funktion als Parameter übergeben wird.
  7. wie bei 6, mit dem Unterschied, dass der Parameter, der die Indexuntergrenze enthält, optional ist. Standardwert: 1
  8. Schreiben Sie eine Funktion, welche für zwei Anfangswerte z1 und z2 ermittelt, welcher die längere Collatz-Folge ergibt. Annahme: die Folge endet jeweils bei der ersten auftretenden 1.
  9. Schreiben Sie eine Funktion, welche für einen Anfangswert z ermittelt, ob die sich daraus ergebende Folge mehr gerade als ungerade Elemente enthält. Annahme: Die Folge endet bei der ersten auftretenden 1.
  10. Schreiben Sie eine Funktion, die für eine Liste von Anfangswerten (eindimensionales Array) die Collatz-Folgen, jeweils einschließlich der ersten auftretenden 1, in Form eines verzweigten Arrays (ein Array von Arrays) liefert.

 

Aufgaben zur Collatz-Folge
Hier noch die Aufgabenstellung zum Herunterladen
AufgCollatzx.pdf
Adobe Acrobat Dokument [39.7 KB]
Download