【计算机算法】枚举法在硬币找零问题中的应用

题目

将一笔零钱换成5分、2分和1分的硬币&＃xff0c;要求每种硬币至少有一枚&＃xff0c;有几种不同的换法&＃xff1f;

输入格式

输入在一行中给出待换的零钱数额x∈(8,100)。

输出格式

要求按5分、2分和1分硬币的数量依次从大到小的顺序&＃xff0c;输出各种换法。每行输出一种换法&＃xff0c;格式为&＃xff1a;“fen5:5分硬币数量,
fen2:2分硬币数量, fen1:1分硬币数量, total:硬币总数量”。最后一行输出“count &＃61; 换法个数”。

输入样例

13

输出样例

fen5:2, fen2:1, fen1:1, total:4
fen5:1, fen2:3, fen1:2, total:6
fen5:1, fen2:2, fen1:4, total:7
fen5:1, fen2:1, fen1:6, total:8
count &＃61; 4

#include
using namespace std;
int main(){int x;//多少分钱 cin>>x; int count&＃61;0; //共多少种换法int ff,tf,of;//代表五分&＃xff0c;两分&＃xff0c;一分 int array[1000][4];int i &＃61; 0;for(int ff &＃61; 1;ff <&＃61; x/5;ff&＃43;&＃43;){for(int tf &＃61; 1; tf <&＃61; (x - ff*5)/2 ;tf&＃43;&＃43;){of &＃61; x - ff*5 - tf*2;if(of >&＃61; 1){array[i][0] &＃61; ff;array[i][1] &＃61; tf;array[i][2] &＃61; of;array[i][3] &＃61; ff&＃43;tf&＃43;of;count&＃43;&＃43;;i&＃43;&＃43;;}}}for(i &＃61; count-1;i >&＃61; 0;i--)cout<<"fen5:"<<array[i][0]<<", fen2:"<<array[i][1]<<", fen1:"<<array[i][2]<<", total:"<<array[i][3]<<endl;cout<<"count &＃61; "<<count<<endl;
}


需要注意的是&＃xff0c;for循环中判断条件是<&＃61;&＃xff0c;包括“&＃61;”&＃xff0c;以及注意题目中提及了倒序输出&＃xff0c;所以我选择用数组存储后倒序输出。当然也可以让for循环中ff从x/5开始&＃xff0c;不断自减直到1为止&＃xff08;每一个最少需要一枚&＃xff09;&＃xff0c;这样相较来说比较省空间。