每日算法刷题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。

目录
相关文章
|
7月前
|
机器学习/深度学习 存储 算法
【算法沉淀】刷题笔记:并查集 带权并查集+实战讲解
【算法沉淀】刷题笔记:并查集 带权并查集+实战讲解
|
7月前
|
自然语言处理 算法
算法刷题(二十三):Bigram 分词
算法刷题(二十三):Bigram 分词
68 0
|
7月前
|
算法
算法刷题(二十二):宝石与石头
算法刷题(二十二):宝石与石头
67 0
|
6月前
|
存储 算法 C语言
【数据结构与算法 刷题系列】合并两个有序链表
【数据结构与算法 刷题系列】合并两个有序链表
|
2月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
16 0
|
4月前
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
|
4月前
|
算法 Python
【Leetcode刷题Python】改进的算法,高效求一个数的因子
一个高效的Python函数用于找出一个整数的所有因子,通过仅遍历到该数平方根的范围来优化性能。
43 0
|
6月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
6月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
6月前
|
算法
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)