Problem.png
给定一个分式(除式)，求商(小数形式)中循环的小数部分，并将其用括号括起来，超过50个字符用...标记。
本题就是对手算除法过程的模拟。
回忆一下竖式除法的步骤，假设分子为a，分母为b，则先用a/b得出商的整数部分，获得余数a%b后，要借一位继续进行除法，而借一位就相当于对余数乘10，之后再除以b得到的就是小数点后第一位的商，以此类推。
那么如何得出商中小数的循环部分呢？再回忆竖式除法，当某一次获得的余数跟前面某次得到的余数相同时，说明后面的计算跟前面的肯定也还是一样，那么商的小数部分就开始了第二次循环。因此只需在每次得到余数时，都以该余数为索引在数组中mark一下它的出现，等到某次碰到重复出现的余数时，就知道我们到达了商的小数部分的第二次循环的开始处，此时就可以结束循环了。同时为了用括号标记出循环部分，我们还需要记录每个余数对应的是商中小数点后哪一位小数，从而得出商中循环部分的起始位置。
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
// 模拟手算除法的过程
int main() {
int nu, de; // nu为分子，de为分母
while (cin >> nu >> de) {
int mark[3005] = {0}; // 记录余数的出现及对应商中的位置
printf("%d/%d = %d.", nu, de, nu / de);
int i;
string frac = ""; // 存储商的小数部分
for (i = 1; ; i++) {
nu = nu % de; // 获得新的余数
if (mark[nu]) { // 若该余数已出现过，就说明找到了循环
break;
}
mark[nu] = i; // 若该余数没出现过，就标记它对应的是商中小数点后哪一位
nu = nu * 10; // 乘10借位，准备进行下一步除法
frac.push_back(nu / de + '0');
}
int end = i - 1; // 循环小数结束处
int start = mark[nu]; // 循环小数开始处
for (int j = 0; j < end && j < 50; j++) {
if (j == start - 1) {
printf("(");
}
printf("%c", frac[j]);
}
if (end - start >= 50) { // 若小数的循环部分长度大于50，则肯定要打...
printf("...");
}
printf(")\n");
printf(" %d = number of digits in repeating cycle\n\n", end - start + 1);
}
return 0;
}
