Fibonacci Zahlen

Draco

God

Montag, 17. Januar 2005, 14:00

1

Ich hab grad ein Brett vorm Kopf oder bin einfach zu dumm.

hab grad ne Aufgabe in C fertig programmiert zum Thema Fibonacci Zahlen. Als Abschluss steht noch eine Frage in der Aufgabe:

Zitat

Ermittel Sie die Abhängigkeit zwischen einer Fibnacci Zahl f1 (f1=1) und der Anzahl der zur Berechnung erforderlichen Funktionsaufrufe Ai

Das Ergebniss sieht so aus:
(links nur Nummerierung, Kommazahl=Fibo.Zahl...)

Im netz habe ich noch folgendes dazu gefunden: klick

Was ist für ne Abhängigkeit gemeint ?

Y0Gi

God

Re: Fibonacci Zahlen

Montag, 17. Januar 2005, 14:06

2

ich denke es geht um die anzahl der benötigten schritte zur errechnung einer fibonacci-zahl. für die erste keinen, für die zweite einen, für die siebte sechs (oder so, bin grad nicht ganz fit). also n-1.

wenn man weiß, dass etwa 347 (angenommen) eine fibonacci-zahl ist, dann muss man ja (ohne schlaue formel) trotzdem am anfang anfangen und so lange die folge ergänzen, bis die gesuchte zahl produziert ist.

This is my sick nature. – NorthCon // LANresort Bispingen // BYCEPS (LAN party software platform) // OrgaTalk (LAN party orga board)

Gemini

Senior Member

Re: Fibonacci Zahlen

Montag, 17. Januar 2005, 14:41

3

Zitat von »Draco«

Ich hab grad ein Brett vorm Kopf oder bin einfach zu dumm.

hab grad ne Aufgabe in C fertig programmiert zum Thema Fibonacci Zahlen. Als Abschluss steht noch eine Frage in der Aufgabe:

Das Ergebniss sieht so aus:
(links nur Nummerierung, Kommazahl=Fibo.Zahl...)

Im netz habe ich noch folgendes dazu gefunden: klick

Was ist für ne Abhängigkeit gemeint ?

Villeicht (Kommazahl*2)-1 = Funktionsaufrufe

Kennen Sie Ted?

Y0Gi

God

Re: Fibonacci Zahlen

Montag, 17. Januar 2005, 14:52

4

ja, das macht schon mehr sinn.

ich seh grad, ich hätt auch eine der aufgelisteten zahlen als beispiel nehmen können :

naja, doofer tag, sollte mich doch besser wieder ins bett legen und mich gesund kurieren.

This is my sick nature. – NorthCon // LANresort Bispingen // BYCEPS (LAN party software platform) // OrgaTalk (LAN party orga board)

powerslide

unregistriert

Re: Fibonacci Zahlen

Montag, 17. Januar 2005, 14:54

5

warum rufst du die funktion sooo oft auf?

ich nehm mal an dass du angibst zur wievielten fibo zahl er zählen soll..

d.h. du fängst automatisch mit 1 an und hörst bei nr x auf

also hasst du ne unterfunktion die a und b übergeben bekommt und einfach beide zahlen addiert solange bis der counter abgelaufen ist
(natürlich musst du vor dem nächsten durchlauf die werte für a und b aktualisieren .. a wird b und b wird das ergebnis der vorherigen rechnung) .. bzw wenn b 1 is dann wird die unterfunktion nicht ausgeführt sondern 1 direkt zurückgegeben.. also dürfte wie yogi das richtig gesagt hat die zahl der aufrufe also die abhängugkeit.. counter-1 sein ..

btw .. kannsu ma deinen quellcode posten?

Draco

God

Re: Fibonacci Zahlen

Montag, 17. Januar 2005, 15:52

6

Quellcode

#include <stdio.h>
#include <stdlib.h>

#define N 20                                     // User Eingabe

int      aufrufe;                                     // Globale Variable zum Aufrufe zählen

 
int fibonacci (int n)
{
    aufrufe++;                                   // Auf globale Variable schreiben (um 1 erhoehen)
      if (n >= 3)                                  // Wenn n groeßer 3, dann weiter...
      {
          return (fibonacci(n-1)+fibonacci(n-2));  //      Rekursionsaufruf
      }
      else
      {
            return 1;
      }
}     
 
 
 
int main(void)
{ 
   int n=N, i; 
   double fib;
    
   printf("*********************************************\n");
   printf(" Aufgabe 8.1\n");
   printf(" -----------\n");
   
   for(i=1; i<=n; i++)
   {
            aufrufe=0;                               // Globale Variable jeweils vor Schleifendurchlauf nullen
            
        fib = fibonacci (i);                     // Funktionsaufruf
            
            printf("\n %3d  %9.1lf  aufgerufen: %5dx", i, fib, aufrufe);
   }
   
   printf("\n*********************************************\n");
   getchar();
   return 0;
}

Bitte keine Kritik am Code, (es sei denn es sind gravierennde Fehler, was ich nicht glaube). Ihr kennt die Aufgabenstellung nicht. Das ganze ist so, wie es da steht, Pflicht.

@Gemini hm das könnte sein, dass des gemeint is

powerslide

unregistriert

Re: Fibonacci Zahlen

Montag, 17. Januar 2005, 16:09

7

das ist so pflicht?
hmm.. ich glaub euer assi wollt euch ärgern..
und die aufrufzahl geht mir immer noch nicht ein!

Y0Gi

God

Re: Fibonacci Zahlen

Montag, 17. Januar 2005, 16:11

8

urgs, jetzt bin ich echt grad etwas verwirrt. meiner momentanen gesinnung nach würde ich folgendes sagen:

anhand deiner ergebnisse hat gemimi recht, weil eben so die abhängigkeit in deinem fall aussieht.
wenn es aber um die rechenschritte geht, ist n-1 aber wohl richtiger.

der unterschied kommt daher, dass du in deiner funktion zwar korrekterweise rekursion benutzt, aber die funktion dort doppelt aufrufst, anstatt den schon errechneten wert wieder zu benutzen. dadurch erhöht sich bei dir auch die laufzeit enorm.

versuch doch mal, zwei variablen in der funktion zu benutzen. so kannst du als zweiten parameter optional die vorhergehende zahl mit übergeben und die gesamte neuerrechnung einer jeden zahl ersparen.

edit: noch was zum code.
explicit is better than implicit. aber in der fibonacci-funktion ist das else eher überflüssig, da bereits mit dem return schon aus der funktion gesprungen wird. aufgrund der klarheit kann man das aber so lassen.
und warum bitte nimmst du für die variable fib den typ double? seit wann gibt's rationale fibonacci-zahlen?

This is my sick nature. – NorthCon // LANresort Bispingen // BYCEPS (LAN party software platform) // OrgaTalk (LAN party orga board)

Draco

God

Re: Fibonacci Zahlen

Montag, 17. Januar 2005, 16:12

9

Mit dem Ding sollte die Rekursion erläutert werden...
Sprich Funktionen die sich selbst aufrufen etc.
Natürlich gibts da einfachere Wege um genau das zu erreihen, was ausgegeben wird.

edit:
ich hab die Lösungen bereits gesehen, das stimmt schon so, auch wenn es totaler quark ist im grunde

Ich kann ja auch nix dafür...

powerslide

unregistriert

Re: Fibonacci Zahlen

Montag, 17. Januar 2005, 16:20

10

die rekursion zu erklären ist anhand von fib auch ok.. aber die rekursion so zu verunstalten dass du sie für jede zahl neu startest ist ja fast schon pervers!

Y0Gi

God

Re: Fibonacci Zahlen

Montag, 17. Januar 2005, 16:22

11

auf jeden fall ist das total unperformant, aber mal so richtig richtig. den kurs hab ich verdrängt, daher rechne ich das jetzt nicht vor. sollte aber auffallen!

in python sieht das als generator-funktion so aus (stammt aus dem cookbook):

	Quellcode
1 2 3 4 5 6 7 8 9 10 11 12	def fib(): x = 0 y = 1 while 1: x, y = y, x + y yield x if __name__ == '__main__': g = fib() for i in range(9): print g.next() print

generatoren sind eine spracheigenschaft von python. wichtig ist, dass yield die sequenzwerte (jeweils den nächsten bei aufruf von .next()) ausgibt. die berechnung, um die es geht, sollte aber klar werden. und dann kommt das auch mit n-1 hin.

This is my sick nature. – NorthCon // LANresort Bispingen // BYCEPS (LAN party software platform) // OrgaTalk (LAN party orga board)

Y0Gi

God

Re: Fibonacci Zahlen

Montag, 17. Januar 2005, 16:37

12

achtung, bewusster doppelpost (damit's denen auffällt, die meinen alten post schon gelesen haben. ja, sowas macht manchmal sinn.).

these: deine funktion ist hochgradig inperformant. wenn die musterlösung in der beziehung wirklich auch so aussieht, dann gute nacht!

schau mal auf http://wikisource.org/wiki/Fibonacci_sequence
da steht, wie man das mit gescheiter und minimaler laufzeit implementieren kann. das beispiel in C zwar ohne separate funktion, aber dafür auch ruhig mal einen blick auf die lösungen in den anderen sprachen werfen.

übrigens fängt die fibonacci-folge nicht selten auch mit 0 (und dann 1) an (wenngleich das bei sich vermehrenden kaninchen wenig sinn machen würde. außer, das erste mutiert irgendwann zum zwitter, aber dann stimmt der rest nicht und der evolutionszeitraum ist wohl zu lang für ein kaninchenleben.).

This is my sick nature. – NorthCon // LANresort Bispingen // BYCEPS (LAN party software platform) // OrgaTalk (LAN party orga board)

Draco

God

Re: Fibonacci Zahlen

Montag, 17. Januar 2005, 16:48

13

nene Musterlösung in dem Sinne gibts nicht.

Aber die Lösung, die ich gesehen habe, nachdem ich selbst hand angelegt habe, sah ziemlich gleich aus. Und diese Lösug hat die nötigen Punkte bekommen.

Rein interessehalber:

a) was bedeutet denn "inperformant" ?
b) wie sähe es optimal aus ?

powerslide

unregistriert

Re: Fibonacci Zahlen

Montag, 17. Januar 2005, 17:06

14

inperformant.. ähm.. keine performance..

lies mal meinen ersten post.. aber ich erklär es nochmal.

die fib folge ist ja..

1 2 3 5 8 13 usw

was du machst.. du fängst immer wieder bei 1 an und berechnest die xte zahl und gibst diese dann aus.. anstatt das jeweilige ergebnis einfach direkt auszugeben..

das frisst halt performance

btw .. ich bin in ner halben stunde @ home..
da kann ich dir was aus meinem algo1 buch abschreiben

Y0Gi

God

Re: Fibonacci Zahlen

Montag, 17. Januar 2005, 17:06

15

a) damit meinte ich "nicht performant". mein duden enthält aber weder "inperformant" noch "unperformant" ("performant" hab ich nicht nachgeschaut, das hab ich aber oft genug gelesen), ich bin geradezu schockiert!

b) wie ich mehrmals geschrieben habe. auf jeden fall so, dass in der rekursion die funktion nur _einmal_ aufgerufen wird (s. wikipedia-code) und nicht mehrmals. und DAS wäre mit sicherheit kein gutes beispiel zur demonstration von rekursion.

powerslide: die "große" reihe ist 0, 1, 1, 2, 3, 5, ... (der vollständigkeit halber), aber die bzw. speziell den anfang kann man glaube ich gar nicht mit nem simplen algorithmus produzieren.

This is my sick nature. – NorthCon // LANresort Bispingen // BYCEPS (LAN party software platform) // OrgaTalk (LAN party orga board)

powerslide

unregistriert

Re: Fibonacci Zahlen

Montag, 17. Januar 2005, 17:10

16

@ yogi. ja ich weiss.. ich habs nur bissel abgekürzt

Draco

God

Re: Fibonacci Zahlen

Dienstag, 18. Januar 2005, 12:40

17

thx aber hab meine Punkte heute bekommen. 10 von 10... was solls Rest ist mir egal höhö

Fürn Mechatroniker reicht das. Für alles andere gibts Informatiker

Y0Gi

God

Re: Fibonacci Zahlen

Dienstag, 18. Januar 2005, 13:49

18

aaaaarm, ganz aaaaaaaaarm! solche leute wie euch würd ich als firmenleiter dann auch ohne wimpernzucken nach timbuktu outsourcen

tschüß, wirtschaftsstandort deutschland

aber ma im ernst: wenn ihr das nicht vernünftig beigebracht bekommt, dann ist das echt traurig und ich würd mich da mal gescheit beschweren. dann lieber nix beigebracht bekommen als was falsches bzw. im falschen glauben gelassen zu werden. und schlechte software gibt's wahrlich schon mehr als genug.

sowas regt mich echt auf.

This is my sick nature. – NorthCon // LANresort Bispingen // BYCEPS (LAN party software platform) // OrgaTalk (LAN party orga board)

Draco

God

Re: Fibonacci Zahlen

Dienstag, 18. Januar 2005, 15:11

19

Zitat von »Y0Gi«

aaaaarm, ganz aaaaaaaaarm! solche leute wie euch würd ich als firmenleiter dann auch ohne wimpernzucken nach timbuktu outsourcen
tschüß, wirtschaftsstandort deutschland

Nuja, wenn du als firmenleiter nen Mechatroniker einstellst, der dann losprogrammieren soll, hast du selbst was falsch gemacht

Nuja, ich persönlich hab schon ein wenig mehr Interesse am Programmieren als der Durchschnitts-Mechatronik-Student.
Daher würd ich persönlich das auch gern ein klein bisschen intensiver erklärt bekommen und lernen.
Ich merks ja daran, wie intensiv und lustvoll ich an verschiedene Aufgaben ran geh. Lieber Programmieren, als Technische Mechanik, denk ich dann

Das geht aber wiederum nicht so weit, dass ich Informatik studieren wollen würde.
Der Studiengang is ja modular aufgebaut. Nuja, und momentan durchlaufen wir halt auch die Informatik-Etage (sinngemäß).
Finds ein wenig nervig, dass sich die Betreuer (Dipl. Inf. ala Laborassistenten) immer aufs neue über uns lustig machen und uns belächeln ala "ihr braucht nich mehr zu können, ihr checkt das sowieso nicht"

Y0Gi

God

Re: Fibonacci Zahlen

Dienstag, 18. Januar 2005, 15:50

20

haste denn jetzt wenigstens verstanden, was an deinem code schlecht war?

This is my sick nature. – NorthCon // LANresort Bispingen // BYCEPS (LAN party software platform) // OrgaTalk (LAN party orga board)