首页 > 其他 > 详细

【ACM小白成长撸】--贪婪法解硬币找零问题

时间:2016-10-12 00:50:38      阅读:265      评论:0      收藏:0      [点我收藏+]

question:假设有一种货币,它有面值为1分、2分、5分和1角的硬币,最少需要多少个硬币来找出K分钱的零钱。按照贪婪法的思想,需要不断地使用面值最大的硬币。如果找零的值小于最大的硬币值,则尝试第二大的硬币,依次类推。

 1 /*程序的版权和版本声明部分:
 2 **从《C++程序设计思想与方法》(作者:翁惠玉)P61转载
 3 */
 4 #include <iostream>
 5 
 6 using namespace std;
 7 
 8 #define ONEFEN 1
 9 #define TWOFEN 2
10 #define FIVEFEN 5
11 #define ONEJIAO 10
12 
13 int main(void)
14 {
15     int money;
16     int onefen = 0, twofen = 0, fivefen = 0, onejiao = 0;
17 
18     cout << "输入要找零的钱(以分为单位):";
19     cin >> money;
20 
21     //不断尝试每一种硬币
22     while(money >= ONEJIAO)
23     {
24         onejiao++;
25         money = money - ONEJIAO;
26     }
27     while(money >= FIVEFEN)
28     {
29         fivefen++;
30         money = money - FIVEFEN;
31     }
32     while(money >= TWOFEN)
33     {
34         twofen++;
35         money = money - TWOFEN;
36     }
37     while(money >= ONEFEN)
38     {
39         onefen++;
40         money = money - ONEFEN;
41     }
42 
43     cout << "1角硬币数:" << onejiao << endl;
44     cout << "5分硬币数:" << fivefen << endl;
45     cout << "2分硬币数:" << twofen << endl;
46     cout << "1分硬币数:" << onefen << endl;
47 
48     return 0;
49 }

 

【ACM小白成长撸】--贪婪法解硬币找零问题

原文:http://www.cnblogs.com/zpc-uestc/p/5951167.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!