Fibonacci series in C++

Question

#include <iostream>

using namespace std;

int main()
{
    int num1 = 0;
    int num2 = 1;
    int num_temp;
    int num_next = 1;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        cout << num_next << "  ";
        num_next = num1 + num2;
        num1 = num2;
        num_temp = num2;
        num2 = num_next - num1;
        num1 = num_temp;
    }
    return 0;
}

I have to output the first "n" fibonacci numbers however I think there is some problem in logic.. I can't find out what am I doing wrong. The first 3 or 4 elements are correct but then a problem occurs...

EXPECTED:
For n=9

0, 1, 1, 2, 3, 5, 8, 13, 21

Actual:

1 1 1 1 1 1 1 1 1

Answer 1

#include <iostream>

using namespace std;

int main()
{
    int num1 = 0;
    int num2 = 1;
    int num_temp;
    int num_next = 1;
    int n;
    cin >> n;
    if (n>=1)
        cout << 0 << " ";
    if (n>=2)
        cout << 1 << " ";
    for (int i = 0; i < n-2; i++){
        num_next = num1 + num2;
        cout << num_next << " ";
        num1 = num2;
        num2 = num_next;
    }
    cout << endl;
    return 0;
}

Answer 2

Try this instead. It's a bit of a different take but will get you there just the same.

#include <iostream>

using namespace std;

int main()
{
   int input(0), Alpha(0), Beta(1), Total(1);  
   cout << "Please input a top number: "; 
   cin >> input; 

   for(int i = 0; i <= input; i++)
   {
      cout << Total << endl; 
      Total = Alpha + Beta; 
      Alpha = Beta;
      Beta = Total; 
   }
} 

Answer 3

The Fibonacci Sequence is {0, 1, 1, 2, 3, ... N - 1, N, 2N - 1}.

In order to implement it, you need to have a N - 2 variable, and an N - 1 variable so that you can calculate N = (N - 2) + (N - 1):

unsigned int count = 0;
std::cin >> count;
// assume count >= 2
unsigned int prev2 = 0;
unsigned int prev1 = 1;

std::cout << prev2 << " " << prev1 << " ";
for (unsigned int i = 2; i < count; ++i)
{
    unsigned int current = prev2 + prev1;
    prev2 = prev1;
    std::cout << current << " ";
    prev1 = current; 
}
std::cout << std::endl;

Answer 4

This is my version.

It's more or less same as previous samples, but I wanted to show the use of ring buffer.

// Study for algorithm that counts n:th fibonacci number
// Fibonacci[1] == 1 and Fibonacci[2] == 1 (and Fibonacci[0] == 0)
// Fibonacci[n] = Fibonacci[n-1] + Fibonacci[n-2]                      

#include <cstdio>
#include <iostream>
#include <cstdlib>

int main(int argc, const char* argv[])
{

  // not counting trivial Fibonacci[0]
  if(argc != 2 || atoi(argv[1]) < 1){
    std::cout << "You must provide one argument. Integer > 0" << std::endl;
    return EXIT_SUCCESS;
  }

  // ring buffer to store previous two fibonacci numbers, index it with  [i%2]
  // seeded with Fibonacci[1] and Fibonacci[2]
  // if you want to count really big fibonacci numbers, you have to make your own type for
  // buffer variable
  // this type overflows after [93] with my macbook
  unsigned long long int buffer[2]={ 1, 1 };

  // n:th Fibonacci                                                             
  unsigned int fn = atoi(argv[1]);

  // count loop is used if seeked fibonacci number is gt 2                      
  if(fn > 2){
    for(unsigned int i = 2; i < fn; ++i){                                
      buffer[i%2] = buffer[(i-1)%2] + buffer[(i-2)%2];
    }
  }

  // Result will be send to cout                                                
  std::cout << "Fibonacci[" << fn << "] is " << buffer[(fn-1)%2] << std::endl;
  return EXIT_SUCCESS;
}

Answer 5

#include <iostream>
using std::cout; using std::cin;

int main()
{
    unsigned int a=0u, b=1u, n;//assuming n is a positive number.
                                //otherwise make it int instead of unsigned
                                //and check if it's negative
    cin >> n;

    if(n==0)
       {return 0;}
    if(n==1)
       {cout << a; return 0;}
    cout << a << " " << b << " ";
    for(unsigned int i=2u ; i<n; i++)
    {
       b = a + b;
       a = b - a;
       cout << b << " ";
    }
    return 0;
}

It puts the next value in 'b' by adding the last two values together. 'a' then gets the previous b value. assume a = 3 and b = 5. Then the new b will become 8, and 'a' will become 5. This is because it always sums the last two numbers to get the result of the next number. The next operation will sum 5 (current a) and 8(current b) and so on...

Answer 6

#include<iostream.h>
#include<conio.h>

void main()
{ 
   clrscr();
   int arr[50],n,i;
   cout<<"Enter the no. of elements to be printed in fibonacci series : ";
   cin>>n;
   arr[0]=0;arr[1]=1;
   for(i=2;i<n;i++)
   { 
      arr[i]=arr[i-1]+arr[i-2];         
   }
   cout<<"\nThe fibonacii series is : "<<endl;
   for(i=0;i<n;i++)
   {
      cout<<arr[i]<<"\t";  
   }
   getch();
}

Answer 7

Stack overflow is, of course, a limitation of the recursive version. If that is not a problem, you may also wish to consider a templated version of recursive Fibonacci.

#include <iostream>

template <int N> int Fib(){ return Fib<N-1>() + Fib<N-2>(); }
template <> int Fib<1>() { return 1; }
template <> int Fib<0>() { return 1; }

using namespace std;
int main()
{
  // For the 10th Fibbonacci number...
  cout << Fib<10>() << endl;
  return 0;
}

Answer 8

Well I have been looking for some recursive solution to do the same task, Mostly what people do is, they write a recursive function for finding nth Fibonacci number, and then in the main program, they run a loop n times, and call this recursive function with values 1 to n to get all the n Fibonacci numbers and print them, which is a big overhead.

Here is a solution which does the same task but it calls recursive function only once for getting all up to n Fibonacci numbers, and stores them in an array, and then prints. Which is ((n-1)*(recursive call's overhead)) times faster than the one I mentioned earlier. Thumbs up if you find it helping :)

#include<iostream>
using namespace std;
int *arr;
int iter = 0;
int len;
int returnValue;
void exist(int num, int arr[] ) /* this function checks if the Fibonacci number that recursive function have calcuated is already in the array or not, mean if it is already calculated by some other recursive call*/
{
    bool checkExistance = false; /* if this is true, means this Fibonacci number is already calculated and saved in array, so do not save it again*/
    returnValue = num;
    for (int i = 0; i< len; i++)
    {
        if(arr[i]==num)
        {
            checkExistance = true;
            break;
        }
    }
    if(!checkExistance)
    {
        arr[iter]=num;
        iter++;
    }
}
int fibonacci(int n)
{   
    if (n==1)
    {
        exist(1,arr);
        return 1;
    }   
    else if (n==2)
    {
        exist(1,arr);
        return 1;
    }
    else
    {
        exist((fibonacci(n-1)+fibonacci(n-2)),arr);
        return returnValue;
    }
}
int main()
{
    int n;
    cout<<"Enter the number of Fibonacci you want to print: ";
    cin>>n;
    len = n;
    arr = new int[n];
    fibonacci(n);
    arr[n-1] = 1;
    cout<<"1:\t"<<arr[n-1]<<endl;
    for (int i = 0; i< len-1; i++)
    {
        cout<<i+2<<":\t"<<arr[i]<<endl;
    }
    return 0;
}

Answer 9

#include <iostream>

using namespace std;

int main()

{

    int num1 = 0, num2 = 1 , num_next = 1, n;

        cout << "enter a number: \n";
        cin >> n;
        //for when a negative value is given
        while(n < 0)
        {
            cout << "ERROR\n";
            cin >> n;
         }
         //when any positive number (above 1 is given)
        if (n > 0)
        {
            //to give the value of 0 without ruining the loop
            cout << num1 << " ";
            for (int i = 0; i < n; i++)
            {
                //the Fibonacci loop
                cout << num_next << " ";
                num_next = num1 + num2;
                num1 = num2;
                num2 = num_next;
            }
        }
        //for when 0 is the given value
        else if (n == 0)
            cout << n << " ";
    return 0;
}

Answer 10

Here's a solution without a temp variable:

#include <iostream>
using namespace std;

int main()
{
  int n0 = 0;
  int n1 = 1;
  int n;

  cout << "Prints first N in Fibonacci series. Please enter a number for N:  ";
  cin >> n;

  for(int i = 0; i < n; i++) {
    cout << n0 << " ";
    n1 = n0 + n1;
    n0 = n1 - n0;
  }
}

Also a (tail) recursive solution:

#include <iostream>
using namespace std;

void fib(int n, int n0, int n1) {
 if(n <= 0) {
    return;
  } else {
    cout << n0 << " ";
    fib(n-1, n1, n0 + n1);
  }
}

int main()
{
  int n;

  cout << "Prints first N in Fibonacci series. Please enter a number for N: ";
  cin >> n;

  fib(n, 0, 1);
}

Answer 11

/* Author: Eric Gitangu
   Date: 07/29/2015
   This program spits out the fibionacci sequence for the range of 32-bit numbers
   Assumption: all values are +ve ; unsigned int works here
*/
#include <iostream>
#include <math.h>
#define N pow(2.0,31.0)

using namespace std;

void fibionacci(unsigned int &fib, unsigned int &prevfib){
    int temp = prevfib;
    prevfib = fib;
    fib += temp;
}
void main(){
    int count = 0;
    unsigned int fib = 0u, prev = 1u;

    while(fib < N){
        if( fib ==0 ){
            fib = 0;
            cout<<" "<< fib++ <<" \n ";
            continue;
        }
        if( fib == 1 && count++ < 2 ){
            fib = 1;
            cout<< fib <<" \n ";
            continue;
        }
        fibionacci(fib, prev);
        cout<< fib <<" \n ";
    }
}

Answer 12

So... Heres a solution to "If you want a specific sequence of the Fib."

#include <iostream>
using namespace std;
int fibonacciSeq(int k)
{
    int num1=1;
    int num2=1;
    int count;
    for(int i=0; i<k; i++)
    {
        if(i==1)
        count=1;
        else
        {
            count=num1+num2;
            num1=num2;
            num2=count;
        }
    }
    return count;
}

Answer 13

How about another look at a recursive solution:

void fibonacci(int n1, int n2, int numCount)
{
  --numCount;

  if (numCount > 0)
  {
    cout << n1 << ", ";
    fibonacci(n2, n1 + n2, numCount);
  }
  else
    cout << n1 << endl;
}

Then you could call it:

enterint fNum;
cout << "Enter a non negative number to print output fibonacci sequence: ";
cin >> fNum;

fibonacci(0, 1, fNum);

Example of the output:

Answer 14

Concise version:

int n, a{0}, b{1};
std::cin >> n;
while (n-- > 0) {
    std::cout << a << " ";
    std::tie(a, b) = std::make_tuple(b, a + b);
}

Answer 15

You can write a code generating a Fibonacci series avoiding the if-else statement that prints zero and one, avoiding printing them outside the loop and avoiding the 'temp' integer. You can do it by initializing the 'first' and 'second' variables with -1 and 1, so the sum between them will give you 0, which is the first organ of the series, and the loop will do the rest of the job.

#include <iostream>

using namespace std;
int main()
{
    int num, a = -1, b = 1; 
    cout << "enter a number:" << endl;
    cin >> num;
    for (int i = 0 ; i <= num ; i++ ) 
    {
    b += a;             
    cout << b << " "; 
    a = b - a;
    }
    cout << endl;
    return 0;
}

Answer 16

Fibonacci with do...while loop.

#include <iostream>
using namespace std;

int main() {

    int n;
    cout << "Input fibonacci sequence length: ";
    cin >> n;

    int i = 1, fib0, fib1, fib2, sum = 0;
    fib0 = 0;
    fib1 = 1;
    fib2 = 1;

    do {
        i++;
        cout << fib0 << "  ";
        sum = sum + fib0;
        fib1 = fib2;
        fib2 = fib0;
        fib0 = fib1 + fib2;
    }
    while (i <= n);
    cout << endl << endl;
    cout << "Sum of numbers are: " << sum << endl;

    return 0;
}