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 1457 Sample Output 132035586497    #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;}

评论