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.
Runde 1 Entwerfen eines mathematischen Algorithmus
-
Wow, für den Prolog ist das recht heftig find ich
Am einfachsten ist das ganze rekursiv zu lösen, was aber ein kleiner Vorgriff wär.
Ob es ohne Rekursion überhaupt lösbar ist ... keine Ahnung.lg Stefan
-
Ob es ohne Rekursion überhaupt lösbar ist ... keine Ahnung.
Also sollte eigentlich mit for auch möglich sein -
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
-
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
-
Stimmt, geht auch ohne Rekursion sehr einfach zu lösen.
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
lg
-
ich würde eher sagen die schleife von 1 bis n, nicht von 2 bis n
-
Hallo,
nein 2 bis n passt schon super, weil vor 2 musst du ja keine einzige Fakultät berechnen sondern hast sie schon gegeben (f(0) = f(1) = 1).
lg Stefan
-
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
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.
-
Das ist ein heftiger Unterschied. Thx Paulchen fürs ausprobieren.
lg Stefan
-
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
f(i)=f(i-1)+f(i-2)
f(i-2)=f(i-1)
f(i-1)=f(i) -
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!