Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Hallo,
Ich soll eine rekursive Darstellung der Fibonacci-Folge programmieren, allerdings komme ich einfach nicht voran.
Ich habe mit natürlich bereits einige Beispiele im Internet angeschaut, allerdings verstehe ich dabei oftmals den Kern des Codes nicht.
Vielleicht kann mir jemand von euch helfen, einen einfachen Code mit Erklärung zu schreiben.
Die naive rekursive Definition ist in diesem Fall einfach die direkte Umsetzung der mathematischen Definition: Für die ersten beiden Folgeglieder sind feste Werte vorgegeben, für alle weiteren Werte muss man zur Berechnung auf das letzte und vorletzte Folgeglied zurückgreifen:
Dich verwirren wahrscheinlich ausgefeiltere Implementierungen, denn die oben genannte ist furchtbar ineffektiv, weil für höhere Folgeglieder enorm viele frühere Glieder mehrfach berechnet werden müssen.
Schreiben wir es doch einmal in Pascal-ähnlichem code hin
Java:
public static long fib(int n) {
if (n == 0) then {
return 0;
} else if then (n == 1) then {
return 1;
} else {
return fib(n-1) + fib(n-2); //der rekursive Aufruf
}
}
oder Deutsch:
Java:
public static long fib(int n) {
wenn (n == 0) dann {
return 0;
} wenn (n == 1) dann {
return 1;
} wenn etwas anderes {
return fib(n-1) + fib(n-2); //der rekursive Aufruf
}
}
und wenn du lieber TO das nun nicht auf die dir sicher vorliegende mathematische Definition der Fiboncci Reihe legen kannst, bist du im falschen Forum.
--
"If-Sätze" ???:L Na ja, wenigstens nicht if-Schleife
Ich hab' zwar (ähnlich wie Landei) auch schon längst den totalen Scala-Schaden, und benutze selten stinknormale for-int-i-Schleifen , aber vielleicht erscheint dir die Version ohne Rekursionen und If's einfacher:
Java:
import static java.lang.System.*;
public class Fibonacci {
public static long fib(int n){
long a = 0, b = 1;
for (int i = 0; i < n; i++) b = a + (a = b);
return a;
}
public static void main(String... _){
for (int i = 0; i <= 50; i++) out.println(i + ":\t" + fib(i));
}
}
Hab's extra kurz gehalten, damit du das nicht einfach als Hausaufgabe abgeben kannst, du musst ja auch irgendeinen Spaß am Knobeln haben^^
[kriegt's einer mit weniger token hin (long nach int und variablennamen ändern zählt nicht)? ]
Ich denke genau eine solche rekursive Darstellung wird der TO brauchen, obwohl ich selbst die Variante mit der for Schleife bevorzuge. (damit kann ich besser umgehen)
sk72 ich denke es wäre gut, wenn du dein Problem noch etwas spezifischer beschreiben könntest, damit wir uns einen besseren Überblick von deinem Problem machen können.
Ich denke genau eine solche rekursive Darstellung wird der TO brauchen, obwohl ich selbst die Variante mit der for Schleife bevorzuge. (damit kann ich besser umgehen)
Wie du siehst, benötigt fib(5) die Werte von fib(4) und fib(3), aber fib(4) selbst braucht auch wieder fib(3) u.s.w. Diese Mehrfachberechnungen versucht man deshalb zu vermeiden (mit Arrays, Maps, paralleler Berechnung von 2 Werten, Matrixmultiplikation, andere Formeln u.s.w.)
Jenau!
Nein, mal im Ernst: ich fand einfach nur die separate Fallunterscheidung für n = 0 und n = 1 unnötig, geht ja auch mit einem <= , und es rennt nicht in unendlichschleife davon, wenn man mal was negatives eingibt
"Bedingungen addiert" klingt komisch. Bevor du was ausimplementierst, ist es sehr hilfreich, wenn du weißt, was du da tust. Landei hat lediglich 1:1 die Definition
Code:
F(n) := {
0 falls n = 0
1 falls n = 1
F(n-1) + F(n-2) sonst
in Java hingeschrieben. Wenn Du nicht mal die Definition verstehst, dann ist es zu früh, über java-code zu reden: nimm Bleistift, werte die Formel per hand für n = 1,2,3 aus.
Vor dem PC bzw. an den mangelnden Java bzw. Programmiergrundlagen ;-)
Fehler stecken quasi in fast jeder Zeile. Das ganz enthält "grammatikalische" Fehler und lässt sich so natürlich nicht kompilieren.
Sind Methoden ein Begriff und Deklaration primitiver Variablen ein Begriff?
Ich habe den Eindruck, dass auch die Rekursion grundsätzlich nicht verstanden wird. ? (eine Methode ruft sich selbst auf)
Ich würde mal mit etwas einfachem anfangen. z.B. gib alle Zahlen von 0 bis n rekursiv aus.
Versuchst Du jetzt das ganze doch iterativ (for Schleife), statt rekursiv zu lösen?
Beides nur sehr bedingt und auf einfachstem Niveau.
Nein, das Problem soll rekursiv gelöst werden.
Doch, ich verstehe die Rekursion grundsätzlich schon - meine ich zumindest: F(n) ist die Summe beider Vorgänger ?!
Und nein, ich weiß auch nicht wie ich eine Rekursion aller Zahlen von 0 bis n in Java programmieren könnte. Mathematisch wäre das ja f(n) = f(n-1)+1 ?
Ich würde halt einfach eine for-Schleife durchlaufen lassen ? Aber das ist ja nicht rekursiv oder ?
Ja, das ist richtig
Für die Rekursion: Du rufst die Funktion erst mit n (sagen wir 10) auf. In der Methode prüfst du dann, ob n = 0 ist, wenn ja, gibst du 0 aus und returnst. Wenn n != 0, dann rufst du deine funktion mit n-1 nochmals auf und gibst danach n aus. So wird immer und immer wieder n um 1 verringert, die Funktion geht immer "tiefer", bis es 0 wird, dann wird die Zahl ausgegeben und die Methode "steigt" wieder "auf" und gibt eine Zahl nach der anderen aus.
Also, im allgemeinen bezeichnet Rekursion eine Technik um eine Funktion durch sich selbst zu definieren. Dazu könntest du auch mal Wikipedia bemühen: Rekursion.
Das stimmt nicht, das würde ja bedeuten, dass f(5) = f(4)+1 = 4, aber richtig ist: f(5) = f(4)+f(3) vgl.: Fibonacci-Folge.
Also brauchst du um f(n) berechnen zu können f(n-1) und f(n-2)!
Der Algorithmus sieht, wie auch schon von 0x7F800000 geschrieben so aus:
Code:
F(n) := {
0 falls n = 0
1 falls n = 1
F(n-1) + F(n-2) sonst
};
Das ist soweit der mathematische Hintergrund.
Um das nun in ein Stück Java-Code zu bringen, sollten jedoch die elementarsten Programmierkenntnisse vorhanden sein.
[offtopic] Obwohl ich mich immer wieder wundern muss, wieso man immer mit einer OO-Sprache das Programmieren lernen will/soll, da ist meiner Meinung nach eine Sprache wie Pascal um längen geeigneter.
public class FibonacciFolge {
public static void main (String [] args) {
long[] fib = new long[10];
fib[0] = 0;
fib[1] = 1;
for(int i = 2; i < fib.length; i++) {
fib[n] = fib[n-1] + fib[n-2];
System.out.println(fib[n]);
}
}
}
Das ist so ziemlich das, was deinem Code am nächsten kommt, allerdings ist das eine iterative (und keine rekursive) Lösung. Normalerweise würde man das natürlich noch in eine extra Methode auslagern u.s.w.
Ich denke, du solltest dich jetzt nicht an diesem Problem festbeißen, sondern erst einmal die Grundlagen lernen: Variablenzuweisungen, Methoden, Arrays u.s.w.
Also, im allgemeinen bezeichnet Rekursion eine Technik um eine Funktion durch sich selbst zu definieren. Dazu könntest du auch mal Wikipedia bemühen: Rekursion.
Das stimmt nicht, das würde ja bedeuten, dass f(5) = f(4)+1 = 4, aber richtig ist: f(5) = f(4)+f(3)
In folgendem Code gibt die Methode printNext die Zahlen von 0 bis n rekursiv aus.
Ich habe mal versucht den Code möglichst einfach und verständlich zu halten - hoffe es ist mir gelungen.
Java:
public static void main(String[] s) {
printNext(0, 5);
}
public static void printNext(int precessor, int limit) {
int next = precessor +1; // Berechne den Nachfolger
if (next <= limit) { // wenn die Grenze noch nicht überschritten ist
System.out.println(next); // gib den Nachfolger aus
printNext(next, limit); // rufe die Methode mit dem ermittelten Nachfolger auf
}
}
Ja, wie jetzt? Die Mathematische Definition hat Landei doch einfach nur wirklich 1:1 hingeschrieben, nur halt in java-style geklammert. Alles was bei der mathematischen Notation als
Code:
WERT falls PRÄDIKAT
da steht, wird ins englische übersetzt [falls = if, sonst = else], und dann einfach nur zu
Java:
if(PRÄDIKAT){ return WERT; }
verdreht und geklammert. Die Typen der Funktionen, die in der Mathematischen Notation als
Code:
f: X -> Y
hingeschrieben werden, übersetz man in Java so:
Java:
Y f(X x){ /* irgendwas vom typ Y zurückgeben */ }
Also wird die mathematische Definition
Code:
f: int -> long
f(n) := {
n falls n <= 1
f(n-2) + f(n-1) sonst
zu
Java:
long f(int n){
if( n <= 1 ){
return n;
}else{
return f(n-2) + f(n-1);
}
}
ggf fügt man da noch das static-keyword hinzu, damit man keine Instanzen braucht, um die Methode aufzurufen... Was soll denn daran schwer sein?
Ich stehe noch ganz am Anfang meines Studiums und dementsprechend besitze ich auch kaum Kenntnisse in Java.
Genau solche Beiträge halten mich immer wieder davon ab, mit einem Musikstudium anzufangen, obwohl ich nie ein Instrument aus der Nähe gesehen habe^^
Folgende Tipps:
1) Leg dir deine persönliche Liste von Lieblingsprogrammen an, die du in zukunft bei jeder neuen "halbwegs general-purpose" - Sprache durchprogrammierst, etwa:
- eine zahl ausgeben
- zwei zahlen addieren und ausgeben
- alle quadrate von 0 bis 100 ausgeben
- fakultät berechnen
- ein paar arrays / listen / maps / sets / matrizen anlegen, je nach dem was die bibliothek / sprache hergibt
- mergesort implementieren
- eingaben von der konsole einlesen, echo ausgeben
Wenn du dir viertel Stunde Zeit für sowas nimmst und es hinbekommst, dann kannst du dir sicher sein, dass du die minimal notwendigsten 10% der Sprache beherrschst, dich mit deinem Programm über die Konsole unterhalten, und somit beobachten kannst, was es so tut. Ab da läuft ales viel leichter, weil man ja sehen kann, was in der blöden Kiste passiert, danach ist es keine vollkommen finstere "Black-Box" mehr, und ab da kann man sich weiterentwickeln.
2) In den ersten 5 Semestern lernst in jedem Semester und in jeder Semesterpause jeweils eine andere Sprache. In deinem restlichen Studium lernst du alle 1.5 jahre eine neue Sprache. In deinem restlichen Leben lernst du alle 3 jahre eine möglichst grundlegend andersartige Sprache.
Das ist so nicht richtig, gerade für die natürlichen Zahlen (inklusive 0) gilt f(n) = f(n-1) + f(n-2)! bsp; f(6) ist laut deiner Definition: f(6) = f(5)+1 = f(4)+1+ 1= f(3)+1+1+1 = f(2)+1+1+1+1 = f(1) 1+1+1+1+1 = 1+1+1+1+1+1 = 6 und das ist definitiv ungleich der allgemeinen Definition: f(6) = f(5) + f(4) = 8
Genau das stellt ja auch die Fibonacci-Folge dar: ein n-tes Glied der Folge ergibt sich aus der Addition der beiden vorgänger Glieder. vgl: Wikipedia:
Die Fibonacci-Folge ist eine unendliche Folge von Zahlen (den Fibonacci-Zahlen), bei der sich die jeweils folgende Zahl durch Addition ihrer beiden vorherigen Zahlen ergibt: 0, 1, 1, 2, 3, 5, 8, 13, …
@Sich: Der TO spricht über das von jemand anderem ins SPiel gebrachte einfacherere Beispiel die Zahlen von 0 bis 10 auszugeben ohne Fibonacci. Das was er schrieb dazu, war richtig
Es scheitert(e anfangs) ja vor allem an der Rekursion.
Die Aufgabe mit dem Fibonacci Algorithmus war die vorletzte Übung auf dem Aufgabenblatt, alle Anderen konnte ich ohne Probleme lösen.
Ich werde mich vielleicht zunächst noch mit ein paar anderen Aufgaben intensiv(er) beschäftigen müssen, bevor ich auch diesen Algorithmus lösen kann.
Leg dir deine persönliche Liste von Lieblingsprogrammen an, die du in zukunft bei jeder neuen "halbwegs general-purpose" - Sprache durchprogrammierst, etwa:
Hier mal mein Code zu den Quadratzahlen, passt doch ? Jedoch gibt es bestimmt noch mehrere Codes die schneller rechnen, aber das sei mal für den Anfang uninteressant.
Java:
class quadrat{
public static void main(String[] args) {
int a = 0;
int b = 0;
while(a<=10) {
if(a==b) {
int c = a*b;
System.out.println(c);
a++;
b++;
}
}
}
}
Für die Fakultät werde ich auch mal noch versuchen einen Code zu schreiben, sollte mir doch hoffentlich gelingen.
Achja übrigens, sehr cooles Forum und nette User! Gefällt mir
Du könntest dir den Vergleich sparen Wenn du immer beide um einen erhöhst, dann sind die beiden Zahlen doch eh immer gleich Du köntnest es auch mit einer Zahl umsetzen^^
Aber sonst richtig
public class Square {
public static int square(int x) {
return sqrHelp(0, 1, x);
}
public static int sqrHelp(int s, int d, int x) {
if (x == 0) {
return s;
} else {
return sqrHelp(s + d, d + 2, x - 1); //der rekursive Aufruf
}
}
public static void main(String[] args) {
for(int i = 0; i < 20; i++) {
System.out.println(square(i));
}
}
}
