华中科技大学18年机试第三题：循环小数

一、题目描述

输入一个带除法运算的字符串，输出运算结果。其中，除不尽的，如果有循环小数，要用括号标识循环体。
输入：$8 / 5$8/5 输出：$1.6$1.6而不是$1.6000...$1.6000...
输入：$1 / 3$1/3 输出：$.(3)$.(3)(而不是$0.333...$0.333...
输入：$11 / 13$11/13 输出：$.(846153)$.(846153)

二、解题思路

这道题重点是怎么找到循环节的位置。

• 我们知道，任意两个自然数相除一定是无限循环小数
• 首先，先输出结果的整数部分，这步很简单，记得保存当前这步剩下的余数
• 然后，我们可以维护一个vector，该vector储存当前的被除数。每次进行运算时，先将操作的被除数乘以$10$10，重复上述操作，得到一个新的余数
• 到vector中去找现在得到的被除数是不是在里面，如果不是，将这个数加入vector，否则就说明找到了循环节，退出

三、解题代码

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
bool VecFind(const vector<unsigned int> &vec, unsigned int num, int &loc){
    loc = -1;
    for (unsigned int i = 0; i < vec.size(); i++){
        if (num == vec[i]){
            loc = i;
            return true;
        }
    }
    return false;
}
void sln(unsigned int n, unsigned int m){
    if (!m){
        cout << "m can not be zero!" << endl;
        return;
    }
    if (!n){
        cout << 0 << endl;
        return;
    }
    if (n % m == 0){
        cout << n / m << endl;
        return;
    }
    vector<unsigned int> vec, output;
    if(n / m)	//处理输出.(3)而不是0.(3)的情况
		cout << n / m;
	cout  << ".";
    unsigned int cur_num = n / m, remain = n % m;
    int find_cur_num = -1;
    while (1){
        auto cur_n = remain * 10;//当前操作数（被除数）为上一步的余数 * 10
        cur_num = cur_n / m;	 //当前步得到的要输出的数字
        remain = cur_n % m;	     //当前步得到的余数
        if (VecFind(vec, cur_n, find_cur_num))
            break;
        else{
            vec.push_back(cur_n);
            output.push_back(cur_num);
        }
    }
    for (unsigned int i = 0; i < find_cur_num; i++)		//输出循环节开始之前的小数数字，比如 7 / 6 = 1.1(3)
        cout << output[i];
    if (find_cur_num == output.size() - 1 && output[find_cur_num] == 0) {}	//可以整除，不用输出循环节，直接返回
    else{
        cout << "(";
        for (unsigned int i = find_cur_num; i < output.size(); i++)
            cout << output[i];
        cout << ")";
    }
    cout << endl;
}
int main(){
    unsigned int n, m;
    while (scanf("%d/%d", &n, &m))
        sln(n, m);
    return 0;
}

四、运行结果