Fibonacci-Sequenz darstellen

[Xfd7887a]

Ich will eine Gui schreiben, auf deren linken Seite ein Zaun (Rechteck) gezeichnet ist und auf der rechten Seite Formeln stehen. Unten sollen sich die Buttons "Nächster Monat" und "Vorheriger Monat" befinden. Dann sollen neue Hasen auf der linken Seite erscheinen und die rechte Formel soll sich auf verändern.
Welches GUI-Toolkit eignet sich hier am meisten? Wie muss ich vorgehen?

[BlackJack]

@Xfd7887a: Das sollte eigentlich mit jedem der gängigen GUI-Toolkits machbar sein.

Zum Vorgehen: Mach Dir die Programmlogik klar, ohne GUI. Also was macht den Zustand aus und welche Operationen diesen Zustand zu manipulieren benötigt man — beides ist ja sehr übersichtlich bei dem beschriebenen Programm. Das dann in eine Klasse kapseln.

Und danach dann die GUI da drauf setzen.

[Xfd7887a]

Erst mal entschuldige, dass ich damals nicht antwortete. Habe es irgendwie verpennt Ich möchte jetzt aber diese Idee wieder aufnehmen. Leider komme ich nicht weiter.

Zunächst dachte ich an die folgende Einteilung:

Code: Alles auswählen

paare = []

class Stall(object):
    def __init__(self):
        pass

    def monat_vergeht(self):
        for kaninchenpaar in paare:
            if kaninchenpaar.reif == True:
                paare.append(kaninchenpaar.kinder_bekommen())


class Kaninchenpaar(object):
    self.reif = False

    def set_reif(self, reif):
        self.reif = reif

    def kinder_bekommen(self):
        Kaninchenpaar()

Aber leider hänge ich und ich glaube auch, dass mein Ansatz falsch ist. Kann mir jemand eine grobe Struktur vorgeben. Damit ich erstmal einen Ansatz habe. Danke

[Sirius3]

@Xfd7887a: solche mathematischen Spielereien neigen dazu, sehr schnell sehr große Zahlen zu produzieren. Für jedes Kaninchen eine eigene Instanz zu haben, müllt Dir Deinen Arbeitsspeicher voll.
Soweit prinzipiell. Konkret solltest Du mit einem Tutorial lernen, wie man in Python mit Klassen umgeht, was Funktionen sind, und warum man keine globalen Variablen benutzen sollte.

[Xfd7887a]

Ok, danke für den Tipp. Habe das ganze erstmal so umgesetzt:

Code: Alles auswählen

import math


class Stall(object):
    def __init__(self, monat):
        self.monat = monat

    def get_anzahl_reife_paare(self):
        """Gibt die Anzahl der geschlechtsreifen Paare zurueck"""
        if self.monat == 1:
            return 0
        elif self.monat == 2:
            return 1
        else:
            return self.get_anzahl_paare() - self.get_anzahl_unreife_paare()

    def get_anzahl_unreife_paare(self):
        """Gibt die Anzahl der unreifen Paare zurueck"""
        if self.monat == 1:
            return 1
        elif self.monat == 2:
            return 0
        else:
            return Stall(self.monat-1).get_anzahl_reife_paare()

    def get_anzahl_kinder(self):
        """Gibt die Anzahl der neuen Kaninchenpaare zurueck"""
        if self.monat == 1 or self.monat == 2:
            return 0
        else:
            return self.get_anzahl_unreife_paare()

    def get_anzahl_paare(self):
        """Gibt die Anzahl aller Paare zurueck"""
        return fibonacci(self.monat)


def fibonacci(n):
    """Berechnung einer bestimmten Fib-zahl mit Hilfe Moivre-Binet"""
    return int(1/math.sqrt(5) * (((1+math.sqrt(5))/2)**n - ((1-math.sqrt(5))/2)**n))


def main():
    stall = Stall(5)
    print "Anzahl reife Paare: ", stall.get_anzahl_reife_paare()
    print "Anzahl Kinder: ", stall.get_anzahl_kinder()
    print "Anzahl unreife Paare:", stall.get_anzahl_unreife_paare()
    print "Insgesamt:", stall.get_anzahl_paare()

if __name__ == "__main__":
    main()

Nicht besonders schön, aber es funktioniert. Wie kann ich jetzt eine GUI einbauen?

[BlackJack]

@Xfd7887a: Der `Stall` ist aber nicht wirklich objektorientiert und ineffizient ist er auch weil der rekursiv das Ergebnis berechnet. Gleichzeitig hast Du mit der `fibonacci()`-Funktion aber auch noch die geschlossene Formel, die zwar in konstanter Zeit läuft, dafür aber das Problem hat, dass sie irgendwann wegen den Gleitkommazahlen ungenau wird. Und das alles wo man aus der iterativen Berechnungsvorschrift eigentlich sehr einfach ein Objekt beschreiben kann das sowohl effizient als auch genau aus dem aktuellen Zustand wahlweise den jeweils Nächsten als auch den Vorherigen berechnen kann.

[Xfd7887a]

Und das alles wo man aus der iterativen Berechnungsvorschrift eigentlich sehr einfach ein Objekt beschreiben kann das sowohl effizient als auch genau aus dem aktuellen Zustand wahlweise den jeweils Nächsten als auch den Vorherigen berechnen kann.

Ich verstehe leider nicht, wie du das meinst :K

[BlackJack]

@Xfd7887a: Da Du überlegst Dir wie man die Fibonacci-Zahlen iterativ berechnet, also ohne Rekursion und ohne geschlossene Formel. Dann hast Du eine Schleife in der alle Zahlen der Reihe nach berechnet werden. Nun musst Du überlegen was für Daten dort *ein* Schleifendurchlauf braucht um die *nächste* Zahl zu berechnen. Das ist der Zustand für das Objekt der in der `__init__()` auf Anfangswerte initialisiert werden muss. Die Berechnung für die nächste Zahl aus der Schleife kommt dann in eine Methode die zum Beispiel `next()` heisst und das berechnet was die Funktion vorher in *einem* Schleifendurchlauf gemacht hat, und den Zustand des Objekts entsprechend ändert. Und dann muss man sich nur noch überlegen wie man aus dem Zustand nicht die nächste Fibonacci-Zahl, sondern die vorhergehende berechnet. Also sozusagen die Umkehrfunktion zu `next()`. Könnte man `previous()` nennen. Dann könnte man dem Datentyp noch eine `__int__()`-Methode verpassen um die aktuelle Zahl zu ermitteln und könnte dann so etwas schreiben:

Code: Alles auswählen

def main():
    fibonacci_sequence = FibonacciIterator()

    for i in xrange(10):
        print(i, fibonacci_sequence.next())
    
    print(int(fibonacci_sequence))

    for i in reversed(xrange(9)):
        print(i, fibonacci_sequence.previous())
    
    try:
        fibonacci_sequence.previous()
    except Exception as error:
        assert isinstance(error, StopIteration)

Die Ausgabe davon sieht so aus:

Code: Alles auswählen

0 1
1 2
2 3
3 5
4 8
5 13
6 21
7 34
8 55
9 89
89
8 55
7 34
6 21
5 13
4 8
3 5
2 3
1 2
0 1

Mit einer GUI wie Du das im ersten Beitrag beschrieben hast liesse sich das auch recht einfach verbinden.

Edit: Wie man am Code sehen kann würde es sich anbieten eine `StopIteration` auszulösen wenn man versucht vor das erste Kaninchen zu gehen. In die andere Richtung ist die Sequenz ja endlos.

[BlackJack]

Ich habe die grundlegende Idee mal in C umgesetzt:

Code: Alles auswählen

#include <assert.h>
#include <stdio.h>

#define FIB_OUT_OF_RANGE    -1

typedef struct {
    int a;
    int b;
} Fibonacci;


void Fibonacci_init(Fibonacci *fib) {
    fib->a = fib->b = 1;
}

int Fibonacci_get(Fibonacci *fib) {
    return fib->a;
}

int Fibonacci_next(Fibonacci *fib) {
    int tmp;

    tmp = fib->a + fib->b;
    if (tmp < fib->a) return FIB_OUT_OF_RANGE;  /* Number overflow. */
    fib->a = fib->b;
    fib->b = tmp;
    return Fibonacci_get(fib);
}

int Fibonacci_previous(Fibonacci *fib) {
    int tmp;

    /* Trying to get before the big rabbit bang. */
    if (fib->b == 1) return FIB_OUT_OF_RANGE;

    tmp = fib->b - fib->a;
    fib->b = fib->a;
    fib->a = tmp;
    return Fibonacci_get(fib);
}

int main(void)
{
    int i;
    Fibonacci fib;

    Fibonacci_init(&fib);
    
    printf("%d\n", Fibonacci_get(&fib));

    for (i = 1; i <= 10; ++i) {
        printf("%d %d\n", i, Fibonacci_next(&fib));
    }

    printf("%d\n", Fibonacci_get(&fib));

    for (i = 9; i >= 0; --i) {
        printf("%d %d\n", i, Fibonacci_previous(&fib));
    }

    assert(Fibonacci_previous(&fib) == FIB_OUT_OF_RANGE);

    puts("\nLet's see how far we get...");
    for (i = 0;; ++i)
    {
        printf("%d %d\n", i, Fibonacci_get(&fib));
        if (Fibonacci_next(&fib) == FIB_OUT_OF_RANGE) break;
    }

    return 0;
}

[Hyperion]

@BlackJack: hübsch Jetzt noch bitte in 6502-Assembler

[darktrym]

Und Z80, der 6502 ist 'ne lahme Sau.

[Hyperion]

Und Z80, der 6502 ist 'ne lahme Sau.

Ok, ich präzisiere: 6510 Und der war toll!

[BlackJack]

@darktrym: Wer eine lahme Sau ist bestimmt ja nicht unwesentlich die Taktrate mit der man den jeweiligen Prozessor betreibt. Ansonten kann man sich ja auch eine kompatible CPU wie den 65C802 nehmen und die deutlich höher takten als den 6502/6510/8502.

@Hyperion: Das macht beim Programmieren keinen Unterschied ob man den 6502 oder 6510 vor sich hat. Die haben die gleichen Befehlssätze. Beim 65C802 wird's interessanter, der hat zusätzliche Befehle und man kann mehr Speicher adressieren und die Register von 8 auf 16 Bit schalten.

[Xfd7887a]

Sorry, das ich mich nicht nochmal gemeldet hatte. War ziemlich stressig die letzte Zeit, weshalb ich dieses Projekt total vergessen hatte Jetzt habe ich aber wieder Zeit und versuche diesmal dranzubleiben. Mit BlackJacks Tipps habe ich mal das folgende versucht:

Code: Alles auswählen

class FibonacciIterator(object):
    def __init__(self):
        self.a = self.b = 1

    def get(self):
        return self.a

    def next(self):
        tmp = self.a + self.b
        self.a = self.b
        self.b = tmp
        return self.get()

    def previous(self):
        tmp = self.b - self.a
        self.b = self.a
        self.a = tmp
        return self.get()

    def __str__(self):
        return "{} {}".format(self.a, self.b)


def main():
    fibonacci_sequence = FibonacciIterator()
    print fibonacci_sequence.get()

    for i in xrange(10):
        print(i, fibonacci_sequence.next())
   
    print fibonacci_sequence.get()
 
    for i in reversed(xrange(9)):
        print(i, fibonacci_sequence.previous())
   
    try:
        fibonacci_sequence.previous()
    except Exception as error:
        assert isinstance(error, StopIteration)

if __name__ == "__main__":
    main()

Ist das erstmal so in Ordnung? Das mit dem Number Overflow ist C-spezifisch, oder?

[darktrym]

Du benutzt xrange, was es nur in Python 2 gibt. Dann aber Klammern bei print was suggeriert wie haben vor uns ein Python 3.
Ich hoffe mal du importiert auch die Funktion aus future warum überlädst du dann nicht gleich range mit xrange? Dann hast du auch automatisch Python 3 Support.

[Xfd7887a]

Danke Habe es zu:

Code: Alles auswählen

 for i in range(10):
        print i, fibonacci_sequence.next()
   
    print fibonacci_sequence.get()
 
    for i in reversed(range(9)):
        print i, fibonacci_sequence.previous()
   

geändert.

[Sirius3]

@Xfd7887a: wunderbar, jetzt hast Du Python3-Variante von xrange und das print von Python 2. Was ist der Vorteil der get-Methode? tmp ist unnötig, weil man die Rechnung auch kürzer als

Code: Alles auswählen

self.a, self.b = self.b, self.a + self.b

schreiben kann.

[Xfd7887a]

Die aktualisierte Version:

Code: Alles auswählen

class FibonacciIterator(object):
    def __init__(self):
        self.a = self.b = 1

    def next(self):
        self.a, self.b = self.b, self.a + self.b
        return self.a

    def previous(self):
        self.a, self.b = self.b - self.a, self.a
        return self.a

    def __str__(self):
        return "{} {}".format(self.a, self.b)


def main():
    fibonacci_sequence = FibonacciIterator()
    print fibonacci_sequence.a

    for i in xrange(10):
        print i, fibonacci_sequence.next()
   
    print fibonacci_sequence.a
 
    for i in reversed(xrange(9)):
        print i, fibonacci_sequence.previous()
   
    try:
        fibonacci_sequence.previous()
    except Exception as error:
        assert isinstance(error, StopIteration)

if __name__ == "__main__":
    main()

[Xfd7887a]

Muss ich nun den Number Overflow auch in Python beachten?

[darktrym]

Gib doch mal in der Konsole 2**512 ein und was da kommt, klärt vermutlich deine Frage.