每日算法刷题Day1-隐式转换与精度丢失

⭐每日算法系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，与笔者另一系列文章有所区别，并不是以知识点的形式提升算法能力，而是以实战习题的形式理解算法，使用算法。

1.球的体积

给定你一个球体的半径 RR，请你计算球体的体积。

计算球体的公式为 $V=(4/3)∗π∗R^3$。

π取 3.14159。

输入格式

输入一个整数 R。

输出格式

输出格式为 VOLUME = X，其中 XX 为球体的体积，结果保留三位小数。

数据范围

1≤R≤2000

输入样例

3

输出样例

VOLUME = 113.097

代码

#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    double a,V;
    cin>>a;
    V=(4/3.0)*3.14159*a*a*a;
    printf("VOLUME = %.3f",V);
    return 0;
}

错题总结

注意：有些语言中 (4/3) 无法得到 1.3333…，建议在公式中使用 (4/3.0)。

2.钞票

在这个问题中，你需要读取一个整数值并将其分解为多张钞票的和，每种面值的钞票可以使用多张，并要求所用的钞票数量尽可能少。

请你输出读取值和钞票清单。

钞票的可能面值有 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>

using namespace std;

int main()
{
    int n, a[7] = {100, 50, 20, 10, 5, 2, 1};
    cin >> n;
    printf("%d\n", n);
    for (int i = 0; i < 7; i ++ )
    {
        printf("%d nota(s) de R$ %d,00\n", n / a[i], a[i]);
        n %= a[i];
    }
    return 0;
}

总结

错题总结：之前的做法太过麻烦，可以考虑采用贪心的思想来完成。用余数作为下一次分解的基数。

3.钞票和硬币

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

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

钞票的面值是 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

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    double sum,b[6]={1.00,0.50,0.25,0.10,0.05,0.01};
    int a[6]={100,50,20,10,5,2};
    scanf("%lf",&sum);
    cout<<"NOTAS:"<<endl;
    for(int i=0;i<6;i++)
    {
        printf("%d nota(s) de R$ %d.00\n",(int)(sum/a[i]),a[i]);
        sum-=((int)sum/a[i])*a[i];
    }
    cout<<"MOEDAS:"<<endl;
    for(int i=0;i<6;i++)
    {
    printf("%d moeda(s) de R$ %.2f\n",(int)(sum/b[i]),b[i]);
    printf("%.2f\n",sum);
    sum-=((int)(sum/b[i]))*b[i];
    }

    return 0;
}

错误

第一个测试样例顺利通过，但是第二个测试样例却报了一发WA。

具体结果如下：

输入

463.01

输出

NOTAS:
4 nota(s) de R$ 100.00
1 nota(s) de R$ 50.00
0 nota(s) de R$ 20.00
1 nota(s) de R$ 10.00
0 nota(s) de R$ 5.00
1 nota(s) de R$ 2.00
MOEDAS:
1 moeda(s) de R$ 1.00
1.01
0 moeda(s) de R$ 0.50
0.01
0 moeda(s) de R$ 0.25
0.01
0 moeda(s) de R$ 0.10
0.01
0 moeda(s) de R$ 0.05
0.01
0 moeda(s) de R$ 0.01 //出现问题
0.01

在最末尾的时候明明剩余0.01，0.01/0.01=1，但是却输出0。

总结

你这里的精度丢失如果从底层来考虑的话是因为浮点数的表示所导致的，其实已开始定义的浮点数就是一个近似值，0.01实际是0.010000000000012这样的数，但是如果用减法的话会导致最后我们看到的n显示是0.01但是他实际是一个近似0.01的一个数，但比0.01小，因为定义的比所显示的大所以加上0.00001就解决了这个问题，这样可以使原来不够除的数够除了

因此我们可以对上面小数的输出做以下修改：

printf("%d nota(s) de R$ %.2f\n",(int)(sum/b[i]+0.00001),b[i]);

结果成功AC。