CS3343/3341 Analysis of Algorithms |
Combinations with Memoization |
Here is the program with edited output data:
| Number of Exchanges Needed while Sorting with Heapsort | |
|---|---|
// Program to calculate combinations.
// Uses recursive formula, but saves answers in
// an array. Written by Neal R. Wagner
#include *lt;stdio.h>
#include *lt;math.h>
#include *lt;stdlib.h>
#define MAXN 50 // largest possible input
int c(int, int); // memoized calculation of C #
int cs(int, int); // slow calculation of C #
void initC(void); // initialize F to -1 values
int C[MAXN][MAXN]; // array holding answers
int recurs; // number of recursive calls
int ins; // number of table insertions
int main() {
int n, k;
for( ; ; ) {
recurs = 0;
ins = 0;
scanf("%d %d", &n, &k);
if (n < 0 || k < 0 || n < k || n>=MAXN) {
printf("bad input\n");
exit(1);
}
printf("No array: |%5d |%5d |%12d |",
n, k, cs(n, k));
printf("%12d | |\n", recurs);
recurs = 0;
initC();
printf("Use array: |%5d |%5d |%12d |",
n, k, c(n, k));
printf("%12d |%8d |\n", recurs, ins);
}
}
| // c: uses memoization
int c(int n, int k) {
int c1, c2;
recurs++;
if (k == 0) return 1;
if (n == k) return 1;
if ( C[n][k] >= 0 ) {
// answer already in C
return C[n][k];
}
c1 = c(n-1, k);
C[n-1][k] = c1; ins++;
c2 = c(n-1, k-1);
C[n-1][ k-1] = c2; ins++;
C[n][k] = c1 + c2; ins++;
return c1 + c2;
}
// cs: uses recursion
int cs(int n, int k) {
int c1, c2;
recurs++;
if (k == 0) return 1;
if (n == k) return 1;
c1 = cs(n-1, k);
c2 = cs(n-1, k-1);
return c1 + c2;
}
void initC(void) {
int i, j;
for(i = 0; i < MAXN; i++)
for (j = 0; j < MAXN; j++)
C[i][j] = -1;
}
|
| Output. | |
+------------+-------+-------+--------------+--------------+----------+ | Array / not| n | k | C(n,k) | Calls to C | Inserts | +------------+-------+-------+--------------+--------------+----------+ | No array: | 4 | 0 | 1 | 1 | | | Use array: | 4 | 0 | 1 | 1 | 0 | +------------+-------+-------+--------------+--------------+----------+ | No array: | 4 | 1 | 4 | 7 | | | Use array: | 4 | 1 | 4 | 7 | 9 | +------------+-------+-------+--------------+--------------+----------+ | No array: | 5 | 4 | 5 | 9 | | | Use array: | 5 | 4 | 5 | 9 | 12 | +------------+-------+-------+--------------+--------------+----------+ | No array: | 6 | 4 | 15 | 29 | | | Use array: | 6 | 4 | 15 | 17 | 24 | +------------+-------+-------+--------------+--------------+----------+ | No array: | 7 | 3 | 35 | 69 | | | Use array: | 7 | 3 | 35 | 25 | 36 | +------------+-------+-------+--------------+--------------+----------+ | No array: | 15 | 10 | 3003 | 6005 | | | Use array: | 15 | 10 | 3003 | 101 | 150 | +------------+-------+-------+--------------+--------------+----------+ | No array: | 20 | 10 | 184756 | 369511 | | | Use array: | 20 | 10 | 184756 | 201 | 300 | +------------+-------+-------+--------------+--------------+----------+ | No array: | 30 | 15 | 155117520 | 310235039 | | | Use array: | 30 | 15 | 155117520 | 451 | 675 | +------------+-------+-------+--------------+--------------+----------+ | No array: | 35 | 10 | 183579396 | 367158791 | | | Use array: | 35 | 10 | 183579396 | 501 | 750 | +------------+-------+-------+--------------+--------------+----------+ | No array: | 35 | 12 | 834451800 | 1668903599 | | | Use array: | 35 | 12 | 834451800 | 553 | 828 | +------------+-------+-------+--------------+--------------+----------+ | |