Part-1 , Fibonacchi Number Finding

Tricks For Fibonacchi ,

If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)

                                                 TIME COMPLEXITY ( O Log ( n ) )


#include<bits/stdc++.h>

using namespace std;

const int MAX =1000;
int fibonacchi[1000]={0};


int fib(int n)
{
    int k;
    if(n==0)
    {

        return 0;
    }
    if(n==1||n==2)
    {
        return (fibonacchi[n]=1);
    }
    if(fibonacchi[n])
        return fibonacchi[n];

    k=(n&1)? (n+1)/2: n/2;

    fibonacchi[n]=(n&1)? (fib(k)*fib(k)+(fib(k-1)*fib(k-1))) : (2*fib(k-1)+fib(k))*fib(k);

    return fibonacchi[n];
}

int main()

{
    int x;
    cin>>x;
    cout<<fib(x)<<endl;
    return 0;
}


                                                          Use Of Dynamic Programming

                                                          TIME COMPLEXITY O(N);   


#include<bits/stdc++.h>

using namespace std;

int fib(int n)
{
  /* Declare an array to store Fibonacci numbers. */
  int f[n+1];
  int i;

  /* 0th and 1st number of the series are 0 and 1*/
  f[0] = 0;
  f[1] = 1;

  for (i = 2; i <= n; i++)
  {
      /* Add the previous 2 numbers in the series
         and store it */
      f[i] = f[i-1] + f[i-2];
  }

  return f[n];
}

int main ()
{
  int n;
  cin>>n;
  cout<<fib(n)<<endl;
  return 0;
}
 

                                                    A Problem & It's Solution 

 https://practice.geeksforgeeks.org/problems/nth-fibonacci-number/0


#include<bits/stdc++.h>

using namespace std;

// Nayeem Shahriar Joy , Applied Physics & Electronic Engineering , UNiversity of Rajshahi.

const int MAX =1000;
long dp[1000]={0};


int fib(int n)
{
   dp[0]=0;
   dp[1]=1;
   for(int i=2;i<=1000;i++)
   {
       dp[i]=(dp[i-1]+dp[i-2])%1000000007;

   }
   return dp[n];
}
int main() {
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cout<<fib(n)<<endl;

    }

    return 0;
}