题目描述

读取一个带有两个小数位的浮点数，这代表货币价值。

在此之后，将该值分解为多种钞票与硬币的和，每种面值的钞票和硬币使用数量不限，要求使用的钞票和硬币的总数量尽可能少。

钞票的面值是 100,50,20,10,5,2
。

硬币的面值是 1,0.50,0.25,0.10,0.05
和 0.01
。

经过实验证明：在本题中，优先使用面额大的钞票和硬币可以保证所用的钞票和硬币总数量最少。

输入格式
输入一个浮点数 N
。

输出格式
参照输出样例，输出每种面值的钞票和硬币的需求数量。

数据范围
0≤N≤1000000.00

样例

输入样例：
576.73

输出样例：
NOTAS:
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
MOEDAS:
1 moeda(s) de R$ 1.00
1 moeda(s) de R$ 0.50
0 moeda(s) de R$ 0.25
2 moeda(s) de R$ 0.10
0 moeda(s) de R$ 0.05
3 moeda(s) de R$ 0.01

算法1

(放大法) $O(n^2)$

其中使用%时候遇到一点困难，%符号不支持浮点型的计算
这里使用了数组，通过乘100来实现

时间复杂度

C++ 代码

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
//用放大法解决浮点型不能除的问题

    double m;
    cin >> m; //输入的浮点型
    int n = int(m*100); //乘100转化为整型
    double arr[12] = {100,50,20,10,5,2,1,0.50,0.25,0.10,0.05,0.01};
    int brr[12];

cout << "NOTAS:\n";
    for(int i=0;i<=5;i++)
    {
        brr[i] = arr[i] * 100;
        printf("%d nota(s) de R$ %.2lf\n",n/brr[i],arr[i]);
        n = n % brr[i]; //浮点型不能取余，*100变为整型or用函数fmod
    }

cout << "MOEDAS:\n" ;
    for(int u=6;u<=11;u++)
    {
        brr[u] = arr[u] * 100;
        printf("%d moeda(s) de R$ %.2lf\n",n/brr[u],arr[u]);
        n = n % brr[u];
    }
    return 0；
}

算法2

(fmod函数来求余) $O(n^2)$

使用fmod来进行求余计算，记得写头文件#include [HTML_REMOVED]，省去了*100的复杂操作

C++ 代码

//用函数解决fmod
#include <iostream>
#include <cmath>
using namespace std;
int main()
{   
    double m;
    cin >> m; //输入的浮点型

    double arr[12] = {100,50,20,10,5,2,1,0.50,0.25,0.10,0.05,0.01};


cout << "NOTAS:\n";
    for(int i=0;i<=5;i++)
    {
        int count = floor(m / arr[i]);
        printf("%d nota(s) de R$ %.2lf\n",count,arr[i]);
        m = fmod(m,arr[i]); 
    }

cout << "MOEDAS:\n" ;
    for(int u=6;u<=11;u++)
    {
        int count = floor(m / arr[u]);
        printf("%d moeda(s) de R$ %.2lf\n",count,arr[u]);
        m = fmod(m,arr[u]);
    }
    return 0;
}