Collatz-Problem

[CaptainNeemo]

Hallo liebes Forum,
ich wollte mich an euch wenden und zwar geht es um das sogenannte Collatz-Problem. Hierbei soll ich testen wie oft ich Zahlen iterieren muss um auf den Wert 1 zu kommen (x%2==0, dann x /2. Wenn ungerade 3*x+1).

Diese Werte sollte ich für die ersten 2**20 Zahlen berechen und in ein Dictionairy schreiben. Ihr seht unten meinen Stand.

Jedoch gibt mir meine Funktion als return value immer None aus. Wähle ich statt ""return count"" ""return print(count)"", printet die Funktion was sie soll.

Aber sobald ich nur count returne, scheint die Funktion nicht meine Variable count an die nächste Funktion zu übergeben.
Rufe ich diese über meine zweite Funktion auf, bekomme ich anscheinend None.

Wenn ihr andere Lösungungsansätze habt, welche schneller und einfacher sind, dann immer gerne her damit, ich bin noch im Anfangsstadium was Python angeht und habe Lust zu lernen.

Vielen Dank schonmal

Code: Alles auswählen

iterdict = {1:0}
def iter(n,count):
    """Dies ist die Funktion, welche darstellt wie oft man eine Zahl iteriert werden muss, im Sinne des Collatz-Problems, bis sie das erste Mal den Wert 1 erreicht. Setzen sie die Variable Count zu Beginn auf 0 und wählen Sie ihre Zahl n beliebig."""
    if n in iterdict:
        count = count + int(iterdict[n])
        return count
    elif n>1:  
        if n%2==0:
            n = n/2
            count = count + 1
            iter(n,count)
        else:
            n = n*3 +1
            count = count + 1
            iter(n,count)
    else: 
        print("Bitte geben Sie einen Wert über 1 ein")

def tau(N):
    "Dies ist die Funktion Tau, welche berechnet wie oft ein Element, im Sinne des Collatz-Problems iteriert werden muss, um das erste Mal den Wert 1 zu erreichen. Sie berechnet alle Werte bis zu einem Endpunkt N und fügt Sie in das Dictionary iterdict"
    for i in range (1,N):
        iterdict[i] = iter(i,0)
        

[__blackjack__]

@CaptainNeemo: Als erstes fällt einem als Python-Programmierer auf, dass Du den Namen `iter` verwendest und damit die eingebaute `iter()`-Funktion verdeckst. Das ist verwirrend und sollte man nicht machen.

Man muss nicht jedes Zwischenergebnis an einen Namen binden.

Der `int()`-Aufruf ist überflüssig, denn die Werte in dem Wörterbuch sind bereits ganze Zahlen.

Das `count`-Argument könnte man mit einer 0 als Defaultwert vorbelegen, dann muss der erste Aufrufer das nicht sinnloserweise mit angeben.

Ohne semantisch etwas an Deiner Funktion zu verändern kann man die so schreiben:

Code: Alles auswählen

def collatz(n, count=0):
    """
    Dies ist die Funktion, welche darstellt wie oft man eine Zahl iteriert
    werden muss, im Sinne des Collatz-Problems, bis sie das erste Mal den Wert 1
    erreicht. Setzen sie die Variable Count zu Beginn auf 0 und wählen Sie ihre
    Zahl n beliebig.
    """
    if n in _collatz_cache:
        return count + _collatz_cache[n]
    elif n > 1:
        collatz(n // 2 if n % 2 == 0 else n * 3 + 1, count + 1)
    else:
        print("Bitte geben Sie einen Wert über 1 ein")

Ein `print()` ist hier allerdings keine adäquate Fehlerbehandlung. Dafür gibt es Ausnahmen. Und das würde man auch als erstes in einer Funktion prüfen und nicht um letzten Zweig.

Globale Variablen sind schlecht. Als Cache für eine Funktion und ihre Ergebnisse geht das vielleicht gerade noch so, aber ganz sicher nicht über zwei Funktionen hinweg. Das ist etwas für die `collatz`-Funktion und zwar nur für die! Womit die `tau()`-Funktion überflüssig wird.

Bleibt also das hier:

Code: Alles auswählen

#!/usr/bin/env python3


def collatz(n, count=0):
    """
    Dies ist die Funktion, welche darstellt wie oft man eine Zahl iteriert
    werden muss, im Sinne des Collatz-Problems, bis sie das erste Mal den Wert 1
    erreicht.
    """
    if n < 1:
        raise ValueError("n muss >=1 sein")

    if n in collatz.cache:
        return count + collatz.cache[n]
    else:
        result = collatz(n // 2 if n % 2 == 0 else n * 3 + 1, count + 1)
        collatz.cache[n] = result


collatz.cache = {1: 0}

Der Fehler ist da immer noch drin. Im ``else``-Zweig gibt die Funktion nichts zurück. Das bedeutet sie gibt `None` zurück.

[CaptainNeemo]

@_blackjack_: Wow vielen Dank für diese schnelle und sehr ausführliche Antwort. Habe mir auch mal die iter()-Funktion durchgelesen, das war natürlich keine Absicht eine von Haus aus bestehende Funktion zu überschreiben. Vielen Dank das hat mir sehr weiter geholfen.

Tatsächlich geht es in der Tau Funktion jedoch hauptsächlich darum mein Dictoniary zu erweitern und die Anzahl der Iterationen für alle Elemente bis zu einem bestimmten Wert zu definieren um so das Ergebnis zu plotten. Ich habe jetzt auch wieder eine Idee wie ich weiter vorgehen kann.

Eine blöde Frage aus Neugier: Was verwendet man denn eher anstatt globaler Variablen, ich verstehe deren Anfälligkeit, wüsste jetzt aber auch keinen Weg drum rum oder ist das dann speziell vom Bereich und Funktion abhängig.

[__blackjack__]

@CaptainNeemo: Du brauchst Du die `tau()`-Funktion gar nicht um den Cache zu füllen wenn die `collatz()`-Funktion das selbst macht.

Für so einen Funktionscache braucht man eine globale Variable, weil die Funktion ja auch eine globale Variable ist. Aber man würde die nicht so öffentlich zur Verfügung stellen und vor allem auch nicht in einer anderen Funktion mit Werten füllen. Simpel manuell kann man den Cache wie im Beispiel als Attribut auf der Funktion definieren. Man kann sich aber auch einen allgemeinen Dekorator dafür schreiben, oder einen fertigen nehmen, wie beispielsweise das externe `cachetools.cashed()`.

Was man davor dann aber machen sollte ist die Rekursion loswerden, denn es gibt durchaus Zahlen bei denen die Anzahl der Schritte die maximale Rekursionstiefe von einem normalen Python-Interpreter sprengen und die Funktion mit einem Fehler abbricht. Es gibt auch überhaupt keinen Grund das rekursiv auszudrücken.

Code: Alles auswählen

#!/usr/bin/env python3
from itertools import count

from cachetools import cached


@cached({})
def collatz(n):
    """
    Dies ist die Funktion, welche darstellt wie oft man eine Zahl iteriert
    werden muss, im Sinne des Collatz-Problems, bis sie das erste Mal den Wert 1
    erreicht.
    """
    if n < 1:
        raise ValueError("n muss >=1 sein")

    for step_count in count():
        if n == 1:
            return step_count
        n = n // 2 if n % 2 == 0 else n * 3 + 1

    raise AssertionError("unreachable")


def main():
    print(list(map(collatz, range(1, 100))))


if __name__ == "__main__":
    main()

[__blackjack__]

Ich sollte so spät (früh?) nix mehr schreiben. Nichtrekursiv wird der Cache natürlich nicht richtig verwendet. Man muss den dann doch explizit in der Funktion füllen/verwenden.

[CaptainNeemo]

@_blackjack_: Ich habe das ganze dennoch begriffen. Aber eine kurze Frage. Der main Teil ist dann beim Programmieren der Teil in dem ich mein gesamtes Programm ausführe und der Definitionsbereich liegt dann darüber.

[sparrow]

Wo ist denn "darüber"?

Die main-Funktion sollte der Einstieg in dein Programm sein und wie hier beschrieben durch das if __name__ .... Konstrukt aufgerufen werden.

[CaptainNeemo]

@sparrow: Mir wurde beigebracht, das ein Python Programm aus 3 Teilen bestehen sollte:
Zunächst der import nötiger Module, dann die Definitionen der Klassen und Funktionen und danach sollte der Anweisungsblock folgen.
Daher meinte ich darüber steht die Definition.

[sparrow]

Der "Anweisungsblock" steht aber nicht auf Modulebene. Dort stehen nur die Importe, die Definitionen von Funktionen und Klassen und die Definition von Konstanten.
Der Grund dafür ist recht einfach: Was auf Modulebene (also uneingerückt) im Code steht, wird beim Import sofort ausgeführt. Das möchte man aber nicht.

Ich verstehe noch immer nicht, wo "darüber" ist, aber vielleicht beantwortet die Erklärung deine Frage.

[Sirius3]

Wobei der Anweisungsblock aus genau den zwei letzten Zeilen besteht, die Blackjack in seinem Code hat; wo die Definition der main-Funktion innerhalb der Definitionen steht, ist eigentlich egal, üblich ist es aber, als letztes.

[CaptainNeemo]

@sparrow: Ich meinte damit das mein Script für die Fibonacci Zahlen nach meiner Überarbeitung zum Beispiel so aussieht:

1.Block

Code: Alles auswählen

from pylab import *
from itertools import count
from cachetools import cached

2.Block

Code: Alles auswählen

@cached(cache={})
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

def mainfib(N):
    Fibo_Nmbr = list(map(fib, range(2,N)))
    print(Fibo_Nmbr)

if __name__ == "__mainfib__":
    mainfib

3.Block

Code: Alles auswählen

mainfib(12)

Hier liegt mein Definitionsblock(2) über dem Anweisungsblock (3). Also ich meine nördlich davon.
Hier gilt auch gebt mir gerne Tipps ich möchte gerne ''sauber" arbeiten und meine Syntax so gestalten, das sie verständlich und sinnvoll ist.

[sparrow]

Den 3. Block gibt es nicht.
Dein Programm steht in Funktionen und beginnt in der main-Funktion.

[CaptainNeemo]

Ah jetzt verstehe ich die Syntax in den letzten zwei Zeilen bedeutet, dass sobald main definiert wurde, wird main ausgeführt?

[sparrow]

Die letzten Zeilen lauten immer:

Code: Alles auswählen

if __name__ == "__main__":
    main()

__name__ ist ein "magischer" Name, den jedes Modul enthält. Handelt es sich um das Script, dass durch den Interpreter gestartet wurde, ist der Wert "__main__". Ansonsten ist der Wert der Name des Moduls.
Mit der Abfrage erhält man also die Sicherheit, dass das Modul direkt gestartet und nicht importiert wurde - und nur dann ruft man main() auf.

Noch einmal zum Verständnis: Wenn man ein Modul importiert, dann wird jeglicher Code auf Modulebene sofort ausgeführt. Deshalb schreibt man da nichts hin.
Falls du denkst, dass dein Programm nie importiert wird: Das ist nicht richtig. Es gibt Tools die das tun. Also gewöhn dir gleich das korrekte Vorgehen an.

[CaptainNeemo]

@sparrow Okay vielen vielen Dank, das war sehr hilfreich und auch vielen Dank an @_blackjack_

[sparrow]

Nebenbei umgeht man so auch gleich den Drang, globale Variablen benutzen zu wollen

[Sirius3]

Variablennamen werden grundsätzlich komplett klein geschrieben. Benutze keine Abkürzungen. Wenn Du numbers meinst, schreibe nicht mbnr oder so ähnlich.

Code: Alles auswählen

@cached(cache={})
def fibonacci(n):
    return n if n < 2 else fibonacci(n - 1) + fibonacci(n - 2)

def mainfib(max_fibonacci_number):
    fibonacci_numbers= list(map(fib, range(2, max_fibonacci_number)))
    print(fibonacci_numbers)

if __name__ == "__main__":
    mainfib(17)

[narpfel]

Noch als Hinweis: Seit Python 3.9 gibt es `functools.cache`, damit spart man sich die externe Abhängigkeit `cachetools`.