【蓝桥杯】有理数的循环节
2022/2/8 6:14:04
本文主要是介绍【蓝桥杯】有理数的循环节,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
有理数的循环节
1 / 7 = 0.142857142 ⋯ ⋯ 1/7 = 0.142857142 \cdots\cdots 1/7=0.142857142⋯⋯ 是个无限循环小数。
任何有理数都可以表示为无限循环小数的形式。
题目要求即是:给出一个数字的循环小数表示法。
输入描述
输入一行,两个整数。
每个整数范围均为:1 ~ 1000。
输出描述
输出两个整数做除法产生的小数或无限循环小数(循环节用方括号括起)。
输入输出样例
示例
输入
1,7
输出
0.[142857]
思路
- 先模拟手算,找规律,这里不妨用题目所给的例子:
1
÷
7
1 \div 7
1÷7
- 1除以7,商0余1,点上小数点,余数不为0,则把余数1乘以10之后继续除以7(即“添0继续除”)
- 10除以7,商1余3,余数不为0,添0继续除
- 30除以7,商4余2,余数不为0,添0继续除
- 20除以7,商2余6,余数不为0,添0继续除
- 60除以7,商8余4,余数不为0,添0继续除
- 40除以7,商5余5,余数不为0,添0继续除
- 50除以7,商7余1,余数不为0,添0继续除
- ⋯ ⋯ \cdots\cdots ⋯⋯
到这里,可能已经看出规律了,再继续除下去的话就循环起来了,则已经找出了循环节
- 然后发现,循环节的最后一个数出现的时候,其对应的余数恰好是出现过的,而这个余数上一次出现时乘10除以除数得到的商恰好是循环节的第一个数
- 这样问题就差不多解决了,因为已经确定了循环节的首尾位置
- 由于题目还要求输出中括号,所以商用一个数组来存放比较方便
- 怎么知道余数已经出现过了?怎么确定循环节的第一个数字?
- 综合考虑,选用哈希表记录出现过的余数,并且将余数和小数点后的位号(数组下标)建立联系,方便确定循环节
- 通过模拟,应该还能得出一个显然的规律:当相除的结果是无限循环小数时,最后一个数字一定是循环节的最后一个数字,且最终答案的最后一个字符一定是 ] ] ];而除得尽的话,就直接输出结果就行,但是依然要用数组来存放,因为好判断是否能除尽
- 将商的整数部分和小数部分分开比较好
代码如下
#include <iostream> #include <unordered_map> #include <vector> using namespace std; unordered_map<int, int> mp; //余数<->下标 vector<int> data; //存放小数部分的数组 int n, m; //分子,分母 void solve() { int res = 0; //整数部分商 int t = 0; //下标 scanf("%d,%d", &n, &m);//坑点,要把逗号加进去 //处理整数部分 res = n / m; n %= m; mp[n] = t++; //处理小数部分 while (true) { if (n == 0) { //这是除得尽的情况 printf("%d.", res);//整数部分 //小数部分全部输出 for (int i = 0; i < int(data.size()); i++) { printf("%d", data.at(i)); } printf("\n"); break; } n *= 10;//添0继续除 data.push_back(n / m);//商 n %= m;//余数更新被除数 //余数不为0且余数出现过 if (n && mp.find(n) != mp.end()) { printf("%d.", res);//输出整数部分 //输出循环节之前的小数部分,有些循环小数要等几个数之后才开始循环 for (int i = 0; i < mp[n]; i++) { printf("%d", data.at(i)); } //输出循环节 printf("["); for (int i = mp[n]; i < (int)data.size(); i++) { printf("%d", data.at(i)); } printf("]\n"); break; } else { //否则加入 mp[n] = t++; } } } int main(void) { solve(); return 0; }
这篇关于【蓝桥杯】有理数的循环节的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?