钞票分解
问题描述
在这个问题中,你需要读取一个整数值并将其分解为多张钞票的和,每种面值的钞票可以使用多张,并要求所用的钞票数量尽可能少。
请你输出读取值和钞票清单。
钞票的可能面值有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
问题分析
拆分问题,首先从最大的开始,选取合适数量后,再选取第二大的金额,以此类推
代码实现
#include <iostream> #include <bits/stdc++.h> using namespace std;
int main(){
long money,m; int yb,ws,es,s,w,e,y; cin>>money; m=money; yb=money/100; money=money%100; ws=money/50; money=money%50; es=money/20; money=money%20; s=money/10; money=money%10; w=money/5; money=money%5; e=money/2; money=money%2; y=money; cout<<m<<endl; cout<<yb<<" nota(s) de R$ 100,00"<<endl; cout<<ws<<" nota(s) de R$ 50,00"<<endl; cout<<es<<" nota(s) de R$ 20,00"<<endl; cout<<s<<" nota(s) de R$ 10,00"<<endl; cout<<w<<" nota(s) de R$ 5,00"<<endl; cout<<e<<" nota(s) de R$ 2,00"<<endl; cout<<y<<" nota(s) de R$ 1,00"<<endl; return 0; }
|
运行结果
574 574 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 0 nota(s) de R$ 5,00 2 nota(s) de R$ 2,00 0 nota(s) de R$ 1,00
|
总结
钞票分解问题,其实就是对一个数的分解,将其分解为对应数位,整除是得到数量,取余是分解后得到剩下的