While-Programm für 3n+1

Aufrufe: 123     Aktiv: 29.08.2021 um 22:05

0

Hallo

Habe Hausaufgaben zu Turingmaschinen zum lösen erhalten.

Die Theorie habe ich dazu gelesen, allerdings bei der untenstehenden Aufgabe habe ich bereits Probleme

Hier die Aufgabe:

"Collatz-Problem oder 3n+1 Problem --> Link: https://de.wikipedia.org/wiki/Collatz-Problem

Für eine natürliche Zahl n≥1 ist eine Collatz-Folge (ak)k∈N wie folgt definiert:

a0=n Ist ak gerade, so gilt ak+1=ak / 2 Ist ak ungerade, so gilt ak+1=3n+1 Die Collatz-Folge für 11 lautet 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, … Es ist offensichtlich, dass sobald einmal eine 1 in einer Collatz-Folge vorkommt, dass dann die Folge periodisch wird und «1, 4, 2» immer wiederholt wird.

Die Collatz-Vermutung besagt, dass für jeden Anfangswert n die Folge schließlich ein Folgeglied hat, das 1 wird.

Die Funktion c(n) bestimme das kleinste k, so dass in der Collatz-Folge für n gilt, dass ak=1.

Es gilt also z.B. c(11)=14.

Schreiben Sie ein While-Programm für c(n).

Sie dürfen in Ihrem Programm nebst den Standard-Konstrukten der While-Programme auch IF-Anweisungen und Operationen für Multiplikation, ganzzahlige Division und Divisionsrest verwenden; man kann zeigen, dass das die Ausdruckskraft der While-Programme nicht verändert."

Es ist mir unklar, wie ich dazu vorgehen muss. Wenn ich mir Videos/Tutorials zu Turingmaschinen anschaue, dann scheint mir alles plausibel usw, allerdings, keine Ahnung wie ich vorgehen muss.

Danke für die Hilfestellung

Freundliche Grüsse

Diese Frage melden
gefragt

Punkte: 10

 
Kommentar schreiben
0 Antworten