首页 > 代码库 > 【ACM小白成长撸】--贪婪法解硬币找零问题

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

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 210 #define FIVEFEN 511 #define ONEJIAO 1012 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小白成长撸】--贪婪法解硬币找零问题