算法数学算法

小数转分数

字数统计: 2.5k字   |   阅读时长: 11分
, , ,

摘要: 小数转分数的算法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们来看一下在数学算法中常见的小数转分数的问题。在编程中，除了整数以外，我们主要用的是小数，比如 float、double，但有的时候需要将小数转换为分数。

本文我们首先看一下小数转分数的算法，然后解决力扣 972，本题还涉及在有限字符串上到寻找最小循环节的问题，这里直接从小到大枚举所有可能的循环节来处理。

有限小数转分数

如果是有限小数，可以直接去掉小数点，然后再约分。具体过程是，如果有限小数的小数位数为 l，构造分数 a/b，其中分子 a = x * pow(10, l)，分母 b = pow(10, l)，然后再约分即可。

例如 $x=0.16$，乘以 100 可以去掉小数点，得到 $x = \frac{16}{100}$，然后再约分，得到最终的分数 $\frac{4}{25}$。

大致代码如下：

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
using ll = long long;

struct Fraction
{
    // 分数 x / y
    ll x, y;
    Fraction(ll x, ll y):x(x),y(y){}
    void reduction()
    {
        // 约分
        int _gcd = gcd<int>(x, y);
        x /= _gcd;
        y /= _gcd;
    }
};

int get_fractional_part_len(double x)
{
    // 小数部分长度
    int len = 0;
    while(x - (int)x != 0)
    {
        len++;
        x *= 10;
    }
    return len;
}


Fraction get_fraction(double x)
{
    // x 为有限小数
    int len = get_fractional_part_len(x);
    Fraction ans(x * pow(10, len), pow(10, len));
    ans.reduction();
}

无限循环小数转分数

无限循环小数有三个部分：整数部分，小数不循环部分，小数循环部分。例如 $0.1666\cdots$，整数部分是 0、小数不循环部分为 1、小数循环部分为 6。

首先找到循环节长度 len，将 x 乘以 pow(10, len) 后再减去 x，可以得到一个关于 x 的一元一次方程，进而可以得到 x 的分数表示，约分后可得到最终的分数。算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
例如 x = 0.1(6)

循环节长 len = 1
不循环小数部分长 nonrepeat_len = 1

乘以 10^len 之后的新数: pow(10, 1) * x = 10x = 1.6(6)

新数减去原数
9x = 1.6(6) - 0.1(6) = 1.6 - 0.1 = 0.5

两边乘以 pow(10, nonrepeat_len)
90x = 16 - 1

约分后，得到最终的分数：
x = 15 / 90 = 1 / 6

该算法理解起来不难，但在实现时有几个要点，容易出错：

  • 需要首先得到循环节长度 len，不循环小数部分的长度 nonrepeat_len，根据小数是以浮点数给出还是字符串给出，实现相应的解析逻辑。
  • 不循环小数部分的长度需要以循环节最早出现的位置计算。
  • 循环节的长度需要以最短的循环节为准。
  • 构造一元一次方程的过程，系数是以整数部分，小数不循环部分共同表示的，构造的时候注意 len >= nonrepeat_len 和 len < nonrepeat_len 两种情况分类讨论。

具体的代码细节见后面的题目，题目的代码可以作为模板。

题目

给定两个字符串 S 和 T，每个字符串代表一个非负有理数，只有当它们表示相同的数字时才返回 true；否则，返回 false。字符串中可以使用括号来表示有理数的重复部分。

通常，有理数最多可以用三个部分来表示：整数部分 、小数非重复部分 和小数重复部分 <(><)>。数字可以用以下三种方法之一来表示：

1
2
3
<IntegerPart>（例：0，12，123）
<IntegerPart><.><NonRepeatingPart> （例：0.5，2.12，2.0001）
<IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)>（例：0.1(6)，0.9(9)，0.00(1212)）

十进制展开的重复部分通常在一对圆括号内表示。例如：

1 / 6 = 0.16666666… = 0.1(6) = 0.1666(6) = 0.166(66)

0.1(6) 或 0.1666(6) 或 0.166(66) 都是 1 / 6 的正确表示形式。

提示：

1
2
3
4
5
每个部分仅由数字组成。
整数部分 <IntegerPart> 不会以零开头。（零本身除外）
1 <= <IntegerPart>.length <= 4
0 <= <NonRepeatingPart>.length <= 4
1 <= <RepeatingPart>.length <= 4

示例 1：
输入：s = “0.(52)”, t = “0.5(25)”
输出：true
解释：因为 “0.(52)” 代表 0.52525252…，而 “0.5(25)” 代表 0.52525252525…..，则这两个字符串表示相同的数字。

示例 2：
输入：s = “0.1666(6)”, t = “0.166(66)”
输出：true

示例 3：
输入：s = “0.9(9)”, t = “1.”
输出：true
解释：”0.9(9)” 代表 0.999999999… 永远重复，等于 1 。[有关说明，请参阅此链接]
“1.” 表示数字 1，其格式正确：(IntegerPart) = “1” 且 (NonRepeatingPart) = “” 。

算法：小数转分数

将两个字符串表示的小数分别转换为分数，然后分别约分，比较它们的分子分母。

分数的表示以及约分操作放到一个结构体 Fraction 中。

将字符串表示的小数转换为结构体 Fraction 表示的分数过程如下：

step1

枚举字符 i = 0,1,...,n-1，直至左括号，中途如果遇到小数点，则记录小数点位置，顺便得到整数部分。

枚举结束后:

  • 如果枚举过程没有遇到小数点，需要单独更新整数部分，不循环小数部分为 0。
  • 如果枚举过程遇到了小数点，整数部分已经更新过，需要更新不循环小数部分。

step2

继续枚举字符 j = i+1,i+1,...,n-1，直至右括号(如果 i == n，则这一步自动跳过)

枚举结束后S[i+1..j-1] 为括号内的部分。但这个循环节有两个问题

  1. 这个括号标记的循环节不一定是最短循环节，需要求最短循环节长度记为 len，得到真正的循环节长度。
  2. i+1 这个位置不一定是循环节最早出现的位置，需要从后往前枚举不循环小数部分并判断是否为循环节，直至不属于循环节的位置，得到真正的循环节最早出现位置。

step3

至此已经有了 ll 类型的整数部分 integerPart，不循环小数部分 nonRepeatingPart 以及其长度 nonrepeat_len，循环节 repeatingPart，以及其长度 len。算法就是前面讲过的小数转分数的算法，有以下细节需要注意：

  • 如果 nonRepeatingPart 和 repeatingPart 均为零，则直接返回 Fraction(integerPart, 1)
  • 如果 repeatingPart 不为零，则先通过整体右移 len 长度，即乘以 pow(10, len) 再与原数做差的方式去掉循环节。过程中需要按照 nonrepeat_len >= len 和 nonrepeat_len < len 分类讨论。最终得到修正后的 integerPart 和 nonRepeatingPart
    • 如果修正后的 nonRepeatingPart 为零，则直接返回 Fraction(integerPart, 1)
    • 否则返回 Fraction(integerPart * pow(10, nonrepeat_len) + nonRepeatingPart, pow(10, nonrepeat_len))

代码 (C++) (模板：小数转分数)

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
using ll = long long;

struct Fraction
{
    // 分数 x / y
    ll x, y;
    Fraction(ll x, ll y):x(x),y(y){}
    void reduction()
    {
        // 约分
        int _gcd = gcd<int>(x, y);
        x /= _gcd;
        y /= _gcd;
    }
};

int repetent(const string& S)
{
    // 有限长的串上寻找最短循环节
    int n = S.size();
    for(int i = 1; i * 2 <= n; ++i)
    {
        if(n % i != 0)
            continue;
        string p = S.substr(0, i);
        bool flag = true;
        for(int j = i; j < n; j += i)
        {
            if(S.substr(j, i) != p)
            {
                flag = false;
                break;
            }
            if(flag)
                return i;
        }
    }
    return n;
}

class Solution {
public:
    bool isRationalEqual(string S, string T) {
        Fraction fracS = to_frac(S);
        Fraction fracT = to_frac(T);
        fracS.reduction();
        fracT.reduction();
        return fracS.x == fracT.x && fracS.y == fracT.y;
    }

private:

    Fraction to_frac(const string& S)
    {
        int n = S.size();
        int i = 0; // 左括号位置
        int dot_idx = -1; // 小数点位置
        int nonrepeat_len = 0; // 不循环部分的长度
        int len = 0; // 循环节长度

        // 解析字符串，得到整数部分、小数不循环部分、小数循环部分
        ll integerPart = 0, nonRepeatingPart = 0, repeatingPart = 0;
        while(i < n && S[i] != '(')
        {
            // 整数部分
            if(S[i] == '.')
            {
                dot_idx = i;
                stringstream ss;
                ss << S.substr(0, dot_idx);
                ss >> integerPart;
            }
            ++i;
        }
        if(dot_idx == -1)
        {
            // i == n 退出的，没有不循环小数部分
            stringstream ss;
            ss << S.substr(0, i);
            ss >> integerPart;
        }
        else if(i - dot_idx - 1 > 0)
        {
            // S[i] == '(' 退出的
            // 不循环小数部分
            nonrepeat_len = i - dot_idx - 1;
            stringstream ss;
            ss << S.substr(dot_idx + 1, i - dot_idx - 1);
            ss >> nonRepeatingPart;
        }

        int j = i + 1; // 右括号位置
        while(j < n && S[j] != ')')
            ++j;
        if(j < n)
        {
            len = repetent(S.substr(i + 1, j - i - 1)); // 最短循环节长度
            // nonRepeatingPart 中往前找与 p 重合的部分
            string p = S.substr(i + 1, len);
            string t = S.substr(dot_idx + 1, i - dot_idx - 1);
            int idx = t.size() - 1;
            int iter = p.size() - 1;
            while(idx >= 0 && t[idx] == p[iter])
            {
                --idx;
                iter = (iter - 1 + len) % len;
            }
            // 重合部分长度，给定的循环节位置不是循环节最早出现的位置，需要调整
            int shift = nonrepeat_len - (idx + 1);
            nonrepeat_len = idx + 1;
            // 调整后的不循环小数部分长度
            if(nonrepeat_len == 0)
                nonRepeatingPart = 0;
            else
            {
                stringstream ss;
                ss << t.substr(0, nonrepeat_len);
                ss >> nonRepeatingPart;
            }
            // 调整后的循环节
            shift %= len;
            rotate(p.begin(), p.begin() + shift,  p.end());
            stringstream ss;
            ss << p;
            ss >> repeatingPart;
        }

        // 小数转分数算法
        if(nonRepeatingPart == 0 && repeatingPart == 0)
            return Fraction(integerPart, 1);
        if(repeatingPart != 0)
        {
            // 乘以 pow(10, len) 之后的整数，不循环小数部分，循环节
            ll new_integerPart = integerPart;
            ll new_repeatingPart = repeatingPart;
            ll new_nonRepeatingPart = nonRepeatingPart;

            new_integerPart = new_integerPart * pow(10, len);
            if(nonrepeat_len >= len)
            {
                int delta = nonrepeat_len - len;
                new_integerPart += new_nonRepeatingPart / (ll)pow(10, delta);
                new_nonRepeatingPart %= (ll)pow(10, delta);
                new_nonRepeatingPart *= pow(10, len);
                new_nonRepeatingPart += new_repeatingPart;
            }
            else
            {
                int delta = len - nonrepeat_len;
                new_integerPart += new_nonRepeatingPart * (ll)pow(10, delta);
                new_integerPart += new_repeatingPart / (ll)pow(10, nonrepeat_len);
                new_nonRepeatingPart = new_repeatingPart % (ll)pow(10, nonrepeat_len);
            }
            // 乘以 pow(10, len) 之后的数与原数相减，整数和不循环小数部分分别做差再加起来
            integerPart = new_integerPart - integerPart;
            integerPart *= pow(10, nonrepeat_len);
            nonRepeatingPart = new_nonRepeatingPart - nonRepeatingPart;
            integerPart += nonRepeatingPart;
            return Fraction(integerPart, (pow(10, len) - 1) * pow(10, nonrepeat_len));
        }
        if(nonRepeatingPart == 0)
            return Fraction(integerPart, 1);
        return Fraction(integerPart * pow(10, nonrepeat_len) + nonRepeatingPart, pow(10, nonrepeat_len));
    }
};
Share