本文共 2115 字,大约阅读时间需要 7 分钟。
/**/ /* 标题:< <系统设计师> >应试编程实例-[递推算法程序设计] 作者:成晓旭 时间:2002年09月14日(18:20:00-20:18:00) 实现“装箱”问题的贪婪算法实现函数 时间:2002年09月14日(22:00:00-23:18:00) 实现“装箱”问题的贪婪算法实现函数 时间:2002年09月14日(18:20:38-22:18:00) 实现“人民币找零”问题的贪婪法解决算法 */ #include " stdio.h " #include " stdlib.h " // :============================“人民币找零”问题的贪婪法解决算法=========================== /**/ /* 作者:成晓旭 时间:2002年09月17日(21:28:38-22:18:00) 完成“人民币找零”问题的贪婪法解决算法 =================================================== 问题描述: 任何一张面额的纸币都找成比它的面额小的纸币,最小单位是元 编程思想: 已知,中华人民共和国的纸币面额分别为:100元、50元、20元、10元、5元、2元、1元, 任何一张较大面额的纸币,都采用贪婪法首先分解成尽可能大的面额的纸币。比如50元的纸币 找零时,首先分解出一个20元,接着在剩余的30元中,再分解出一个20元,剩余部分的10元, 可以用一张10元的纸币来找补。因此,分解结果是:50元 = 20元 + 20元 + 10元。*/ #define N 20 // 找补零钱函数 // int money: 将被找零的面额 // int number: 当前面额money要求被找补的最大允许张数 // int subscript: 面额数组下标 // int *denomination: 纸币面额数组 // int *param: 当前面额money在被要求找补的最大允许张数范围内,贪婪法解决方案结果 int Give_Change( int money, int number, int subscript, int * denomination, int * param) ... { int result; if(money == 0) return(0); //已经分解完成 if(number == 0 || subscript == 0) return(-1); //不可能分解 if(money < *denomination) return(Give_Change(money,number,subscript - 1,denomination + 1,param)); else ...{ *param = *denomination; //按能找零的最大面额给 //继续对剩余金额部分作分解 result = Give_Change(money - *denomination,number - 1,subscript,denomination,param + 1); if(result >= 0) return(result + 1); return(-1); //不可能分解 }} void Run_Give_Change() ... { int money,number,k,i,dibs[N]; int denomination[7] = ...{ 100,50,20,10,5,2,1}; printf("输入整钱数、找零的最大张数money,number: "); scanf("%d%d",&money,&number); for(i = 0;i < 7;i++) if(money > denomination[i]) break; //跳过面额比它在或相等的纸币单位 k = Give_Change(money,number,7 - i,&denomination[i],dibs); if(k <= 0) printf("面额为[%d]元纸币想找零成[%d]张零钞,是找不开! ",money,number); else ...{ printf("%d = %d",money,dibs[0]); for(i = 1;i < k;i++) printf(" + %d",dibs[i]); printf(" "); }} // :============================“人民币找零”问题的贪婪法解决算法=========================== int main( int argc, char * argv[]) ... { //Encase_Box(); //Journey_Horse(); Run_Give_Change(); printf(" 应用程序运行结束! "); return 0;} Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=935835