Quick links
Latest articles
Internship
Members
New...
Algorithms
Discrete Mathematics
Big data
Languages
C
C++
C++ STL
Java
Data Structure
C#.Net
Android
Kotlin
SQL
Web
PHP
Python
JavaScript
CSS
Ajax
Node.js
Web prog.
Programs
C
C++
DS
Java
C#
Python
Aptitude
C
C++
Java
DBMS
Interview
C
Embedded C
Java
SEO
HR
CS Subjects
CS Basics
O.S.
Networks
DBMS
Embedded Systems
Cloud Computing
Machine learning
CS Organizations
Linux
DOS
More...
Articles
Puzzles
News/Updates

Home » Algorithms

Find the Nth Fibonacci number | C++



Here, we are going to learn how to find the Nth Fibonacci number using Dynamic programming in C++.
Submitted by Ritik Aggarwal, on November 07, 2018

Problem: Compute the Nth Fibonacci number

You are given a number N. You have to find the Nth Fibonacci number. 0th Fibonacci number is 0 and first Fibonacci number is 1.

Sample inputs:

    N = 0, answer is 0
    N = 1, answer is 1
    N = 5, answer is 5

Basic Approach: Recursive approach

int fibonacci(int N){
    if(N == 0 || N == 1){
        return N;
    }
    int ans = fibonacci(N-1) + fibonacci(N - 2);
    return ans;
}

Now provided above is the basic recursive approach which takes O(2^N) time to compute as every call needs to call two other calls but if we already have the answers of two other calls in an array then we can directly use them.

Top Down Approach:

int fibonacciTopDown(int N, int strg[]){
    if(N == 1 || N == 0){
        return N;
    }
    if(strg[N] != 0){
        return strg[N];
    }
    int ans = fibonacciTopDown(N-1, strg) + fibonacciTopDown(N - 2, strg);
    strg[N] = ans;
    return ans;
}

Now the top down approach also uses recursion but before returning the answer to the solution we store the answer in strg array so that if we needed the answer again then we could simply use that answer directly from our array. The time complexity of the program is O(N).

Bottom Up Approach:

int fibonacciBottomUp(int N){
    int strg[N + 1] = {0};
    strg[0] = 0;
    strg[1] = 1;
    for(int i = 2;i<N+1;i++){
        strg[i] = strg[i-1] + strg[i-2];
    }
    return strg[N];
}

This is the Bottom Up approach with time complexity as O(N). Now we have an iterative method to the recursive problem.

As seen above from the dp approaches we can very easily see that storage matrix or dp matrix has some meaning. For example, In the Fibonacci case, the Nth index of strg matrix stores the Nth fibonaaci number that's why we can very easily write this line strg[i] = strg[i-1] + strg[i-2].

As stated above start solving dp problems with recursion first and then proceed to dp. Try assigning some meaning to the storage matrix or dp matrix and formulate the correct equation.



Code to find the Nth Fibonacci number using all given approaches

#include <iostream>
using namespace std;

int fibonacci(int N){
	if(N == 0 || N == 1){
		return N;
	}
	int ans = fibonacci(N-1) + fibonacci(N - 2);
	return ans;
}

int fibonacciTopDown(int N, int strg[]){
	if(N == 1 || N == 0){
		return N;
	}
	if(strg[N] != 0){
		return strg[N];
	}
	int ans = fibonacciTopDown(N-1, strg) + fibonacciTopDown(N - 2, strg);
	strg[N] = ans;
	return ans;
}

int fibonacciBottomUp(int N){
	int strg[N + 1] = {0};
	strg[0] = 0;
	strg[1] = 1;
	for(int i = 2;i<N+1;i++){
		strg[i] = strg[i-1] + strg[i-2];
	}
	return strg[N];
}

int main() {
	int N;
	cin >> N;

	int strg[N + 1] = {0};
	cout << "The answer using recursive solution is " << fibonacci(N) << endl;
	cout << "The answer using Bottom up aproach is " << fibonacciBottomUp(N) << endl;
	cout << "The answer using Top down approach is " << fibonacciTopDown(N,strg) << endl;

	return 0;
}

Output

8
The answer using recursive solution is 21
The answer using Bottom up aproach is 21
The answer using Top down approach is 21





Quick links:
C FAQ(s) C Advance programs C/C++ Tips & Tricks Puzzles JavaScript CSS Python Linux Commands PHP Android Articles More...

Featured post:
Introduction to Linux (Its modes, Safety, Most popular Applications)
Linux Best Distribution Software (Distros) of 2018

Was this page helpful? Please share with your friends...

Are you a blogger? Join our Blogging forum.

Comments and Discussions



Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates



© https://www.includehelp.com (2015-2018), Some rights reserved.