【UVA-202】Repeating Decimals【紫书】

【UVA-202】Repeating Decimals【紫书】

问题链接:https://vjudge.net/problem/UVA-202

udebug数据链接:https://www.udebug.com/UVa/202

Solution:

模拟除法过程,需要注重细节,建议编码之前有一个大致规划再开始,不然编完后遇到问题不易修改。循环的启动时状态是:rest中存放a % b,之后开始循环,每次循环执行顺序是:rest变为10倍→判断这个数是否出现过(出现过的话就说明找到了循环节)→判断rest是否比b大(如果小于b说明这位应该补零并直接进入下次循环)→进行运算→判断是否整除(整除说明运算结束,不是循环小数,可以跳出循环)→修改ans,并且准备好下一次循环的初始状态(即rest的值)。

#include <iostream>
#include <map>
#include <string>

using namespace std;

map<int, int> pos;

void solve(string & ans, int & rest, int num, const int b) {
    ans = ".";
    pos.clear();

    while (true) {
        num *= 10;
        int p = pos[num];

        if (p == 0) {
            pos[num] = ans.size();
        } else {
            rest = ans.size() - p;
            if (rest > 50) {
                ans.erase(p + 50);
                ans += "...";
            }
            ans.insert(p, "(");
            ans += ")";
            break;
        }

        //do the cal
        if (num < b) {
            ans += "0";         //不够除的情况
        } else {
            int div = num / b, mod = num % b;
            ans += (char)(div + '0');
            if (!mod) {         //整除
                ans += "(0)";
                rest = 1;
                break;
            }
            num = mod;          //迭代余数到被除数上
        }
    }
}

int main(void) {
    int a, b;
    while (scanf("%d%d", &a, &b) == 2) {
        string ans = ".(0)";
        int r = 1;
        if (a % b)
            solve(ans, r, a % b, b);
        printf("%d/%d = %d%s\n", a, b, a / b, ans.c_str());
        printf("   %d = number of digits in repeating cycle\n\n", r);
    }
    return 0;
}