欢迎来到天天文库
浏览记录
ID:51979194
大小:26.00 KB
页数:4页
时间:2020-03-21
《找零问题贪心算法实现.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、找零问题贪心算法实现一、实验描述当前有面值分别为2角5分,1角,5分,1分的硬币,请给出找n分钱的最佳方案(要求找出的硬币数目最少)。二、实验原理具体实例:假如老板要找给我99分钱,他有上面的面值分别为25,10,5,1的硬币数,为了找给我最少的硬币数,那么他是不是该这样找呢,先看看该找多少个25分的,99/25=3,好像是3个,要是4个的话,我们还得再给老板一个1分的,我不干,那么老板只能给我3个25分的拉,由于还少给我24,所以还得给我2个10分的和4个1分。具体实现://找零钱算法//Byfalcon//输入:数
2、组m,依次存放从大到小排列的面值数,n为需要找的钱数,单位全部为分//输出:数组num,对照数组m中的面值存放不同面值的硬币的个数,就找钱方案参考实验代码部分。三、实验代码#ifndefLEASTCOINS_H#defineLEASTCOINS_HclassLeastCoins{public:LeastCoins();~LeastCoins();voidrun();private:intnumber;//不同面值的硬币个数intTotalMoney;//要找回的总钱数int*T;//存储硬币的面值int*Coins;/
3、/硬币的个数int**m;//m[i][j]是以最大面值i要找回钱数是j需要硬币数的最少个数boolinput();intchangeMoney(inti,intj);//i是第i中硬币voidoutput();voidtraceback();//寻找轨迹};#endif#include#include#include#include#defineN10ifstreaminputFile("input.txt",ios::out);o
4、fstreamoutputFile("output.txt",ios::out);LeastCoins::LeastCoins(){number=0;TotalMoney=0;T=newint[N];Coins=newint[N];m=newint*[N];for(inti=0;i5、dLeastCoins::run(){if(input()){changeMoney(number,TotalMoney);output();}}boolLeastCoins::input(){inputFile>>number;outputFile<<"有"<>T[i];inputFile6、>>Coins[i];outputFile<>TotalMoney;outputFile<<"需要找回的总钱数为:"<=TotalMoney)returntrue;elseoutputFile<<"所有硬币的总钱数是"<7、1){if(j8、ngeMoney(i-1,j-(X-1)*T[i]);m[i-1][j-X*T[i]]=T1;m[i-1][j-(X-1)*T[i]]=T2;if((T1+X)>(T2+X-1))m[i][j]=T2+X-1;elsem[i][j]=T1+X;returnm[i][j];}}elseif(i==1)//此时i==1{if((j%T
5、dLeastCoins::run(){if(input()){changeMoney(number,TotalMoney);output();}}boolLeastCoins::input(){inputFile>>number;outputFile<<"有"<>T[i];inputFile
6、>>Coins[i];outputFile<>TotalMoney;outputFile<<"需要找回的总钱数为:"<=TotalMoney)returntrue;elseoutputFile<<"所有硬币的总钱数是"<7、1){if(j8、ngeMoney(i-1,j-(X-1)*T[i]);m[i-1][j-X*T[i]]=T1;m[i-1][j-(X-1)*T[i]]=T2;if((T1+X)>(T2+X-1))m[i][j]=T2+X-1;elsem[i][j]=T1+X;returnm[i][j];}}elseif(i==1)//此时i==1{if((j%T
7、1){if(j8、ngeMoney(i-1,j-(X-1)*T[i]);m[i-1][j-X*T[i]]=T1;m[i-1][j-(X-1)*T[i]]=T2;if((T1+X)>(T2+X-1))m[i][j]=T2+X-1;elsem[i][j]=T1+X;returnm[i][j];}}elseif(i==1)//此时i==1{if((j%T
8、ngeMoney(i-1,j-(X-1)*T[i]);m[i-1][j-X*T[i]]=T1;m[i-1][j-(X-1)*T[i]]=T2;if((T1+X)>(T2+X-1))m[i][j]=T2+X-1;elsem[i][j]=T1+X;returnm[i][j];}}elseif(i==1)//此时i==1{if((j%T
此文档下载收益归作者所有