Problem description
Recurrence relations are where a function is defined in terms of itself and maybe other functions as well. in this problem, we have two functions of interest:
F (N) = F (N - 1) + G (N - 1) ; F (1) = 1

G (N) = G (N - 1) + G (N - 3) ; G (1) = 1, G (2) = 0, G (3) = 1

For a given value of N, compute F (N).

 
Input
Each line of input will have exactly one integer, 57 > = N > 0.

 
Output
For each line of input, output F(N).

 
Sample Input
1
4
57
 
Sample Output
1
3
2035586497
 

#include <stdio.h>

unsigned long getfn(unsigned long n);
void getgn();

unsigned long   a[60];

unsigned long getfn(unsigned long n)
{ unsigned long i = 0,j = 0,k = 0;

  if(n == 1)
 i = 1;

  else  { j = getfn(n - 1);
   k = a[n - 1];
   i = j + k;
 }
  return i;
}

void getgn()
{ int n,m,i,j;

  a[1] = 1;
  a[2] = 0;
  a[3] = 1;
  for(n = 4,i = 0,j = 0; n <= 57; n ++)
     { i = n - 1;
       j = n - 3;
       a[n] = a[i] + a[j];
     }
}

int main()
{ unsigned long n,m;

  getgn();
  while( scanf("%ld",&m) != EOF )
 { n = getfn( m );
   printf("%ld\n",n);
 }
  return 0;
}

评论