Runde 1 Entwerfen eines mathematischen Algorithmus

    Hallo Leute!

    Ich bin gerade bei der 2.Runde und weiß absolut nicht wie ich da anfangen soll, hat wer ebenfalls so ein ähnliches Beispiel bekommen??
    Kann mir irgendwelche Tipps geben wie man hier am besten vorgeht!

    Danke im Voraus
    prolog übung - Runde 2


    Kurzbeschreibung


    Aufgabe der zweiten Runde ist das Entwerfen eines mathematischen Algorithmus und Umsetzen in Java. Thema: Fibonacci-Folge Lösungshinweise


    Sie k?nnen wie im letzten Beispiel, Pseudocode schreiben, und/oder auch ein Struktogramm mit Nessi entwerfen und im Abgabearchiv mitliefern. Verplichtend ist nur die Abgabe des Java-Programmes. Aufgabenstellung


    Eine "Fibonacci-Folge" ist eine Folge von positiven, ganzen Zahlen f(0), f(1), f(2), ...
    Die ersten beiden Zahlen der Folge sind:
    f(0) = 1
    f(1) = 1
    Alle weiteren Folgenelemente sind definiert durch die "rekursive" Formel:
    f(n) = f(n-1) + f(n-2)
    d.h. jedes Element der Folge ist die Summe seiner beiden Vorg?nger.
    Der Anfang der Folge lautet also:
    1, 1, 2, 3, 5, 8, ... Schreiben Sie ein Java-Programm "Fibonacci", dass einen Zahlenwert n einliest und das Element f(n) ausgibt.

    Zitat von Horrendus

    Ob es ohne Rekursion überhaupt lösbar ist ... keine Ahnung.

    Natürlich, sogar effizienter als der "naive" rekursive Ansatz, der zum Beispiel für n=5 rechnet: f(5) = f(3)+f(4) = f(1)+f(2)+f(4) = f(1)+f(0)+f(1)+f(4) = f(1)+f(0)+f(1)+f(2)+f(3) = f(1)+f(0)+f(1)+f(0)+f(1)+f(3) = f(1)+f(0)+f(1)+f(0)+f(1)+f(1)+f(2) = f(1)+f(0)+f(1)+f(0)+f(1)+f(1)+f(0)+f(1) = ...

    Man kann das auch in einer Schleife bearbeiten, die f(2) aus f(1) und f(0) berechnet (diese beiden Werte sind ja von Anfang an bekannt) und das Ergebnis zwischenspeichert. Dann wird f(3) aus f(2) und f(1) berechnet, das Ergebnis wird wieder abgespeichert usw. Als Datenstruktur zum Abspeichern der Zwischenergebnisse kann man ein Array verwenden.

    Dieser Ansatz rechnet:
    f(2) = f(1)+f(0)
    f(3) = f(2)+f(1)
    f(4) = f(3)+f(2)
    f(5) = f(4)+f(3)

    Man sieht: Das sind bedeutend weniger Rechenoperationen.

    Horrendus: ja eh ich dachte das ist so ne Art Übung wo ich die Anfängerkenntnisse
    Einheimsen kann*lol*! Aber naja scheint irgendwie härter zu sein als die 3.ersten Runden des Eprogs und das wird nicht einmal als Studium angerechnet!


    @Paulchen du hast nicht zufällig ein ähnliches Beispiel, dass ich hernehmen könnte(als Muster) um nachvollziehen zu können wie es funktioniert??
    Naja komme aus einer AHS und soweit bin ich halt noch nicht :frowning_face:

    Paulchen hat es ehh schon gesagt.

    Du brauchst 3 Variablen:

    1 für f(n)
    1 für f(n-1)
    1 für f(n-2)

    Jetzt machst du eine Schleife von 2 (die erste f(n) die man berechnen muss) bis n

    Was machst du in der Schleife?

    Du berechnest f(n) aus den Variablen für f(n-1) und f(n-2) (welche du für 2 ja bereits weisst).
    Danach ersetzt du den Wert in f(n-2) durch den Wert von f(n-1) und den Wert von f(n-1) durch den Wert von f(n)

    Und nach der Schleife gibst du halt dann f(n) aus.

    lg Stefan

    Zitat von Horrendus

    Irgendwie kann man mit Linux ja ziemlich einfach die Runtime von Programmen ausgeben lassen ... wär bei Fibonacci sehr interessant die 2 Implementierungen zu vergleichen :winking_face:

    Ich hab beide Algorithmen mal schnell in C implementiert. Bei f(10) fällt der Unterschied noch nicht so auf (bei mir 14 µs gegen 2 µs), aber bei f(50) schon beträchtlich: Bei meinem Testlauf hat die eine Implementierung 393736469 µs gebraucht (das sind über sechs Minuten), die andere lediglich 5 µs.

    horrendus hat es in post #6 eh schon ganz gut erklärt. aber weils anscheinend immer noch nicht klar ist:
    wenn du es nicht rekursiv machen willst, weil du mit funktionen noch nicht so fit bist geht es auch nur mit einer for-schleife. wenn n 0 oder 1 ist brauchst nur 1 ausgeben und eigentlich gar nix berechnen. sonst brauchst drei variablen. eine für das aktuelle n (sage wir i), eine für i-1 und eine für i-2.
    das i steigerst du von anfangs 2 bei jedem schleifendurchlauf um 1 bis es das geforderte n erreicht. in der schleife berechnest du die neuen werte. wichtig ist die reihenfolge, damit du dir nichts überschreibst was du noch brauchst :winking_face:
    f(i)=f(i-1)+f(i-2)
    f(i-2)=f(i-1)
    f(i-1)=f(i)

    jagt die jäger aus dem wald :: 667 - the neighbour of the beast

    oder man schreibt ein for, in dem man einfach das n immer zu einer summe zählt, so kommst du auch zur folge....

    summe = 1;
    dann die abfrage, ob das n 1 oder zwei ist, wenn es aber großer ist, startest du eine forschleife die immer das macht:

    solange kleiner als n
    summe = summe + i;


    also ich habs bewusst so schwammig reingeschrieben, weil die fibonacci-folge doch noch etwas leichter ist als zB die annäherung von pi.
    da kapier ich ja nichtmal die formel....

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!

Benutzerkonto erstellen Anmelden