Thread: Fibonacci sequence

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    7

    Fibonacci sequence

    Ok, I have to create a program that prints whether a number is in the Fibonacci sequence. This is what i have so far, but i could use some help:

    Code:
    #include <iostream>
    #include <iomanip>
    using namespace std;
    int main (void)
    {
    int valin, n=0;
    cout << "Input a positive integer: " << endl;
    cin>> valin;
    if (valin==0 || valin==1)
    cout << "The number" << valin << "is in the Fibonacci sequence." << endl;
    else if (valin==(n-1)+(n-2))
    cout << "The number" << valin << "is in the Fibonacci sequence." << endl;
    else
    cout << "The number"  << valin << "in not in the Fibonacci sequence." << endl;
    return 0;
    }
    I don't know if this is the best way to go about this problem. Also, is there a way for me to use "bool found=false;" or "char found='N';"
    any help would be appreciated, thanks

  2. #2
    Registered User
    Join Date
    Nov 2002
    Posts
    1,109
    have you learned about loops or recursion yet?

  3. #3
    Registered User
    Join Date
    Sep 2003
    Posts
    7
    yes, I've learned for and while loops, but do not totally understand them.
    Last edited by girliegti; 09-30-2003 at 08:01 PM.

  4. #4
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    Have you read the tutorials on them here?
    Away.

  5. #5
    Registered User Moni's Avatar
    Join Date
    Oct 2002
    Location
    Dhaka, Bangladesh.
    Posts
    104
    Watch this ...

    Code:
    long fib(int n)
    { if (n < 2) return n;         //  basis
      return fib(n-1) + fib(n-2);  // recursion
    }
    We all are the components of a huge program...... the programmer is always debugging us with His debugger.

  6. #6
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    Originally posted by alpha
    have you learned about loops or recursion yet?
    I would use a for loop instead of recursion. Recursion will give an exponential run time, versus linear for the for structure.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  7. #7
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    Originally posted by Moni
    Watch this ...
    Code:
    long fib(int n)
    { if (n < 2) return n;         //  basis
      return fib(n-1) + fib(n-2);  // recursion
    }
    or this:
    Code:
    int fib( int n )     //assume  n >= 0 
    {
          if ( n <= 1 ) { return 0; }
    
          int f0 = 0;
          int f1 = 1;
          int f2;
    
          for( int i = 2; i <= n; i++ ){
               f2 = f1 + f0; 
               f0 = f1;
               f1 = f2;
          }
          return f2;
    }
    recursion here is innaficient (top code), as it results in exponential time. My code results in linear time...haha...good ol' CS discrete Mathematics.

    axon
    Last edited by axon; 09-30-2003 at 09:25 PM.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  8. #8
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Restating axon's point:

    As a general rule, recursive solutions are elegant and fun to show off. Iterative solutions, on the other hand, are inelegant, but much more efficient in terms of both time and memory.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  9. #9
    Registered User Moni's Avatar
    Join Date
    Oct 2002
    Location
    Dhaka, Bangladesh.
    Posts
    104
    At least Recursive solutions look small and easy to understand

    But of course Iterative solutions are very good with the BIG O Notations
    We all are the components of a huge program...... the programmer is always debugging us with His debugger.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. fibonacci sequence
    By cph in forum C Programming
    Replies: 57
    Last Post: 04-30-2009, 07:17 AM
  2. n-th element of the fibonacci sequence
    By me001 in forum C Programming
    Replies: 22
    Last Post: 09-24-2008, 03:27 AM
  3. Fibonacci Sequence
    By Dogmasur in forum C Programming
    Replies: 15
    Last Post: 08-10-2008, 07:55 AM
  4. Immediate programming help! Please!
    By xMEGANx in forum C++ Programming
    Replies: 6
    Last Post: 02-20-2008, 12:52 PM
  5. Fibonacci sequence output statement
    By chocha7 in forum C++ Programming
    Replies: 10
    Last Post: 11-18-2004, 11:04 PM