Home » C++ programs » C++ Most popular & searched programs

# C++ program to find Fibonacci number using different methods

Learn: What to **find fibonacci number using different methods**, here you will find multiple methods to find the fibonacci number using **C++ programs**.

Submitted by Shubham Singh Rajawat, on June 23, 2017

**Fibonacci numbers are the numbers having a specific sequential pattern.**

**0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34, ...** this type of sequence follow a mathematical pattern.

F_{n} = F_{n-1} + F_{n-2} , where F_{0} = 0 , F_{1} = 1

Where **n** = 2,3,4,5,6,7,8, ...

### 1. Using recursion method

In recursion a lot work is done as it repeatedly calculates the number and solves same case more than one time.

**For Example:**

**As it calculates Fibo(1) & Fibo(0) multiple time **

**Consider the program:**

#include<iostream> using namespace std; int Fib(int n) { if(n<=1) return n; return Fib(n-1)+Fib(n-2); /*recusively add the numbers*/ } int main() { int n; /*position of the element starting from 0...n*/ cout<<"Enter the number :"; cin>>n; cout<<"Number at "<<n<<"th place is "<<Fib(n)<<endl; return 0; }

Output

Enter the number :10 Number at 10th place is 55

### 2. Using Dynamic programming method

A dynamic programming algorithm remembers the past result and uses them to find new result means it solve complex problems by breaking it down into a collection of simpler subproblems, then solving each of those subproblems only once ,and storing their solution for future use instead of recomputing their solutions again.

**Algorithm:**

Fib(n) if n=0 return 0 else prev_Fib=0,curr_Fib=1 repeat n-1 times /*if n=0 it will skip*/ next_Fib=prev_Fib+curr_Fib prev_Fib=curr_Fib curr_Fib=next_Fib return curr_Fib

**Consider the program:**

#include<iostream> using namespace std; int main() { int n; cout<<"Enter the number :"; cin>>n; /*position of the element starting from 0...n*/ int Fibo[n+1],i; Fibo[0]=0,Fibo[1]=1; for(i=2;i<=n;i++) { Fibo[i]=Fibo[i-1]+Fibo[i-2]; /*It will store the sum of previous two elements */ } cout<<"Number at "<<n<<"th place is "<<Fibo[n]<<endl; return 0; }

Output

Enter the number :10 Number at 10th place is 55

### 3. Without using array

Well it is the easiest way to calculate Fibonacci number as we just have to add two previous numbers to calculate next number.

**Consider the program:**

#include<iostream> using namespace std; int Fib(int n) { if(n==0) return 0; else { int prev_Fib=0,curr_Fib=1,next_Fib; if(n==0) return n; while(n>=2) { next_Fib=prev_Fib+curr_Fib; prev_Fib=curr_Fib; curr_Fib=next_Fib; n--; } return curr_Fib; } } int main() { int n; /*position of the element starting from 0...n*/ cout<<"Enter the number :"; cin>>n; cout<<"Number at "<<n<<"th place is "<<Fib(n)<<endl; return 0; }

Output

Enter the number :10 Number at 10th place is 55

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.

Learn PCB Designing: PCB DESIGNING TUTORIAL