Laden...

Zahlenfolge ala Fibonaci

Erstellt von Stube vor 17 Jahren Letzter Beitrag vor 17 Jahren 10.103 Views
S
Stube Themenstarter:in
112 Beiträge seit 2006
vor 17 Jahren
Zahlenfolge ala Fibonaci

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

Warum verschoben ? Das soll auf meine Website ^^

Auch anfänger haben "mal" ne frage 😁

M
13 Beiträge seit 2005
vor 17 Jahren

So sollte es gehen.


int fibominus1=1;
int fibominus2=0;
int fibo;

Console.WriteLine(fibominus2);
Console.WriteLine(fibominus1);

for (int x = 1; x < 20; x++)
{
    fibo = fibominus1 + fibominus2;
    fibominus2 = fibominus1;
    fibominus1 = fibo;
    Console.WriteLine(fibo);
    
}

T
327 Beiträge seit 2006
vor 17 Jahren

Also,

wenn du Fibonacci richtig schreibst findest du was bei Wikipedia:

http://de.wikipedia.org/wiki/Fibonacci-Folge

Da steht schon mal das Bildungsgesetz drin.

Das einfach noch in ne Funktion einbauen und die Funktion dann rekursiv aufrufen. (Abbruchbedingung nicht vergessen !!!)

Verschoben wahrscheinlich deswegen, weil das was du willst eine grundsätzliche Frage zu .NET ist und keine spezielle Frage der Webtechnologie.

S
Stube Themenstarter:in
112 Beiträge seit 2006
vor 17 Jahren

und wie schreibe ich die jetzt auf die homepage, also in das literal ?
danke schonmal bis jetzt !!!

Auch anfänger haben "mal" ne frage 😁

S
Stube Themenstarter:in
112 Beiträge seit 2006
vor 17 Jahren

ja ich weiß ja wie die bildung ist 😉
nur, wie binde ich den code daoben jetzt in ein literal, ich bin ein absoluter anfänger bei ´c#

Auch anfänger haben "mal" ne frage 😁

S
Stube Themenstarter:in
112 Beiträge seit 2006
vor 17 Jahren

habs hingekriegt, allerdings kommen so nur die zahlen von 1-20

Auch anfänger haben "mal" ne frage 😁

L
497 Beiträge seit 2006
vor 17 Jahren

Das ist jetzt aber nicht Dein Ernst oder?

Sarkusmus ist, wenn nichts mehr hilft, außer Lachen.

W
799 Beiträge seit 2004
vor 17 Jahren

Weil die Schleife nur bis 20 läuft.

S
Stube Themenstarter:in
112 Beiträge seit 2006
vor 17 Jahren

🙂 doch war mein ernst, bis ich auf die gloreiche idee kam, anstatt X fibo einzugeben 😁 😁 😁 😁 😁 selbsteinereinhaut

Auch anfänger haben "mal" ne frage 😁

D
128 Beiträge seit 2005
vor 17 Jahren

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#

habs hingekriegt, allerdings kommen so nur die zahlen von 1-20

Gruss, DaMoe

S
Stube Themenstarter:in
112 Beiträge seit 2006
vor 17 Jahren

hab ich mir auch grade überlegt, wenn ich hier immer poste und die sachen dein reinhau, lern ich nix, bringt mir also nix 😉 danke Damoe

Auch anfänger haben "mal" ne frage 😁

49.485 Beiträge seit 2005
vor 17 Jahren

Hallo DaMoe,

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.

herbivore

N
46 Beiträge seit 2006
vor 17 Jahren

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]

22 Beiträge seit 2004
vor 17 Jahren

Original von niceBeast

  
public static int Fibonacci(int n){  
  return n==1 ? (1) : (n==2) ? (1) : (Fibonacci(n-1)+Fibonacci(n-2));  
}  
  

Hi,

warum verwendest du so viele Kalmmer?

Ein Einfaches "return n1 ? 1 : n2 ? 1 : Fibonacci(n-1)+Fibonacci(n-2);" hätte auch gereicht.

Servus...
Para.

N
46 Beiträge seit 2006
vor 17 Jahren

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)

niceGreeze
niceBeast

N
46 Beiträge seit 2006
vor 17 Jahren

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:


public static decimal FibonacciRecursiv(decimal n){
	return n==1 ? (1) : (n==2) ? (1) : (Fibonacci(n-1)+Fibonacci(n-2));
}

Und extra für dich Paratrooper 😁


public static decimal FibonacciRecursiv(decimal n){
	return n==1 ? 1 : n==2 ? 1 : Fibonacci(n-1)+Fibonacci(n-2);
}

Außer man verwendet den Datentyp BigInt (auf codeproject erhältlich). Dann liegt die Grenze auf bei so 100.000.

N
46 Beiträge seit 2006
vor 17 Jahren

Hi nochmal.

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...

Danke schonmal 😁

niceGreeze
niceBeast

49.485 Beiträge seit 2005
vor 17 Jahren

Hallo niceBeast,

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.

herbivore

T
223 Beiträge seit 2006
vor 17 Jahren

Hi,

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?

Gruß Thomas

49.485 Beiträge seit 2005
vor 17 Jahren

Hallo Thomas B,

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.

N
46 Beiträge seit 2006
vor 17 Jahren

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...

niceGreeze
niceBeast

B
1.529 Beiträge seit 2006
vor 17 Jahren

Es gibt eine implizite Bildungsvorschrift für die Fibonacci-Folge.
Diese lautet:

F( n ) = [ (1+sqrt(5))^n - (1-sqrt(5))^n ] / [(2^n)*sqrt(5))]

EDIT: Damit es schöner aussieht noch mal als Bild.

4.207 Beiträge seit 2003
vor 17 Jahren

Zumal man sich bei der rekursiven Variante den Stack mit unnötigen Methodenaufrufen zumüllt ...

Wissensvermittler und Technologieberater
für .NET, Codequalität und agile Methoden

www.goloroden.de
www.des-eisbaeren-blog.de

49.485 Beiträge seit 2005
vor 17 Jahren

Hallo niceBeast,

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. 1015 wäre, wären das 1015-1 Additionen. Das geht sicher nicht in einer Sekunde!

herbivore

N
46 Beiträge seit 2006
vor 17 Jahren

@herbivore: Also, bei mir war's möglich, doch die iterative Variante war doch markant schneller.

@Borg: Danke, diese Formel hatte ich auch mal in der HTL, doch so schlampig wie die Schüler heute sind... 😁

niceGreeze
niceBeast

49.485 Beiträge seit 2005
vor 17 Jahren

Hallo niceBeast,

hast du denn auch die normaler rekursive Variante, also die mit zwei rekursiven Aufrufen benutzt? Sonst reden wir die ganze Zeit aneinander vorbei.

herbivore

N
46 Beiträge seit 2006
vor 17 Jahren

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.

niceGreeze
niceBeast

T
512 Beiträge seit 2006
vor 17 Jahren

Ist die explizite Formel eigentlich bei aktuellen CPUs besser?

Es müsste dafür ja auf dem CPU/FPU ne optimierte Exponentialfunktion geben.
Sonst ist das ja auch nur ne O(n) Operation.

Würde mich mal interessieren.

e.f.q.

Aus Falschem folgt Beliebiges

N
46 Beiträge seit 2006
vor 17 Jahren

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

niceGreeze
niceBeast

49.485 Beiträge seit 2005
vor 17 Jahren

Hallo niceBeast,

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.

puh, alles andere hätte mein Weltbild zerstört.

herbivore

N
46 Beiträge seit 2006
vor 17 Jahren

puh, alles andere hätte mein Weltbild zerstört.

Dann kannst du ja wieder ruhig einschlafen 😁

niceGreeze
niceBeast