有理数的循环节
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;
}