引言

前一阵做了一个有理数四则混合运算的程序（详见：用C++实现的有理数（分数）四则混合运算计算器），以分数形式呈现运算结果。这次添加以循环小数形式呈现运算结果的功能。例如：

Please input a rational expression to calculate its value or input q to quit:

67+34*(23-78/(54*5))-2*(5/37-6.5789)
= 67 + 34 * ( 23 - 78 / ( 270 ))-2*(5/37-6.5789)
= 67 + 34 * ( 23 - 13/45 )-2*(5/37-6.5789)
= 67 + 34 * ( 1022/45 )-2*(5/37-6.5789)
= 67 + 34748/45 -2*(5/37-6.5789)
= 37763/45 -2*(5/37-6.5789)
= 37763/45 - 2 * ( 5/37 -6.5789)
= 37763/45 - 2 * ( 5/37 - 65789/10000 )
= 37763/45 - 2 * ( -2384193/370000 )
= 37763/45 - -2384193/185000
= 852[108737/1665000] {852.0653`075}

算法分析

由分数化循环小数不像由循环小数化分数那么简单明了。比如 0.2`142857 这个小数，它等于 0.2 加上 0.0`142857，用分数表示分别是 2/10 和 142857/9999990，化简即是 1/5 和 1/70，相加并化简得到分数运算结果：3/14。

现在考察由 3/14 如何反推出 0.2`142857。

1、3 / 14 = 0…3  商为0，得到小数形式结果的整数部分，余数不为0，继续

2、30 / 14 = 2…2  商为2，得到小数点后第1位小数，余数不为0，继续

3、20 / 14 = 1…6  商为1，得到小数点后第2位小数，余数不为0，继续

4、60 / 14 = 4…4 商为4，得到小数点后第3位小数，余数不为0，继续

5、40 / 14 = 2…12 商为2，得到小数点后第4位小数，余数不为0，继续

6、120 / 14 = 8…8 商为8，得到小数点后第5位小数，余数不为0，继续

7、80 / 14 = 5…10 商为5，得到小数点后第6位小数，余数不为0，继续

8、100 / 14 = 7…2 商为7，得到小数点后第7位小数，余数不为0，继续

9、20 / 14 = 1…6  商为1，得到小数点后第8位小数，余数不为0，继续

……

上述试商过程，当进行到第8步时，得到的余数是2，和第2步得到的余数相同，于是从第9步开始就会周而复始重复第3步到第8步的过程。说明已经找到了循环小数的循环体。

由于余数要小于指定的除数（即分数中的分母），上述过程必然会在有限的步数（小于除数）出现相同余数。

算法实现

在 SFraction 里增加 toDecimal 接口：

1 struct SFraction
2 {
3 u64 numerator;
4 u64 denominator;
5 bool bNegative;
6
7 SFraction() {
8 numerator = 0;
9 denominator = 1;
10 bNegative = false;
11 }
12
13 std::string toStr(bool bFinal = false) const;
14 std::string toDecimalStr() const;
15 };

SFraction 的 toDecimal 接口实现如下：

1 std::string SFraction::toDecimalStr() const
2 {
3 std::ostringstream oStream;
4 if (bNegative)
5 {
6 oStream << "-"; 7 } 8 u64 quotient = numerator / denominator; 9 oStream << quotient; 10 u64 remainder = numerator % denominator; 11 if (remainder == 0) 12 { 13 return oStream.str(); 14 } 15 oStream << "."; 16 u64 pos = 0; 17 u64 posMatched = 0; 18 std::map mapRemainderPos;
19 std::vector vecQuotient;
20 while (true)
21 {
22 mapRemainderPos[remainder] = pos++;
23 remainder *= 10;
24 vecQuotient.push_back(remainder / denominator);
25 remainder = remainder % denominator;
26 if (remainder == 0)
27 break;
28 std::map::iterator it = mapRemainderPos.find(remainder);
29 if (it != mapRemainderPos.end())
30 {
31 posMatched = it->second;
32 break;
33 }
34 }
35 if (remainder == 0)
36 {
37 for (size_t idx = 0; idx < vecQuotient.size(); ++idx)
38 oStream << vecQuotient[idx];
39 return oStream.str();
40 }
41 size_t idx = 0;
42 for (; idx < posMatched; ++idx)
43 oStream << vecQuotient[idx];
44 oStream << "`";
45 for (; idx < vecQuotient.size(); ++idx)
46 oStream << vecQuotient[idx];
47 return oStream.str();
48 }

然后对 SFraction 的 toStr 接口稍作调整，即可达到增加循环小数形式的呈现效果：

1 std::string SFraction::toStr(bool bFinal) const
2 {
3 std::ostringstream oStream;
4 if (bNegative)
5 {
6 oStream << "-";
7 }
8 if (denominator == 1)
9 {
10 oStream << numerator;
11 return oStream.str();
12 }
13 if (!bFinal)
14 {
15 oStream << numerator << "/" << denominator;
16 return oStream.str();
17 }
18 if (numerator < denominator)
19 {
20 oStream << numerator << "/" << denominator << " {" << toDecimalStr() << "}";
21 return oStream.str();
22 }
23 u64 quotient = numerator / denominator;
24 u64 remainder = numerator % denominator;
25 oStream << quotient << "[" << remainder << "/" << denominator << "] {" << toDecimalStr() << "}";
26 return oStream.str();
27 }

完整代码文件提取位置

https://github.com/readalps/RationalCalculator