【计算机算法】枚举——换硬币

题目

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

输入格式

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

输出格式

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

输入样例

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 = 4

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

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

最后

以上就是内向小猫咪为你收集整理的【计算机算法】枚举——换硬币的全部内容，希望文章能够帮你解决【计算机算法】枚举——换硬币所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。