{"id":26534,"date":"2017-12-20T21:39:26","date_gmt":"2017-12-20T16:09:26","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26534"},"modified":"2017-12-20T21:39:26","modified_gmt":"2017-12-20T16:09:26","slug":"cpp-programming-program-for-fibonacci-numbers","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/cpp-programming-program-for-fibonacci-numbers\/","title":{"rendered":"Cpp Programming – Program for Fibonacci numbers"},"content":{"rendered":"

The Fibonacci numbers are the numbers in the following integer sequence.<\/span><\/p>\n

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \u2026\u2026..<\/p>\n

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation<\/p>\n

    Fn<\/sub> = Fn-1<\/sub> + Fn-2<\/sub><\/pre>\n
with seed values<\/p>\n
F0<\/sub> = 0 and F1<\/sub> = 1.<\/pre>\n
Write a function int fib(int n)<\/em> that returns Fn<\/sub>. For example, if n<\/em> = 0, then fib()<\/em> should return 0. If n = 1, then it should return 1. For n > 1, it should return Fn-1<\/sub> + Fn-2<\/sub><\/p>\n
For n = 9\r\nOutput:34<\/pre>\n
Following are different methods to get the nth Fibonacci number.<\/p>\n[ad type=”banner”]\n
Method 1 ( Space Optimized )<\/strong><\/p>\n
We can optimize the space used in method 2 by storing the previous two numbers only because that is all we need to get the next Fibonacci number in series.<\/p>\n
 
 C++<\/span> <\/div> 
\/\/ Fibonacci Series using Space Optimized Method#include<stdio.h>int fib(int n){  int a = 0, b = 1, c, i;  if( n == 0)    return a;  for (i = 2; i <= n; i++)  {     c = a + b;     a = b;     b = c;  }  return b;} int main (){  int n = 9;  printf("%d", fib(n));  getchar();  return 0;}<\/code><\/pre> <\/div>\n
Time Complexity:<\/em> O(n)
\nExtra Space: <\/em>O(1)<\/p>\n
 <\/p>\n[ad type=”banner”]\n
Method 2\u00a0(O(Log n) Time)<\/strong>
\nBelow is one more interesting recurrence formula that can be used to find n\u2019th Fibonacci Number in O(Log n) time.<\/p>\n
If n is even then k = n\/2:\r\nF(n) = [2*F(k-1) + F(k)]*F(k)\r\n\r\nIf n is odd then k = (n + 1)\/2\r\nF(n) = F(k)*F(k) + F(k-1)*F(k-1)<\/pre>\n
How does this formula work?<\/strong>
\nThe formula can be derived from above matrix equation.<\/p>\n
\"Fibonacci<\/p>\n
 <\/p>\n
 <\/p>\n
Taking determinant on both sides, we get
\n(-1)n<\/sup> = Fn+1<\/sub>Fn-1<\/sub> \u2013 Fn<\/sub>2<\/sup>
\nMoreover, since An<\/sup>Am<\/sup> = An+m<\/sup> for any square matrix A, the following identities can be derived (they are obtained form two different coefficients of the matrix product)<\/p>\n
Fm<\/sub>Fn<\/sub> + Fm-1<\/sub>Fn-1<\/sub> = Fm+n-1<\/sub><\/p>\n
By putting n = n+1,<\/p>\n
Fm<\/sub>Fn+1<\/sub> + Fm-1<\/sub>Fn<\/sub> = Fm+n<\/sub><\/p>\n
Putting m = n<\/p>\n
F2n-1<\/sub> = Fn<\/sub>2<\/sup> + Fn-1<\/sub>2<\/sup><\/p>\n
F2n<\/sub> = (Fn-1<\/sub> + Fn+1<\/sub>)Fn<\/sub> = (2Fn-1<\/sub> + Fn<\/sub>)Fn<\/sub> (Source: Wiki)<\/p>\n
To get the formula to be proved, we simply need to do following
\nIf n is even, we can put k = n\/2
\nIf n is odd, we can put k = (n+1)\/2<\/p>\n[ad type=”banner”]\n
Below is C++ implementation of above idea.<\/p>\n
 
 C++<\/span> <\/div> 
\/\/ C++ Program to find n'th fibonacci Number in\/\/ with O(Log n) arithmatic operations#include <bits\/stdc++.h>using namespace std; const int MAX = 1000; \/\/ Create an array for memoizationint f[MAX] = {0}; \/\/ Returns n'th fuibonacci number using table f[]int fib(int n){    \/\/ Base cases    if (n == 0)        return 0;    if (n == 1 || n == 2)        return (f[n] = 1);     \/\/ If fib(n) is already computed    if (f[n])        return f[n];     int k = (n & 1)? (n+1)\/2 : n\/2;     \/\/ Applyting above formula [Note value n&1 is 1    \/\/ if n is odd, else 0.    f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1))           : (2*fib(k-1) + fib(k))*fib(k);     return f[n];} \/* Driver program to test above function *\/int main(){    int n = 9;    printf("%d ", fib(n));    return 0;}<\/code><\/pre> <\/div>\n
Output :<\/p>\n
34<\/pre>\n
Time complexity of this solution is O(Log n) as we divide the problem to half in every recursive call.<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
C++ Programming – Program for Fibonacci numbers – Dynamic Programming The Fibonacci numbers are the numbers in the following integer sequence.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83515,1,70145],"tags":[72844,79068,72850,72438,79071,79070,74945,79073,74954,74060,72839,79069,72020,72852,79066,79077,72855,72853,79086,79074,79082,74961,72444,74934,72851],"class_list":["post-26534","post","type-post","status-publish","format-standard","hentry","category-c-programming-3","category-coding","category-dynamic-programming","tag-dynamic-programming-software","tag-dynamic-programming-tutorial-with-fibonacci-sequence","tag-explain-dynamic-programming","tag-factorial-c-program","tag-fibonacci-numbers-using-dynamic-programming","tag-fibonacci-sequence-with-dynamic-programming","tag-fibonacci-series","tag-fibonacci-series-algorithm-analysis","tag-fibonacci-series-c","tag-fibonacci-series-c-program","tag-how-to-solve-dynamic-programming-problems","tag-improve-c-fibonacci-series","tag-palindrome-program","tag-problems-on-dynamic-programming","tag-program-for-fibonacci-numbers","tag-program-for-fibonacci-series","tag-simple-dynamic-programming-example","tag-types-of-dynamic-programming","tag-write-a-c-program-for-fibonacci-series","tag-write-a-c-program-to-print-nth-fibonacci-number","tag-write-a-program-in-c-for-fibonacci-series","tag-write-a-program-to-generate-the-fibonacci-series","tag-write-a-program-to-generate-the-fibonacci-series-in-c","tag-write-a-program-to-print-fibonacci-series","tag-youtube-dynamic-programming"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26534","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26534"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26534\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26534"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26534"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26534"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}