Here, is code below to calculate nth term of Fibonacci series in log(n) time complexity. Do comment if find any bug. Thanks E-mail :- surajjumpy@gmail.com
#include<iostream> using namespace std; void ope(int F[2][2], int M[2][2]) { int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w; } void mul(int M[2][2],int n) { if(n <= 1) return; int F[2][2]={1,1,1,0}; mul(M,n/2); ope(M,M); if(n&1) ope(M,F); } int fab(int n) { if(n == 0) return 0; int M[2][2] = {1,1,1,0}; mul(M,n-1); return M[0][0]; } int main() { int i; cout<<"Enter the term no. "; cin>>i; cout<<"\nThe "<<i<<" term is : "<<fab(i); return 0; }
No comments:
Post a Comment
Your comment is valuable to us