tsaiwn dynamic % cat -n coin0.c 1 #include 2 /* greedy */ 3 int nct; /* number of coin type */ 4 int vct[33], nc[33]; /* value of coin, number of each coin */ 5 int ncoins; /* min. number of coins for the change */ 6 void getCoinData(), printResult(); 7 int ask(), makeChange(int); 8 int main(){ 9 int money, i; 10 getCoinData(); 11 money=ask(); 12 while(money > 0){ 13 for(i=1; i<= nct; ++i) nc[i] = 0; ncoins=0; /* clear */ 14 ncoins = makeChange(money); 15 printResult(); 16 money=ask(); 17 } 18 return 0; 19 } 20 void getCoinData(){ 21 int i, tmp[] = { 0, 1, 5, 10, 25, 50 }; 22 nct = sizeof(tmp) / sizeof(int) - 1; 23 for(i=1; i<= nct; ++i) { 24 vct[i] = tmp[i]; 25 } 26 } 27 int ask(){ 28 char tmp[99]; 29 printf("How much of the change? "); 30 gets(tmp); 31 return (int)atol(tmp); 32 } 33 int makeChange(int m){ 34 int i, nthis; 35 int nmin = 0; /* number of min. coin */ 36 i = nct; /* the max one */ 37 while(m){ 38 if(m >= vct[i]) { 39 nthis = m / vct[i]; 40 nc[i] += nthis; 41 nmin += nthis; 42 m -= nthis * vct[i]; /* remain money */ 43 } 44 --i; 45 } 46 return nmin; 47 } 48 void printResult(){ 49 int i; 50 printf("Total number of coins required: %d\n", ncoins); 51 for(i=nct; i>0; --i){ 52 if(nc[i]){ 53 printf("\t%d x %2d\n", nc[i], vct[i]); 54 } 55 } 56 printf("\n"); 57 } tsaiwn dynamic % gcc coin0.c /var/tmp/ccj314Z4.o: In function `ask': /var/tmp/ccj314Z4.o(.text+0x10a): warning: this program uses gets(), which is unsafe. tsaiwn dynamic % ./a.out warning: this program uses gets(), which is unsafe. How much of the change? 1 Total number of coins required: 1 1 x 1 How much of the change? 2 Total number of coins required: 2 2 x 1 How much of the change? 63 Total number of coins required: 5 1 x 50 1 x 10 3 x 1 How much of the change? 67 Total number of coins required: 5 1 x 50 1 x 10 1 x 5 2 x 1 How much of the change? 0 tsaiwn dynamic % tsaiwn dynamic % cat -n coin2.c 1 #include 2 /* Dynamic programming for making change, ver.1 */ 3 int nct; /* number of coin type */ 4 int vct[33], nc[33]; /* value of coin, number of each coin */ 5 int ncoins; /* min. number of coins for the change */ 6 void getCoinData(), printResult(); 7 int ask(), makeChange(int); 8 int nmin[100]; /* min coins for each i cents */ 9 int imax=0; 10 int main(){ 11 int money, i; 12 getCoinData(); 13 money=ask(); 14 while(money > 0){ 15 imax=0; 16 for(i=1; i<=money; ++i) nmin[i] = money; 17 for(i=1; i<= nct; ++i) nc[i] = 0; ncoins=0; /* clear */ 18 ncoins = makeChange(money); 19 printResult(); 20 money=ask(); 21 } 22 return 0; 23 } 24 void getCoinData(){ 25 int i, tmp[] = { 0, 1, 5, 10, 21, 50 }; 26 nct = sizeof(tmp) / sizeof(int) - 1; 27 for(i=1; i<= nct; ++i) { 28 vct[i] = tmp[i]; 29 } 30 } 31 int ask(){ 32 char tmp[99]; 33 printf("How much of the change? "); 34 gets(tmp); 35 return (int)atol(tmp); 36 } 37 int makeChange(int m){ 38 int i, k; 39 for(i=1; i <= nct; ++i){ 40 if(m == vct[i]) return 1; 41 } 42 if(m <= imax) return nmin[m]; /* Remove this line and try again ! */ 43 for(i=1; i< m; ++i) { 44 k = makeChange(i) + makeChange(m-i); 45 if( k < nmin[m] ) nmin[m] = k; 46 if(i>imax) imax = i; 47 } 48 return nmin[m]; 49 } 50 void printResult(){ 51 int i; 52 printf("Total number of coins required: %d\n", ncoins); 53 for(i=nct; i>0; --i){ 54 if(nc[i]){ 55 printf("\t%d x %2d\n", nc[i], vct[i]); 56 } 57 } 58 printf("\n"); 59 } tsaiwn dynamic % gcc coin2.c tsaiwn dynamic % ./a.out warning: this program uses gets(), which is unsafe. How much of the change? 2 Total number of coins required: 2 How much of the change? 63 Total number of coins required: 3 How much of the change? 65 Total number of coins required: 3 How much of the change? 50 Total number of coins required: 1 How much of the change? 55 Total number of coins required: 2 How much of the change? 0 tsaiwn dynamic % tsaiwn dynamic % cat -n coin3.c 1 #include 2 #define MAX_CHANGE 99 3 /* Dynamic programming for making change, ver.2 */ 4 int nct; /* number of coin type */ 5 int vct[33], nc[33]; /* value of coin, number of each coin */ 6 int ncoins; /* min. number of coins for the change */ 7 void getCoinData(), printResult(), prepareChange(); 8 int ask(), makeChange(int); 9 int nmin[ MAX_CHANGE+1 ]; /* min coins for each i cents */ 10 int imax=0; 11 int main(){ 12 int money, i; 13 getCoinData(); 14 prepareChange(); 15 money=ask(); 16 while(money > 0){ 17 for(i=1; i<= nct; ++i) nc[i] = 0; ncoins=0; /* clear */ 18 ncoins = makeChange(money); 19 printResult(); 20 money=ask(); 21 } 22 return 0; 23 } 24 void getCoinData(){ 25 int i, tmp[] = { 0, 1, 5, 10, 21, 50 }; 26 nct = sizeof(tmp) / sizeof(int) - 1; 27 for(i=1; i<= nct; ++i) { 28 vct[i] = tmp[i]; 29 } 30 } 31 int ask(){ 32 char tmp[99]; 33 printf("How much of the change? "); 34 gets(tmp); 35 return (int)atol(tmp); 36 } 37 int makeChange(int m){ 38 return nmin[m]; 39 } 40 void prepareChange( ){ 41 int i, k, m; 42 nmin[0] = 0; 43 for(m=1; m<= MAX_CHANGE; ++m) nmin[m] = MAX_CHANGE; 44 for(i=1; i <= nct; ++i) 45 nmin[ vct[i] ] = 1; /* exactly one coin */ 46 /******/ 47 for(m=2; m<= MAX_CHANGE; ++m) { 48 for(i=1; i< m; ++i) { 49 k = nmin[i] + nmin[m-i]; 50 if( k < nmin[m] ) nmin[m] = k; 51 } 52 } 53 } 54 void printResult(){ 55 int i; 56 printf("Total number of coins required: %d\n", ncoins); 57 for(i=nct; i>0; --i){ 58 if(nc[i]){ 59 printf("\t%d x %2d\n", nc[i], vct[i]); 60 } 61 } 62 printf("\n"); 63 } tsaiwn dynamic % exit