#include <stdio.h>
#include <stdlib.h>

/* Straightforward recursive function to compute C(n) */
unsigned int frogRec ( unsigned int n )
{
   if (n == 0) return 1;   /* Only one possibility: Don't move at all */
   if (n == 1) return 1;   /* Only one possibility: 1 */
   if (n == 2) return 2;   /* Only two possibilities: 1,1 and 2 */

   /* for n >= 3 use recursion */
   return frogRec(n-1) + frogRec(n-2) + frogRec(n-3);
}

/* Straightforward iterative version to compute C(n) */
unsigned int frogItr ( unsigned int n )
{
   unsigned int curr, prev1, prev2, prev3, i;

   /* Handle boundary conditions */
   if (n == 0) return 1;
   if (n == 1) return 1;
   if (n == 2) return 2;

   /* Remember three previous values */
   prev3 = prev2 = 1; prev1 = 2; i = 3;

   /* Iterate */
   while (i <= n) {
      curr = prev3 + prev2 + prev1;
      prev3 = prev2;
      prev2 = prev1;
      prev1 = curr;
      ++i;
   }

   return curr;
}

/* Straightforward recursive function to compute C(n,m) */
unsigned int frogRec2 ( unsigned int n, unsigned int m )
{
   /* You must have m <= n <= 3m */
   if ((n < m) || (n > 3*m)) return 0;

   /* Here the inequalities m <= n <= 3m are satisfied.
      For n = 0, m can be 0 only, but C(0,0) = 1.
      For n = 1, m can be 1 only, but C(1,1) = 1.
      For n = 2, m can be 1 or 2, but C(2,1) = C(2,2) = 1. */
   if (n <= 2) return 1;

   /* If you are not in the above boundary conditions, use recursion */
   return frogRec2(n-1,m-1) + frogRec2(n-2,m-1) + frogRec2(n-3,m-1);
}

/* Iterative implementation of a function to compute C(n,m) */
unsigned int frogItr2 ( unsigned int n, unsigned int m )
{
   unsigned int *C, i, j, prev1, prev2, prev3, curr;

   /* Handle the boundary conditions as before */
   if ((n < m) || (n > 3*m)) return 0;
   if (n <= 2) return 1;

   /* In the jth iteration, C[i] is meant to store C(i,j), that is,
      C stores the jth column of the (n+1) x m table of C(i,j) values. */
   C = (unsigned int *)malloc((n + 1) * sizeof(unsigned int));

   /* Initialize the first column: C[0,0] = 1, and C[i,0] = 0 for i > 0 */
   C[0] = 1; for (i=1; i<=n; ++i) C[i] = 0;

   /* Iterate for j = 1,2,3,...,m */
   for (j = 1; j <= m; ++j) {
      /* for i < j, we have C(i,j) = 0 */
      for (i=0; i<j; ++i) C[i] = 0;

      /* Initialize for computing C[j] to C[min(3j,n)] */

      /* C(j,j) = 1 (j jumps of 1 stairs */
      if (j <= n) { prev3 = C[j]; C[j] = 1; }

      /* C(j+1,j) = j (out of j jumps exactly one has to be 2, others 1) */
      if (j <= n-1) { prev2 = C[j+1]; C[j+1] = j; }

      /* C(j+2,j) = j (one jump of 3, others 1)
                    + binomial(j,2) (two jumps of 2, others 1) */
      if (j <= n-2) { prev1 = C[j+2]; C[j+2] = j * (j + 1) / 2; }

      i = j + 3;

      /* Iterate */
      while ((i <= n) && (i <= 3 * j)) {
         curr = prev3 + prev2 + prev1;
         prev3 = prev2;
         prev2 = prev1;
         prev1 = C[i];
         C[i] = curr;
         ++i;
      }

      /* If the loop breaks because of i > 3 * j, fill the rest of the
         array by 0 */
      while (i <= n) C[i++] = 0;
   }

   /* Free C[] before returning C[n,m] */
   curr = C[n];
   free(C);
   return curr;
}

int main ( int argc, char *argv[] )
{
   unsigned int n, m, count, sum;

   if (argc > 1) n = atoi(argv[1]);
   else {
      printf("n = "); scanf("%d", &n);
   }

   printf("+++ Any number of jumps...\n\n");

   count = frogRec(n);
   printf("    Recursive function returns count = %u\n\n", count);

   count = frogItr(n);
   printf("    Iterative function returns count = %u\n\n", count);

   printf("+++ Fixed number of jumps...\n\n");

   sum = 0;
   for (m=0; m<=n; ++m) {
      count = frogRec2(n,m);
      printf("    Recursive function returns count = %10u for m = %2u\n", count, m);
      sum += count;
   }
   printf("    ---------------------------------------------\n");
   printf("    Total number of possibilities    = %10u\n\n", sum);

   sum = 0;
   for (m=0; m<=n; ++m) {
      count = frogItr2(n,m);
      printf("    Iterative function returns count = %10u for m = %2u\n", count, m);
      sum += count;
   }
   printf("    ---------------------------------------------\n");
   printf("    Total number of possibilities    = %10u\n\n", sum);

   exit(0);
}