653. 钞票
题目描述
在这个问题中,你需要读取一个整数值并将其分解为多张钞票的和,每种面值的钞票可以使用多张,并要求所用的钞票数量尽可能少。
请你输出读取值和钞票清单。
钞票的可能面值有 100,50,20,10,5,2,1。
输入格式
输入一个整数 N。
输出格式
参照输出样例,输出读取数值以及每种面值的钞票的需求数量。
数据范围
0<N<1000000
输入样例
576
输出样例
576
5 nota(s) de R$ 100,00
1 nota(s) de R$ 50,00
1 nota(s) de R$ 20,00
0 nota(s) de R$ 10,00
1 nota(s) de R$ 5,00
0 nota(s) de R$ 2,00
1 nota(s) de R$ 1,00
算法1
笨算法
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int n, a, b, c, d, e, f, g;
cin >> n;
a = n / 100;
b = (n - a * 100) / 50;
c = (n - a * 100 - b * 50) / 20;
d = (n - a * 100 - b * 50 - c * 20) / 10;
e = (n - a * 100 - b * 50 - c * 20 - d * 10) / 5;
f = (n - a * 100 - b * 50 - c * 20 - d * 10 - e * 5) / 2;
g = (n - a * 100 - b * 50 - c * 20 - d * 10 - e * 5 - f * 2) / 1;
//cout << n << endl;//慢!!!
printf("%d\n", n);
printf("%d nota(s) de R$ 100,00\n", a);
printf("%d nota(s) de R$ 50,00\n", b);
printf("%d nota(s) de R$ 20,00\n", c);
printf("%d nota(s) de R$ 10,00\n", d);
printf("%d nota(s) de R$ 5,00\n", e);
printf("%d nota(s) de R$ 2,00\n", f);
printf("%d nota(s) de R$ 1,00\n", g);
return 0;
}
算法2
优化一下
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int n;
cin >> n;
//cout << n << endl;//慢!!!
printf("%d\n", n);
printf("%d nota(s) de R$ 100,00\n", n / 100);
n %= 100;
printf("%d nota(s) de R$ 50,00\n", n / 50);
n %= 50;
printf("%d nota(s) de R$ 20,00\n", n / 20);
n %= 20;
printf("%d nota(s) de R$ 10,00\n", n / 10);
n %= 10;
printf("%d nota(s) de R$ 5,00\n", n / 5);
n %= 5;
printf("%d nota(s) de R$ 2,00\n", n / 2);
n %= 2;
printf("%d nota(s) de R$ 1,00\n", n / 1);
return 0;
}
算法3
用循环结构
#include <iostream>
//这道题适合用贪心的思想,在算法基础里会学
using namespace std;
int n;
int a[7] = {100, 50, 20, 10, 5, 2, 1};//定义数组,类型为整形,存放所有货币类型;
//int a[] = {100,50,20,10,5,2,1}; 也可以
int main()
{
cin >> n;
printf("%d\n", n);
//注意换行,以下循环结构;
for (int i = 0; i < 7; i ++ )
{
int x = n / a[i];
printf("%d nota(s) de R$ %d,00\n", x, a[i]);
n %= a[i];
}
return 0;
}
//要尽量小,每次就要取尽量的多的大