URI 1029 - Fibonacci, How Many Calls?

/// Header file begin

#include <iostream>

#include <cstdio>

#include <cstring>

#include <map>

#include <string>

#include <vector>

#include <cmath>

#include <cctype>

#include <sstream>

#include <set>

#include <list>

#include <stack>

#include<utility>

#include <queue>

#include <algorithm>

/// End

//..........

/// Macro

#define sf scanf

#define pf printf

#define sfint(a,b) scanf("%d %d",&a,&b)

#define sfl(a,b) scanf("%ld %ld",&a,&b)

#define sfll(a,b) scanf("%lld %lld",&a,&b)

#define sfd(a,b) scanf("%lf %lf",&a,&b)

#define sff(a,b) scanf("%f %f",&a,&b)

#define lp1(i,n) for(i=0;i<n;i++)

#define lp2(i,n) for(i=1;i<=n;i++)

#define mem(c,v) memset(c,v,sizeof(c))

#define cp(a) cout<<" "<<a<<" "

#define nl puts("")

#define sq(x) ((x)*(x))

#define all(x) x.begin(),x.end()

#define reall(x) x.rbegin(),x.rend()

#define sz size()

#define gc getchar()

#define pb push_back

/// End.........

 

/// Size

#define mx7 20000100

#define mx6 1500000

#define mx5 100005

#define mx4 1000100

#define inf 1<<30                                           //infinity value

#define eps 1e-9

#define mx (65540)

#define mod 1000000007

#define pi acos(-1.0)

 

/// Macros for Graph

 

#define white 0

#define gray 1

#define black -1

#define nil -2

 

using namespace std;

/***************/

 

/// typedef

 

typedef long long LL;

typedef long L;

typedef unsigned long long ull;

typedef unsigned long ul;

typedef unsigned int ui;

typedef pair<int, int> pii;

typedef vector<int>vi;

typedef vector<long long> vll;

typedef vector<long>vl;

typedef vector<char>vch;

typedef vector<string>vs;

typedef map<int,int>mpii;

typedef map<int,bool>mpbi;

typedef map<char,int>mpci;

typedef map<char,bool>mpbc;

typedef map<string,int>mpsi;

typedef map<long long,long long>mpll;

 

/// template

 

template<class T> T gcd(T a, T b ) {return b<=0?a:gcd(b,a%b);}

template<class T> T large(T a, T b ) {return a>b?a:b;}

template<class T> T small(T a, T b ) {return a<b?a:b;}

template<class T> T diffrnce(T a, T b) {return a-b<0?b-a:a-b;}

 

int dp[50],call[50];

 

int fib(int n)

{

 

    if(n==0)return 0;

    if(n == 1)

    {

        //c++;

        return n;

    }

 

    if(dp[n] != -1)

    {

        return dp[n];

    }

 

    else

    {

        //c++;

        //cout << "dp = " << dp[n] << " ";

        //c++;

        return (dp[n] = fib(n-1) + fib(n-2));

    }

}

 

int call_num(int n)

{

    if(n==0) return 0;

    if(n==1) return 0;

 

    if(call[n] != -1)

    {

        return call[n];

    }

 

    else

    {

        return (call[n] = call_num(n-1) + call_num(n-2) + 2);

    }

}

 

int main()

{

    mem(dp,-1);

    mem(call,-1);

 

    int t;

 

    sf("%d",&t);

 

    while(t--)

    {

        int n;

        sf("%d",&n);

 

        pf("fib(%d) = %d calls = %d\n",n,call_num(n),fib(n));

    }

 

    return 0;

}