Fibonnaci

Discussion in 'C Programming' started by MARQUITOS51, Dec 9, 2005.

  1. MARQUITOS51

    MARQUITOS51 Guest

    Im trying to find any code in C developed to calculate the fibonnacci
    series with or without functions. I need a code example so I can
    studied and see how it works.
     
    MARQUITOS51, Dec 9, 2005
    #1
    1. Advertising

  2. MARQUITOS51

    Jordan Abel Guest

    On 2005-12-09, MARQUITOS51 <> wrote:
    > Im trying to find any code in C developed to calculate the fibonnacci
    > series with or without functions. I need a code example so I can
    > studied and see how it works.


    If you're cheating on homework, ask for something less obvious than code
    examples.

    #include <math.h>

    double fibon(double n) {
    return (
    pow(1.6180339887498948482045868343656381177203L,n)
    -
    pow(-.6180339887498948482045868343656381177203L,n)
    )/2.2360679774997896964091736687312762354406L;
    }

    Good luck explaining to your instructor how this works.

    [If you're not, you'll need to give people more to work with to show
    that you understand the problem and also give your best effort and show
    what code you've tried that doesn't work]
     
    Jordan Abel, Dec 9, 2005
    #2
    1. Advertising

  3. MARQUITOS51 said:

    > Im trying to find any code in C developed to calculate the fibonnacci
    > series with or without functions. I need a code example so I can
    > studied and see how it works.


    The Fibonacci series can be defined as f(0) = 0, f(1) = 1, and f(n) = f(n -
    1) + f(n - 2) for n > 1.

    So it goes like this: 0, 1, 1, 2, 3, 5, 8, 13, etc.

    Think about how you would implement this recursively. Hint: look at the
    above definition.

    Write it. See how slow it is? Find out why. Hint: use printf.

    Now think about how you could make it a lot faster. Hint: think about
    arrays.

    Now see if you can avoid the need for an array by writing this iteratively
    instead of recursively.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at above domain (but drop the www, obviously)
     
    Richard Heathfield, Dec 9, 2005
    #3
  4. MARQUITOS51

    Suman Guest

    Richard Heathfield wrote:
    > MARQUITOS51 said:
    >
    > > Im trying to find any code in C developed to calculate the fibonnacci
    > > series with or without functions. I need a code example so I can
    > > studied and see how it works.

    >

    [...]
    > Now see if you can avoid the need for an array by writing this iteratively
    > instead of recursively.


    Do you mean Q-Matrix? If not, that's one more thing the OP might want
    to check
    out.
     
    Suman, Dec 9, 2005
    #4
  5. MARQUITOS51

    Jordan Abel Guest

    On 2005-12-09, Richard Heathfield <> wrote:
    > Write it. See how slow it is? Find out why. Hint: use printf.
    >
    > Now think about how you could make it a lot faster. Hint: think about
    > arrays.


    All that's needed to change the worst-case performance to linear is a
    two-element cache.
     
    Jordan Abel, Dec 9, 2005
    #5
  6. MARQUITOS51

    buda Guest

    "Jordan Abel" <> wrote in message
    news:...
    > On 2005-12-09, Richard Heathfield <> wrote:
    >> Write it. See how slow it is? Find out why. Hint: use printf.
    >>
    >> Now think about how you could make it a lot faster. Hint: think about
    >> arrays.

    >
    > All that's needed to change the worst-case performance to linear is a
    > two-element cache.


    I think Richard tryed to explain the process... how to move from a top down,
    recursion-based solution to a memoized recursion, and then to a bottom-up
    solution (building that same array that was used for memoization from 0 to
    n). This is infact the best you can do if you need to keep all of the first
    n Fibonacci numbers - it is unclear if the OP needs this, or he just wants
    to write them out. Also, your comment is covered in the last "idea" Richard
    gives.
     
    buda, Dec 9, 2005
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.

Share This Page