Thread: Fibonacci

Originally Posted by liyanhong

My English is poor, so I post code directly

Code:

#include <stdio.h>  

int main(void)  

{  

    int F[46];  

    int i;  

    F[0] = 0; F[1] = 1;  

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

	F[i] = F[i-1] + F[i-2];  

    printf("%d\n", F[8]);  

    return 0;  

}

what is 'N'?

do you mean 46?

Code:

#include <stdio.h>  
#define N 8

int main(void)  

{  

    int F[46] = {0, 1};  

    int i;  

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

	F[i] = F[i-1] + F[i-2];  

    printf("%d\n", F[N]);  

    return 0;  

}


//I'm sorry, I mean 'F[8]' ,  heihei

Originally Posted by Zeldic

Right what you said!!


I think the best solution is to implement the Fibonacci algorithm iteratively, as you have already said. Infact it takes much less memory and time (on an input n = 58, F(58) with the recursion takes ≈ 4 hours, while iteratively only ≈ 0.7 millionths of a second)!

Here my pseudocode algorithm for Fibonacci, using cycles instead of recursion for calculating the n-th Fibonacci number :

Algorithm Fibonacci4 (int n) --> int

1. a <-- 1, b <-- 1

2. for i = 3 to n do
3. c <-- a + b
4. a <-- b
5. b <-- c

6. return b.


I hope it could be of a little help! Bye!!

Actually, F(58) will beyond the 'int' can store.

alrighty. I've got it to compile /finally/. And yes, when it gets so large it begins showing negative numbers.

Code:

#include <stdio.h>

int Fibonacci (int n);

int main ()
{

long result;
long number;


printf("Enter an integer: ");
scanf("%ld", &number);
result=Fibonacci(number);
printf("Fibonacci(%ld)=%ld/n",number,result);
return 0;
}

 int Fibonacci (int n)
{

    int previous= 0;
    int result =1;
    int i;
    for (i=2; i <=n; ++i)
    {
     int const sum=result + previous;
     previous= result;
     result = sum;
  }

 return result;
}

Also, it's showing them as F5 being 5, F6 being 8, F7 being 13, F8 being 21, when it should be F5 being 8, F6 being 13, F7 being 21, etc. What would I need to make my int previous and result and i= to make it display the way I want?

Originally Posted by nonoob

Your solution agrees with this Fibonacci table here:
PlanetMath: list of Fibonacci numbers

Your teacher has the sequence advanced by one... so if your teacher wanted 21 as an answer for input 7, just add 1 to user input and proceed.
Or call

Code:

Fibonacci(number + 1);

Thanks!

Originally Posted by iMalc

If you're suggesting what I think you're suggesting, then I hope that was a joke.
The naieve recursive imlementation of it takes literally hours to calculate a mere fib(50). Reference
Besides, it says you must use loops.

Oh, I didn't notice that he had to find large fibonacci numbers, i'm sorry, in this case the only solution is to use strings and int arrays to store big numbers, I made an algorithm to find fibonacci numbers up to 5000 once, my solution was to precalculate into a matrix all fibonacci numbers untill n = 5000 by doing string addition