Fibonacci

This is a discussion on Fibonacci within the C Programming forums, part of the General Programming Boards category; Originally Posted by liyanhong My English is poor, so I post code directly Code: #include <stdio.h> int main(void) { int ...

  1. #16
    Registered User
    Join Date
    Jun 2010
    Posts
    45
    Quote Originally Posted by liyanhong View Post
    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?

  2. #17
    Registered User
    Join Date
    Nov 2008
    Location
    China
    Posts
    17
    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

  3. #18
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Posting solutions directly is a bad way of teaching anyone anything.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  4. #19
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by claudiu View Post
    Posting solutions directly is a bad way of teaching anyone anything.
    Apart from not knowing whether saria777 has covered arrays yet, saria777 looks to have worked out about as much as liyanhong posted anyway, but without unnecessarily using a fixed-sized array, which incidentally is too small (as is the data type).

    As for the bugs:
    Take a closer look at laserlight's first post. You didn't follow the advice fully.
    Check the places your brackets are. Indent the code properly and make sure everything is either inside or outside of where it should be.
    Don't forget to actually return something.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #20
    Registered User
    Join Date
    May 2010
    Location
    Italy
    Posts
    5
    Quote Originally Posted by claudiu View Post
    Posting solutions directly is a bad way of teaching anyone anything.

    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!!
    Last edited by Zeldic; 06-14-2010 at 06:14 AM. Reason: An error

  6. #21
    Registered User
    Join Date
    Nov 2008
    Location
    China
    Posts
    17
    Quote Originally Posted by Zeldic View Post
    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.

  7. #22
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,256
    saria777, concerning the range of numbers that you are supposed to accommodate: check with your teacher. If you are allowed to compile with respect to the 1999 edition of the C standard, then you have access to unsigned long long, which would allow you to handle F(93). But F(100) really is beyond reach unless you use a non-standard bignum library, or code your own (which would be an entirely different project, and in some ways more difficult than what you are supposed to solve here). Otherwise, your teacher may tell you that this was an oversight, and perhaps you only need to deal with at most F(47).
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #23
    Registered User
    Join Date
    Jun 2010
    Posts
    6
    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?

  9. #24
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    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);
    Last edited by nonoob; 06-14-2010 at 03:29 PM.

  10. #25
    Registered User
    Join Date
    Jun 2010
    Posts
    6
    Quote Originally Posted by nonoob View Post
    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!

  11. #26
    Registered User
    Join Date
    Nov 2009
    Location
    Italy
    Posts
    65
    Quote Originally Posted by iMalc View Post
    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

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 12-25-2009, 01:22 AM
  2. fibonacci prime
    By dbzx in forum C Programming
    Replies: 5
    Last Post: 04-17-2009, 12:13 PM
  3. fibonacci using recursion?
    By n3cr0_l0rd in forum C Programming
    Replies: 12
    Last Post: 02-25-2009, 08:49 AM
  4. Recursive Fibonacci, some help needed
    By cwafavre in forum C Programming
    Replies: 8
    Last Post: 11-04-2007, 02:20 PM
  5. void fibonacci() - Is This Possible?
    By Not Yet in forum C++ Programming
    Replies: 3
    Last Post: 11-25-2002, 10:24 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21