Hi, ich hab mal wieder ne frage !
Ihr kennt doch bestimmt Fibonaci.
So die Fibonaci-Folge geht : 0,1,1,2,3,5,8,13,21....
also immer die beiden letzten Zahlen bilden die nächste...
Ich will also jetzt per code die Fibonaci-Folge generieren lassen!
Könnt ihr mir helfen ?
mfg
stube
Ich wuerde die Fibonacci Zahlen rekursiv berechnen. Ausserdem such doch mal unter Google nach Fibonacci und Rekursiv. Da findest Du eine Unmenge an Informationen
@michaelklaus: Das ist zwar nett, dass Du den Sourcecode postest, aber ich glaube an dieser Stelle waere nur ein Tip besser gewesen, was man auch an kurz vorangegangenem Posting von Stube sieht. Meistens sind das Lernaufgaben, die etwas mit Fibonacci zu tun haben und daher wuerde ich nicht sofort immer Source Code posten.
@Stube: Ohne das jetzt boese zu meinen, wuerde ich Dir raten entsprechende Quellen mal unter Google herauszusuchen, um ein besseres Verstaendnis von Fibonacci zu bekommen und natuerlich auch ein wenig von C#
Zitat
habs hingekriegt, allerdings kommen so nur die zahlen von 1-20
Ich wuerde die Fibonacci Zahlen rekursiv berechnen.
warum denn das??? Wenn du es rekursiv machst, brauchst du für f(30) mehr als eine Million Additionen, wenn du es iterativ machst, brauchst du nur 30 Additionen. Und rekursiv braucht man nicht weniger Code als iterativ, eher mehr.
Also weil ich zufällig auf diesen Thread gestoßen bin:
public static int Fibonacci(int n){
return n==1 ? (1) : (n==2) ? (1) : (Fibonacci(n-1)+Fibonacci(n-2));
}
Jedoch braucht mein pavilion notebook mit amd 64 3200+ Prozessor bei Fibonacci(36); schon fast eine Sekunde. Daher würd ich herbivore zustimmen und dir diese Rekursive Funktion nicht empfehlen.
Aber die Möglichkeit von michaelklaus77 gefällt mir gut. Du kannst das ja in eine Funktion packen:
public static int Fibonacci(int n){
int fibominus1=1;
int fibominus2=0;
int fibo;
for (int x = 1; x < n; x++){
fibo = fibominus1 + fibominus2;
fibominus2 = fibominus1;
fibominus1 = fibo;
}
return fibo;
}
niceGreeze
niceBeast
[EDIT]
Wenn jemand die Uhrzeit aufgefallen sein sollte, nich wundern, ich muss heute durcharbeiten, um mit meinem Part eines Projekts fertig zu werden. Und das schlimmste daran, im Fernsehen laufen nur Quizshows...
[/EDIT]
Naja, ich kanns halt so besser lesen.
Und ich glaube die paar Klammern ändern auch nix an der Performance
Die Performance ist übrigens bei der rekursiven Funktion doch fast gleich schnell wie bei der anderen. Aber das ich das so sehe könnte auch an der Uhrzeit oder dem ständig rotierendem Ventilator über mir liegen
Jedenfalls weiß ich jetzt, dass ich nicht der einzige bin, der um diese Zeit noch auf ist 8)
Achja, übrigens ist bei der oben implementierten Funktion die Grenze für n um so 50 bis ein Überlauf erreicht wird.
Die Grenze für decimal liegt jedoch bei 139:
Ich wollte jetzt mal kurz die Rekursive gegen die Iterativen Funktion performen lassen, aber die DateTime Klasse ist mir hier zu ungenau, weil beide Zeitdifferenzen gleich 0 sind.
Hat wer mal schnell einen halbwegs genauen Timer auf lager?
Habe mich bisher noch nicht mit Timern auseinandergesetzt, weil ich die eigentlich nie brauchte...
wenn du messen willst, führe dieselbe Berechung in einer Schleife immer und immer wieder aus. Dann reicht auch DateTime und gleichzeitig minimiert man damit den Einfluss des JIT-Compilers auf die Berechnung.
Aber es ist schon wie ich sagte, die rekursive Funktion ist um *Größenordnungen* langsamer als die iterative.
Ich habe da eine Frage. Warum habe ich bei der rekursiven Funktion mehr Additionen als bei der anderen Möglichkeit? Ich kann meiner Funktion doch die zuletzt gerechnete Zahl und den Vorgänger mitgeben, sodass immer nur die nächste Zahl errechnet wird, und dann sollten es doch gleich viele Additionen sein?
weil "normale" rekursive Definition der Fibonacci-Folge zwei rekursive Aufrufe hat, nämlich für f(n-1) und für f(n-2).
Man kann natürlich die Schleife der iterativen Variante - wie jede Schleife - in eine Rekursion umsetzen und hätte dann nur einen rekursiven Aufruf. Aber warum sollte man das tun?
Also entweder rekursiv mit zwei Aufrufen (zu langsam) oder Iteration (schnell).
Eine rekursive Varianten mit nur einem Aufruf (die zwar schnell wäre) ist nichts halbes und nichts ganzes.
herbivore
PS: Im Zweifel schreib mal alle drei Varianten auf, um sie zu vergleichen.
Naja gut, aber die obere Grenze bei decimal liegt ja bei 139, und deswegen denke ich, dass es von der Leistung selbst her nahezu egal ist, was man macht, da ja bei mir z.B. beide Varianten unter einer Sekunde liegen.
Ich werde trotzdem die Iterative Version weiterverwenden, falls ich die jemals brauchen sollte...
da ja bei mir z.B. beide Varianten unter einer Sekunde liegen.
die normale rekursive Variante braucht für die fib(n)-1 Additionen für die Berechnung von fib(n), also wenn das Ergebnis z..B. 10^15 wäre, wären das 10^15-1 Additionen. Das geht sicher nicht in einer Sekunde!
Jap, hab ich.
Hatte das schon selbst nichtmehr geglaubt, aber ich habs heute noch einmal ausprobiert: mein hp pavilion (AMD 64 3200+) rechnet das in weniger als einer Sekunde. Falls das etwas ausmacht: ich hab das in einer Konsolenapplikation getestet.
Hi,
Hier mal die Ergebnisse des Zeitaufwands bei meinem Rechner um die Nachteile der Iterativen- zur Formel-Variante deutlich darzustellen:
für: for(int i=0; i<100000; i++){
1.: Mithilfe der Formel von Borg
2.: Iterativ
16.09.2006 03:44:07 - 16.09.2006 03:44:07 = 00:00:00.0468750
16.09.2006 03:44:09 - 16.09.2006 03:44:07 = 00:00:01.9843750
Und weils so schön war, das ganze noch 1.000.000 statt 100.000 mal:
1.: Mithilfe der Formel von Borg
2.: Iterativ
16.09.2006 03:52:32 - 16.09.2006 03:52:31 = 00:00:00.5468750
16.09.2006 03:52:51 - 16.09.2006 03:52:32 = 00:00:19.6562500
Die Formel ist hier um ~36mal schneller als die Iterative Variante, außerdem wird der Stack vergleichsweise auch kaum belastet.
@Traumzauberbaum: Davon hab ich leider keine Ahnung.
@herbivore: Sorry, du hattest natürlich doch recht, ich rief in der Rekursiven die Iterative Var. auf. Die echte Rekursive dauert auf jedenfall länger als ich warten will. Scham über mich
So, jetzt 3mal editiert, ich geh jetzt schlafen, ich hab schon mühe meine Finger zu Bewegen... ;( GN
Sorry, du hattest natürlich doch recht, ich rief in der Rekursiven die Iterative Var. auf. Die echte Rekursive dauert auf jedenfall länger als ich warten will.
