Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Zahlenfolge ala Fibonaci
Stube
myCSharp.de - Member



Dabei seit:
Beiträge: 112
Herkunft: Wildbergerhütte

Themenstarter:

Zahlenfolge ala Fibonaci

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
michaelklaus77
myCSharp.de - Member



Dabei seit:
Beiträge: 13

beantworten | zitieren | melden

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);
    
}
private Nachricht | Beiträge des Benutzers
telnet
myCSharp.de - Member



Dabei seit:
Beiträge: 327

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
Stube
myCSharp.de - Member



Dabei seit:
Beiträge: 112
Herkunft: Wildbergerhütte

Themenstarter:

beantworten | zitieren | melden

und wie schreibe ich die jetzt auf die homepage, also in das literal ?
danke schonmal bis jetzt !!!
Auch anfänger haben "mal" ne frage
private Nachricht | Beiträge des Benutzers
Stube
myCSharp.de - Member



Dabei seit:
Beiträge: 112
Herkunft: Wildbergerhütte

Themenstarter:

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Stube
myCSharp.de - Member



Dabei seit:
Beiträge: 112
Herkunft: Wildbergerhütte

Themenstarter:

beantworten | zitieren | melden

habs hingekriegt, allerdings kommen so nur die zahlen von 1-20
Auch anfänger haben "mal" ne frage
private Nachricht | Beiträge des Benutzers
Lord Hessia
myCSharp.de - Member



Dabei seit:
Beiträge: 497
Herkunft: Gießener Umland

beantworten | zitieren | melden

Das ist jetzt aber nicht Dein Ernst oder?
Sarkusmus ist, wenn nichts mehr hilft, außer Lachen.
private Nachricht | Beiträge des Benutzers
Waschbecken
myCSharp.de - Member



Dabei seit:
Beiträge: 799

beantworten | zitieren | melden

Weil die Schleife nur bis 20 läuft.
private Nachricht | Beiträge des Benutzers
Stube
myCSharp.de - Member



Dabei seit:
Beiträge: 112
Herkunft: Wildbergerhütte

Themenstarter:

beantworten | zitieren | melden

doch war mein ernst, bis ich auf die gloreiche idee kam, anstatt X fibo einzugeben *selbsteinereinhaut*
Auch anfänger haben "mal" ne frage
private Nachricht | Beiträge des Benutzers
DaMoe
myCSharp.de - Member



Dabei seit:
Beiträge: 128

beantworten | zitieren | melden

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

Gruss, DaMoe
private Nachricht | Beiträge des Benutzers
Stube
myCSharp.de - Member



Dabei seit:
Beiträge: 112
Herkunft: Wildbergerhütte

Themenstarter:

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

Hallo DaMoe,
Zitat
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
private Nachricht | Beiträge des Benutzers
niceBeast
myCSharp.de - Member



Dabei seit:
Beiträge: 46
Herkunft: Straßwalchen(Salzburg)

beantworten | zitieren | melden

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]
private Nachricht | Beiträge des Benutzers
Paratrooper
myCSharp.de - Member

Avatar #avatar-1887.gif


Dabei seit:
Beiträge: 22
Herkunft: LA

beantworten | zitieren | melden

Zitat
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 n==1 ? 1 : n==2 ? 1 : Fibonacci(n-1)+Fibonacci(n-2);" hätte auch gereicht.

Servus...
Para.
private Nachricht | Beiträge des Benutzers
niceBeast
myCSharp.de - Member



Dabei seit:
Beiträge: 46
Herkunft: Straßwalchen(Salzburg)

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
niceBeast
myCSharp.de - Member



Dabei seit:
Beiträge: 46
Herkunft: Straßwalchen(Salzburg)

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
niceBeast
myCSharp.de - Member



Dabei seit:
Beiträge: 46
Herkunft: Straßwalchen(Salzburg)

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Thomas B
myCSharp.de - Member



Dabei seit:
Beiträge: 223

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
niceBeast
myCSharp.de - Member



Dabei seit:
Beiträge: 46
Herkunft: Straßwalchen(Salzburg)

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Borg
myCSharp.de - Member



Dabei seit:
Beiträge: 1.529
Herkunft: Berlin, Germany

beantworten | zitieren | melden

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.
Attachments
private Nachricht | Beiträge des Benutzers
Golo Roden
myCSharp.de - Member

Avatar #avatar-2167.png


Dabei seit:
Beiträge: 4.207
Herkunft: Riegel am Kaiserstuhl

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

Hallo niceBeast,
Zitat
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!

herbivore
private Nachricht | Beiträge des Benutzers
niceBeast
myCSharp.de - Member



Dabei seit:
Beiträge: 46
Herkunft: Straßwalchen(Salzburg)

beantworten | zitieren | melden

@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
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
niceBeast
myCSharp.de - Member



Dabei seit:
Beiträge: 46
Herkunft: Straßwalchen(Salzburg)

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Traumzauberbaum
myCSharp.de - Member



Dabei seit:
Beiträge: 512

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
niceBeast
myCSharp.de - Member



Dabei seit:
Beiträge: 46
Herkunft: Straßwalchen(Salzburg)

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

Hallo niceBeast,
Zitat
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
private Nachricht | Beiträge des Benutzers