#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/time.h>

/**
 * File    : divcon.c
 * Compile : gcc -o divcon divcon.c
 * Name    : Edison Chindrawaly
 * Class   : CSCI 4450 Spring 2002
 * Descp   : Math's technique of Combination of n choose r things.
 *           Implement divide & conquer with 10<n<30
 *           Implement dynamic programming with 1<n<256
 */

/************** Prototype *****************/
double times();
void chooseDynamic(int,int);
int choose(int,int);
void start(int,int);
/*****************************************/

/************** Global variable***********/
int table[256][256];

/************** Main *********************/
int main()
{
 printf("=========divide & conquer============\n");
 start(10,30);
 printf("=========dynamic programming=========\n");
 start(1,256);
 return 0;
}

/**
 * start's procedure is to start the process.
 * Its value of n is the switch to use divide & conquer
 * approach or to use dynamic programming.
 * if n == 256, it uses dynamic programming
 * else it uses divide and conquer.
 * @param  int a, int n
 * @return none
 */
void start(int a, int n)
{
 double z;
 int i,j;
 for(i=a; i<n+1; i++)
 {
   j=i/2;
   z = times();
   if(n == 256) chooseDynamic(i,j);
   else choose(i,j);
   printf("%i %.5f\n",i, times()-z);
 }
}


/**
 * times' procedure is to measure time elapsed.
 * @param none
 * @return double current time
 */
double times()
{
 struct timeval tv;
 gettimeofday(&tv,NULL);
 return tv.tv_sec+(float)(tv.tv_usec)/1000000.0;
}

/**
 * chooseDynamic's procedure is combination of n choose r
 * using Dynamic Programming approached. It is iterative
 * approached but faster in time due to the redundancy
 * of the results.
 * @param  int n, int r
 * @return none
 */
void chooseDynamic(int n, int r)
{
 int i,j;
 for(i=0; i<n-r; i++)
   table[i][0] = 1;
 for(i=0; i<r; i++)
   table[i][j] = 1;
 for(j=1; j<r; j++)
   for(i=j+1; i < n-r+j; i++)
     table[i][j] = table[i-1][j-1] + table[i-1][j];
}

/**
 * choose's procedure is combination of n choose r
 * using divide and conquer approached that is recursive.
 * @param  int n, int r
 * @return int result of choose(n-1,r-1)+choose(n-1,r)
 */
int choose(int n, int r)
{
 if((r==0)||(n==0))
   return 1;
 else
   return (choose(n-1,r-1)+choose(n-1,r));
}