fibonacci στη C

[antemar]

Έχω μια απορία σχετικά με το τί επιστρέφει η κλήση της fibonacci. Συγκεκριμένα:

 

Ποια τιμή επιστρέφει η κλήση Fibonacci2(9);

int Fibonacci2(int N) {

int i, a,b,c;

if (N<=0)

return 0;

a=0;

b=c=1;

for(i=2;i<=N;i++) {

c=b+a;

a=b;

b=c;

}

return c;

Η ΣΩΣΤΗ ΑΠΑΝΤΗΣΗ ΕΙΝΑΙ 34. ΠΩΣ ΠΡΟΚΥΠΤΕΙ ΟΜΩΣ;

-----------------------------------------------------------------

ΕΧΩ ΚΑΙ ΜΙΑ ΔΕΥΤΕΡΗ ΕΡΩΤΗΣΗ (ΑΣΧΕΤΗ ΜΕ Fibonacci):

Έστω ο παρακάτω πίνακας:

int testarray[3][2][2] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

Γιατί η τιμή που περιέχεται στη μεταβλητή testarray[2][1][0] είναι το 11;

[system]

Για την δευτερη ερωτηση αν σκεφτεις συνειρμικα δεν θα ναι καπως ετσι?

 

testarray[0][0][0] =1

testarray[0][0][1] =2

testarray[0][1][0] =3

testarray[0][1][1] =4

....

....

testarray[2][1][0]=11

testarray[2][1][1]=12

[antemar]

Ωραία και πώς προκύπτει το 11?

[Dr.Fuzzy]

Για τους αριθμους Fibonacci ισχυει:

 

Fn = {0 if n=0; 1 if n=1; Fn-1+Fn-2 if n>1}

 

Δηλαδη καθε αριθμος Fibonacci προκυπτει ως το αθροισμα των 2 προηγουμενων αριθμων Fibonacci, εκτος απο τις δυο αρχικες τιμες.

 

Πολυ σωστα λοιπον ο αριθμος Fibonacci του 9 ειναι το 34.

 

[antemar]

Την λογική των αριθμών Fibonacci την γνωρίζω.

Εδώ όμως υπάρχει ένα for που επιστρέφει την τιμή του c.

Με άλλα λόγια, από που προκύπτει αυτό το 34?

[parsifal]

Την λογική των αριθμών Fibonacci την γνωρίζω.

Εδώ όμως υπάρχει ένα for που επιστρέφει την τιμή του c.

Με άλλα λόγια, από που προκύπτει αυτό το 34?

 

Μα ο κώδικας είναι self-explanatory, πρόκειται για το μη αναδρομικό αλγόριθμο Fibonacci: Σε κάθε επανάληψη του βρόχου, το b παριστάνει τον (i-1)-οστό Fibonacci και το a τον (i-2)-οστό. Αφού υπολογίσθεί εκ νέου το c (δηλαδή, παριστάνει πλέον τον i-οστό Fibonacci), απλά ενημερώνεις τα a και b ώστε να περιέχουν την τιμή του κατά μία μονάδα μεγαλύτερου Fibonacci, για να δουλέψουν σωστά οι υπολογισμοί και στο επόμενο iteration κ.ο.κ.

[antemar]

Δεν ξέρω εάν το έκανα σωστά αλλά βρήκα 34. Λοιπόν έχω δεδομένο ότι F(0)=0 & F(1)=1.

f9=f8+f7=f7+f6+f6+f5=f6+f5+f5+f4+f5+f4+f4+f3=....

[system]

Ωραία και πώς προκύπτει το 11?

 

Η γραμμή που εχεις δωσει είναι απλη αναθεση τιμων με την σειρα που βρισκονται μεσα στις αγκυλες σε εναν τρισδιαστατο πινακα. Και θα δωθουν με την σειρα που σου εγραψα παραπανω. Επομενως για την προτελευταια αναθεση θα δεις οτι testarray[2][1][0]=11

[Dr.Fuzzy]

Δεν ξέρω εάν το έκανα σωστά αλλά βρήκα 34. Λοιπόν έχω δεδομένο ότι F(0)=0 & F(1)=1.

f9=f8+f7=f7+f6+f6+f5=f6+f5+f5+f4+f5+f4+f4+f3=....

 

Σωστα το εκανες.

 

[sgoll]

ΣΤΗΝ ΑΚΟΛΟΥΘΙΑ FIBONACCI ΤΟ ΚΑΘΕ ΝΟΥΜΕΡΟ ΕΙΝΑΙ ΤΟ ΑΘΡΟΙΣΜΑ ΤΩΝ ΔΥΟ ΠΡΟΗΓΟΥΜΕΝΩΝ.

 

ΣΧΕΤΙΚΑ http://en.wikipedia.org/wiki/Fibonacci_number