While-Programm für 3n+1

Aufrufe: 1148     Aktiv: 05.11.2021 um 21:12
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
1 Antwort
0

Code:

def collatz_sequence(x):
    num_seq = [x]
    if x < 1:
       return []
    while x > 1:
       if x % 2 == 0:
         x = x / 2
       else:
         x = 3 * x + 1
       num_seq.append(x)    
    return num_seq

print(collatz_sequence(n)) # n durch eine beliebige Zahl tauschen
Diese Antwort melden
geantwortet

Student, Punkte: 35

 

Kommentar schreiben