循环小数化为分数的方法

发表于 | 分类于 | | 阅读次数:

修数学双学位的朋友给我出了一道小学奥数题= =，一个以abc为循环节的小数0.abc…，（其中a，b，c都是0～9的整数，且互不相同）。假设它的真分数表达形式为$\frac{m}{n}，0 < n < 100$，求这个范围里的所有的n的可能取值。然而我用程序暴力破解了2333。虽然被朋友谴责了，但是这就是程序猿的解决方式(逃
下面先给出数学求解方式，最后附上暴力破解程序。

参考链接

Wikiwand-循环小数
无限循环小数化分数

数学解法

设x = 0.abcabcabc…，则1000x = abc.abcabcabc…。
1000x - x = abc.abcabcabc… - 0.abcabcabc…，即999x = abc。所以$$x = \frac{abc}{999}$$999的因子有1，3，9，27，37，111，333，999，因为a，b，c各不相同且0 < n < 100，所以n的可能取值为27和37。

维基百科上关于计算更一般情况的解法：
wiki
此外第二个参考链接的博主还提出了一种计算等比数列和的求解方式也很有意思。

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
 *
 * Author : Aincrad
 *
 * Date : Mon 10 Dec 00:11:35 CST 2018
 *
 */
 
#include <bits/stdc++.h>

using namespace std;

string s;

bool ok(string s){
    if(s[2] == s[5] && s[3] == s[6] && s[4] == s[7] && s[2] != s[3] && s[2] != s[4] && s[3] != s[4]){
        return true;
    }
    return false;
}

int gcd(int a, int b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);

    for(int m = 1; m < 100; m++){
        for(int n = m + 1; n < 100; n++){
            double x = (double)m / n;
            stringstream ss;
            ss << x;
            ss >> s;
            if(ok(s)){
                int d = gcd(m, n);
                cout << m / d << " " << n / d << " " << x << endl;
            }
        }
    }

    return 0;
}