面试题-判断无限循环小数

发表于   |  

题目：正整数A、B，判断A/B是否为无限循环小数，若是，找出循环部分。如1/7，循环部分为142857。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/*
 * 判断两数相除是否为无限循环小数，如果是，找出循环的部分
 */
public class RepeatDecimal
{
    private int _dividend;
    private int _divider;
    public RepeatDecimal(int dividend, int divider)
    {
        _dividend = dividend;
        _divider = divider;
    }
    /*
     * 判断是否为无限循环小数
     */
    public bool IsRpeatDecimal()
    {
        // 分子为0
        if (_dividend == 0) return false;
        // 分母为0
        if (_divider == 0) throw new Exception("Divider is zero");
        // 先找到最大公约数，化为最简分数
        var gcd = getGCD();
        int tmp = _divider / gcd;
        // 分母存在2、5以外的因数，则无限循环
        while (tmp % 2 == 0) tmp /= 2;
        while (tmp % 5 == 0) tmp /= 5;
        return tmp != 1;
    }
    /*
     * 获取循环部分
     */
    public string GetRepeatPart()
    {
        if (!IsRpeatDecimal()) return null;
        string result = "";
        var a = Math.Abs(_dividend);
        var b = Math.Abs(_divider);
        // 模拟除法
        List<int> decimals = new List<int>();
        while (a > b) a -= b;
        while (true)
        {
            while (a < b) {
                a *= 10;
            }
            // 如果商之前得到过，则找到了循环部分
            int quotient = a / b;
            int index = decimals.IndexOf(quotient);
            if (index >= 0)
            {
                for (var i = index; i < decimals.Count; ++i)
                {
                    result += decimals[i];
                }
                break;
            }
            else
            {
                decimals.Add(quotient);
            }
            a %= b;
        }
        return result;
    }
    private int getGCD()
    {
        int a = _dividend;
        int b = _divider;
        int c = 0;
        while (true)
        {
            c = a % b;
            a = b;
            b = c;
            if (b == 0)
            {
                return a;
            }
        }
    }
}