首页 / 知识

关于算法：如何将浮点数转换为人类可读的分数？

2023-04-17 08:09:00

How to convert floats to human-readable fractions?

假设我们有0.33，我们需要输出" 1/3"。
如果我们有" 0.4"，我们需要输出" 2/5"。

这样做的想法是使用户易于理解，以使用户理解" y之外的x个部分"，作为理解数据的更好方法。

我知道百分比是一个很好的替代品，但我想知道是否有简单的方法可以做到这一点？

我发现David Eppstein对给定的实数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

/*
** find rational approximation to given real number
** David Eppstein / UC Irvine / 8 Aug 1993
**
** With corrections from Arno Formella, May 2008
**
** usage: a.out r d
** r is real number to approx
** d is the maximum denominator allowed
**
** based on the theory of continued fractions
** if x = a1 + 1/(a2 + 1/(a3 + 1/(a4 + ...)))
** then best approximation is found by truncating this series
** (with some adjustments in the last term).
**
** Note the fraction can be recovered as the first column of the matrix
** ( a1 1 ) ( a2 1 ) ( a3 1 ) ...
** ( 1 0 ) ( 1 0 ) ( 1 0 )
** Instead of keeping the sequence of continued fraction terms,
** we just keep the last partial product of these matrices.
*/

#include <stdio.h>

main(ac, av)
int ac;
char ** av;
{
double atof();
int atoi();
void exit();

long m[2][2];
double x, startx;
long maxden;
long ai;

/* read command line arguments */
if (ac != 3) {
fprintf(stderr,"usage: %s r d
",av[0]); // AF: argument missing
exit(1);
}
startx = x = atof(av[1]);
maxden = atoi(av[2]);

/* initialize matrix */
m[0][0] = m[1][1] = 1;
m[0][1] = m[1][0] = 0;

/* loop finding terms until denom gets too big */
while (m[1][0] * ( ai = (long)x ) + m[1][1] <= maxden) {
long t;
t = m[0][0] * ai + m[0][1];
m[0][1] = m[0][0];
m[0][0] = t;
t = m[1][0] * ai + m[1][1];
m[1][1] = m[1][0];
m[1][0] = t;
if(x==(double)ai) break; // AF: division by zero
x = 1/(x - (double) ai);
if(x>(double)0x7FFFFFFF) break; // AF: representation failure
}

/* now remaining x is between 0 and 1/ai */
/* approx as either 0 or 1/m where m is max that will fit in maxden */
/* first try zero */
printf("%ld/%ld, error = %e
", m[0][0], m[1][0],
startx - ((double) m[0][0] / (double) m[1][0]));

/* now try other possibility */
ai = (maxden - m[1][1]) / m[1][0];
m[0][0] = m[0][0] * ai + m[0][1];
m[1][0] = m[1][0] * ai + m[1][1];
printf("%ld/%ld, error = %e
", m[0][0], m[1][0],
startx - ((double) m[0][0] / (double) m[1][0]));
}

从Python 2.6开始，提供了fractions模块。

(引自文档。)

1
2
3
4
5
6
7
8
9

>>> from fractions import Fraction
>>> Fraction('3.1415926535897932').limit_denominator(1000)
Fraction(355, 113)

>>> from math import pi, cos
>>> Fraction.from_float(cos(pi/3))
Fraction(4503599627370497, 9007199254740992)
>>> Fraction.from_float(cos(pi/3)).limit_denominator()
Fraction(1, 2)

如果输出是为了使读者快速了解结果的顺序，则返回" 113/211"之类的内容是没有意义的，因此输出应将自身限制为使用一位数字(也许是1 / 10和9/10)。如果是这样，您可以观察到只有27个不同的分数。

由于生成输出的基础数学永远不会改变，因此解决方案可以是简单地对二进制搜索树进行硬编码，以便该函数最多执行log(27)?= 4 3/4比较。这是经过测试的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
166
167
168
169

char *userTextForDouble(double d, char *rval)
{
if (d == 0.0)
return"0";

// TODO: negative numbers:if (d < 0.0)...
if (d >= 1.0)
sprintf(rval,"%.0f", floor(d));
d = d-floor(d); // now only the fractional part is left

if (d == 0.0)
return rval;

if( d < 0.47 )
{
if( d < 0.25 )
{
if( d < 0.16 )
{
if( d < 0.12 ) // Note: fixed from .13
{
if( d < 0.11 )
strcat(rval,"1/10"); // .1
else
strcat(rval,"1/9"); // .1111....
}
else // d >= .12
{
if( d < 0.14 )
strcat(rval,"1/8"); // .125
else
strcat(rval,"1/7"); // .1428...
}
}
else // d >= .16
{
if( d < 0.19 )
{
strcat(rval,"1/6"); // .1666...
}
else // d > .19
{
if( d < 0.22 )
strcat(rval,"1/5"); // .2
else
strcat(rval,"2/9"); // .2222...
}
}
}
else // d >= .25
{
if( d < 0.37 ) // Note: fixed from .38
{
if( d < 0.28 ) // Note: fixed from .29
{
strcat(rval,"1/4"); // .25
}
else // d >=.28
{
if( d < 0.31 )
strcat(rval,"2/7"); // .2857...
else
strcat(rval,"1/3"); // .3333...
}
}
else // d >= .37
{
if( d < 0.42 ) // Note: fixed from .43
{
if( d < 0.40 )
strcat(rval,"3/8"); // .375
else
strcat(rval,"2/5"); // .4
}
else // d >= .42
{
if( d < 0.44 )
strcat(rval,"3/7"); // .4285...
else
strcat(rval,"4/9"); // .4444...
}
}
}
}
else
{
if( d < 0.71 )
{
if( d < 0.60 )
{
if( d < 0.55 ) // Note: fixed from .56
{
strcat(rval,"1/2"); // .5
}
else // d >= .55
{
if( d < 0.57 )
strcat(rval,"5/9"); // .5555...
else
strcat(rval,"4/7"); // .5714
}
}
else // d >= .6
{
if( d < 0.62 ) // Note: Fixed from .63
{
strcat(rval,"3/5"); // .6
}
else // d >= .62
{
if( d < 0.66 )
strcat(rval,"5/8"); // .625
else
strcat(rval,"2/3"); // .6666...
}
}
}
else
{
if( d < 0.80 )
{
if( d < 0.74 )
{
strcat(rval,"5/7"); // .7142...
}
else // d >= .74
{
if(d < 0.77 ) // Note: fixed from .78
strcat(rval,"3/4"); // .75
else
strcat(rval,"7/9"); // .7777...
}
}
else // d >= .8
{
if( d < 0.85 ) // Note: fixed from .86
{
if( d < 0.83 )
strcat(rval,"4/5"); // .8
else
strcat(rval,"5/6"); // .8333...
}
else // d >= .85
{
if( d < 0.87 ) // Note: fixed from .88
{
strcat(rval,"6/7"); // .8571
}
else // d >= .87
{
if( d < 0.88 ) // Note: fixed from .89
{
strcat(rval,"7/8"); // .875
}
else // d >= .88
{
if( d < 0.90 )
strcat(rval,"8/9"); // .8888...
else
strcat(rval,"9/10"); // .9
}
}
}
}
}
}

return rval;
}

以下是一个链接，解释了将小数转换为分数的数学原理：

http://www.webmath.com/dec2fract.html

这是一个示例函数，说明如何使用VB实际执行此操作(来自www.freevbcode.com/ShowCode.asp?ID=582)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Public Function Dec2Frac(ByVal f As Double) As String

Dim df As Double
Dim lUpperPart As Long
Dim lLowerPart As Long

lUpperPart = 1
lLowerPart = 1

df = lUpperPart / lLowerPart
While (df <> f)
If (df < f) Then
lUpperPart = lUpperPart + 1
Else
lLowerPart = lLowerPart + 1
lUpperPart = f * lLowerPart
End If
df = lUpperPart / lLowerPart
Wend
Dec2Frac = CStr(lUpperPart) &"/" & CStr(lLowerPart)
End Function

(从谷歌搜索：将小数转换为分数，将小数转换为分数代码)

您可能想阅读每位计算机科学家应该知道的有关浮点运算的知识。

您必须通过乘以大数来指定一些精度：

1	3.141592 * 1000000 = 3141592

那么你可以做一个分数：

1	3 + (141592 / 1000000)

并通过GCD减少...

1	3 + (17699 / 125000)

但无法将预期的分数去除。您可能希望始终在整个代码中使用分数-记住要尽量减少分数，以免发生溢出！

这是devinmoore建议的VB代码的Perl和Javascript版本：

Perl：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

sub dec2frac {
my $d = shift;

my $df = 1;
my $top = 1;
my $bot = 1;

while ($df != $d) {
if ($df < $d) {
$top += 1;
}
else {
$bot += 1;
$top = int($d * $bot);
}
$df = $top / $bot;
}
return"$top/$bot";
}

和几乎相同的javascript：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function dec2frac(d) {

var df = 1;
var top = 1;
var bot = 1;

while (df != d) {
if (df < d) {
top += 1;
}
else {
bot += 1;
top = parseInt(d * bot);
}
df = top / bot;
}
return top + '/' + bot;
}

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

/// <summary>
/// Represents a rational number
/// </summary>
public struct Fraction
{
public int Numerator;
public int Denominator;

/// <summary>
/// Constructor
/// </summary>
public Fraction(int numerator, int denominator)
{
this.Numerator = numerator;
this.Denominator = denominator;
}

/// <summary>
/// Approximates a fraction from the provided double
/// </summary>
public static Fraction Parse(double d)
{
return ApproximateFraction(d);
}

/// <summary>
/// Returns this fraction expressed as a double, rounded to the specified number of decimal places.
/// Returns double.NaN if denominator is zero
/// </summary>
public double ToDouble(int decimalPlaces)
{
if (this.Denominator == 0)
return double.NaN;

return System.Math.Round(
Numerator / (double)Denominator,
decimalPlaces
);
}

/// <summary>
/// Approximates the provided value to a fraction.
/// http://stackoverflow.com/questions/95727/how-to-convert-floats-to-human-readable-fractions
/// </summary>
private static Fraction ApproximateFraction(double value)
{
const double EPSILON = .000001d;

int n = 1; // numerator
int d = 1; // denominator
double fraction = n / d;

while (System.Math.Abs(fraction - value) > EPSILON)
{
if (fraction < value)
{
n++;
}
else
{
d++;
n = (int)System.Math.Round(value * d);
}

fraction = n / (double)d;
}

return new Fraction(n, d);
}
}

斯特恩·布罗科特树(Stern-Brocot Tree)引出了一种相当自然的方法，可以用简单的分母将分数近似为实数。

问题的一部分在于，实际上并不容易将这么多的分数解释为分数。例如。 0.33不是1/3，而是33/100。但是，如果您还记得您的小学培训，那么就有一个将十进制值转换为分数的过程，但是，由于大多数时候十进制数字不是存储在0.33，而是存储在0.329999999999998或类似的数字中，因此不太可能提供所需的内容。

帮自己一个忙，不要打扰，但是如果需要，可以执行以下操作：

将原始值乘以10，直到除去小数部分为止。保留该数字，并将其用作除数。然后通过寻找共同的分母来做一系列的简化。

所以0.4将是4/10。然后，您将寻找以低值(可能是质数)开头的常见除数。从2开始，通过检查除法底数是否与除法本身相同，可以看到2是否将分子和分母均分。

1 2	floor(5/2) = 2 5/2 = 2.5

因此5不能平均分配2。因此，然后检查下一个数字，例如3。执行此操作，直到达到或小于较小数字的平方根为止。

完成之后，您需要

这不是一个"算法"，只是一个Python解决方案：
http://docs.python.org/library/fractions.html

1
2
3

>>> from fractions import Fraction
>>> Fraction('3.1415926535897932').limit_denominator(1000)
Fraction(355, 113)

"假设我们有0.33，我们需要输出" 1/3"。"

您期望"解决方案"具有什么精度？ 0.33不等于1/3。您如何识别"好"(易于阅读)的答案？

无论如何，可能的算法可能是：

如果希望以X / Y的形式找到最接近的分数，其中Y小于10，则可以遍历所有9个可能的Y，为每个Y计算X，然后选择最准确的一个。

R中的内置解决方案：

1
2
3

library(MASS)
fractions(0.666666666)
## [1] 2/3

这使用连续分数法，并具有可选的cycles和max.denominator自变量来调整精度。

在C ++中回答，假设您有一个'BigInt'类，该类可以存储无限制大小的整数。

您可以改用" unsigned long long"，但仅适用于某些值。

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

void GetRational(double val)
{
if (val == val+1) // Inf
throw"Infinite Value";
if (val != val) // NaN
throw"Undefined Value";

bool sign = false;
BigInt enumerator = 0;
BigInt denominator = 1;

if (val < 0)
{
val = -val;
sign = true;
}

while (val > 0)
{
unsigned int intVal = (unsigned int)val;
val -= intVal;
enumerator += intVal;
val *= 2;
enumerator *= 2;
denominator *= 2;
}

BigInt gcd = GCD(enumerator,denominator);
enumerator /= gcd;
denominator /= gcd;

Print(sign?"-":"+");
Print(enumerator);
Print("/");
Print(denominator);

// Or simply return {sign,enumerator,denominator} as you wish
}

顺便说一句，GetRational(0.0)将返回" +0/1"，因此您可能想单独处理这种情况。

P.S .：我在自己的" RationalNum"类中使用此代码已有几年了，并且已经过全面测试。

伊恩·理查兹(Ian Richards)/约翰·肯尼迪(John Kennedy)的这种算法不仅返回了很好的分数，而且在速度方面也表现出色。这是我从此答案中获取的C＃代码。

它可以处理所有double值，但特殊值(如NaN和+/-无穷大)除外，如果需要，您必须添加这些值。

它返回一个new Fraction(numerator, denominator)。用您自己的类型替换。

有关更多示例值以及与其他算法的比较，请转到此处

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

public Fraction RealToFraction(double value, double accuracy)
{
if (accuracy <= 0.0 || accuracy >= 1.0)
{
throw new ArgumentOutOfRangeException("accuracy","Must be > 0 and < 1.");
}

int sign = Math.Sign(value);

if (sign == -1)
{
value = Math.Abs(value);
}

// Accuracy is the maximum relative error; convert to absolute maxError
double maxError = sign == 0 ? accuracy : value * accuracy;

int n = (int) Math.Floor(value);
value -= n;

if (value < maxError)
{
return new Fraction(sign * n, 1);
}

if (1 - maxError < value)
{
return new Fraction(sign * (n + 1), 1);
}

double z = value;
int previousDenominator = 0;
int denominator = 1;
int numerator;

do
{
z = 1.0 / (z - (int) z);
int temp = denominator;
denominator = denominator * (int) z + previousDenominator;
previousDenominator = temp;
numerator = Convert.ToInt32(value * denominator);
}
while (Math.Abs(value - (double) numerator / denominator) > maxError && z != (int) z);

return new Fraction((n * denominator + numerator) * sign, denominator);
}

此算法返回的示例值：

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

Accuracy: 1.0E-3 | Richards
Input | Result Error
======================| =============================
3 | 3/1 0
0.999999 | 1/1 1.0E-6
1.000001 | 1/1 -1.0E-6
0.50 (1/2) | 1/2 0
0.33... (1/3) | 1/3 0
0.67... (2/3) | 2/3 0
0.25 (1/4) | 1/4 0
0.11... (1/9) | 1/9 0
0.09... (1/11) | 1/11 0
0.62... (307/499) | 8/13 2.5E-4
0.14... (33/229) | 16/111 2.7E-4
0.05... (33/683) | 10/207 -1.5E-4
0.18... (100/541) | 17/92 -3.3E-4
0.06... (33/541) | 5/82 -3.7E-4
0.1 | 1/10 0
0.2 | 1/5 0
0.3 | 3/10 0
0.4 | 2/5 0
0.5 | 1/2 0
0.6 | 3/5 0
0.7 | 7/10 0
0.8 | 4/5 0
0.9 | 9/10 0
0.01 | 1/100 0
0.001 | 1/1000 0
0.0001 | 1/10000 0
0.33333333333 | 1/3 1.0E-11
0.333 | 333/1000 0
0.7777 | 7/9 1.0E-4
0.11 | 10/91 -1.0E-3
0.1111 | 1/9 1.0E-4
3.14 | 22/7 9.1E-4
3.14... (pi) | 22/7 4.0E-4
2.72... (e) | 87/32 1.7E-4
0.7454545454545 | 38/51 -4.8E-4
0.01024801004 | 2/195 8.2E-4
0.99011 | 100/101 -1.1E-5
0.26... (5/19) | 5/19 0
0.61... (37/61) | 17/28 9.7E-4
|
Accuracy: 1.0E-4 | Richards
Input | Result Error
======================| =============================
0.62... (307/499) | 299/486 -6.7E-6
0.05... (33/683) | 23/476 6.4E-5
0.06... (33/541) | 33/541 0
1E-05 | 1/99999 1.0E-5
0.7777 | 1109/1426 -1.8E-7
3.14... (pi) | 333/106 -2.6E-5
2.72... (e) | 193/71 1.0E-5
0.61... (37/61) | 37/61 0

您必须确定您愿意接受的错误级别。并非所有的十进制小数都会减少为一个简单的分数。我可能会选择一个易于除数的数字，例如60，并找出最接近该值的60分之几，然后简化分数。

Ruby已经有一个内置的解决方案：

1 2	0.33.rationalize.to_s # =>"33/100" 0.4.rationalize.to_s # =>"2/5"

在Rails中，也可以转换ActiveRecord数值属性：

1 2	product.size = 0.33 product.size.to_r.to_s # =>"33/100"

一种解决方案是首先将所有数字存储为有理数。有用于有理数算术(例如GMP)的库。如果使用OO语言，您也许可以使用有理数类库来替换您的数类。

金融程序等将使用这样的解决方案，以便能够进行精确的计算并保留使用普通浮点数可能会丢失的精度。

当然，它会慢很多，因此对您来说可能不切实际。取决于您需要执行多少计算，以及精度对您的重要性。

1
2
3
4
5
6

a = rational(1);
b = rational(3);
c = a / b;

print (c.asFraction) ---> "1/3"
print (c.asFloat) ---->"0.333333"

我认为最好的方法是首先将浮点值转换为ascii表示形式。在C ++中，可以使用ostringstream，在C中，可以使用sprintf。这是在C ++中的外观：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

ostringstream oss;
float num;
cin >> num;
oss << num;
string numStr = oss.str();
int i = numStr.length(), pow_ten = 0;
while (i > 0) {
if (numStr[i] == '.')
break;
pow_ten++;
i--;
}
for (int j = 1; j < pow_ten; j++) {
num *= 10.0;
}
cout << static_cast<int>(num) <<"/" << pow(10, pow_ten - 1) << endl;

在直线C中可以采用类似的方法。

之后，您需要检查分数是否处于最低水平。此算法将给出精确的答案，即0.33将输出" 33/100"，而不是" 1/3"。但是，0.4表示" 4/10"，当减至最低时为" 2/5"。这可能不像EppStein的解决方案那么强大，但是我相信这更简单。

您可以按照以下步骤以任何一种编程语言来执行此操作：

乘以10除以x，其中x是确保该数字没有小数位所需的10的幂。
示例：将0.33乘以10 ^ 2 = 100，将其乘以33，然后将其除以33/100

通过分解将所得分数的分子和分母减少，直到您不再可以从结果中获取整数。

减少的分数应该是您的答案。

例：
0.2
= 0.2 x 10 ^ 1/10 ^ 1
= 2/10
= 1/5

因此，可以将其解释为" 5分之1"

您将遇到两个基本问题，这将使这一工作变得困难：

1)浮点数不是精确的表示形式，这意味着如果您有一个分数" x / y"，结果为" z"，那么分数算法可能会返回" x / y"以外的结果。

2)无穷多比理性多得多的无理数。有理数是可以表示为分数的数。非理性的人不能。

但是，以一种廉价的方式，由于浮点数具有极限精度，因此您始终可以将其表示为某种派系形式。 (我认为...)

这是使用蛮力方法的javascript快速且肮脏的实现。
根本没有优化，它可以在预定义的分数范围内工作：http://jsfiddle.net/PdL23/1/

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

/* This should convert any decimals to a simplified fraction within the range specified by the two for loops. Haven't done any thorough testing, but it seems to work fine.

I have set the bounds for numerator and denominator to 20, 20... but you can increase this if you want in the two for loops.

Disclaimer: Its not at all optimized. (Feel free to create an improved version.)
*/

decimalToSimplifiedFraction = function(n) {

for(num = 1; num < 20; num++) { //"num" is the potential numerator
for(den = 1; den < 20; den++) { //"den" is the potential denominator
var multiplyByInverse = (n * den ) / num;

var roundingError = Math.round(multiplyByInverse) - multiplyByInverse;

// Checking if we have found the inverse of the number,
if((Math.round(multiplyByInverse) == 1) && (Math.abs(roundingError) < 0.01)) {
return num +"/" + den;
}
}
}
};

//Put in your test number here.
var floatNumber = 2.56;

alert(floatNumber +" =" + decimalToSimplifiedFraction(floatNumber));

这是受JPS使用的方法的启发。

完成上述代码并将其转换为as3

public static function toFrac(f:Number) : String
{
if (f>1)
{
var parte1:int;
var parte2:Number;
var resultado:String;
var loc:int = String(f).indexOf(".");
parte2 = Number(String(f).slice(loc, String(f).length));
parte1 = int(String(f).slice(0,loc));
resultado = toFrac(parte2);
parte1 *= int(resultado.slice(resultado.indexOf("/") + 1, resultado.length)) + int(resultado.slice(0, resultado.indexOf("/")));
resultado = String(parte1) + resultado.slice(resultado.indexOf("/"), resultado.length)
return resultado;
}
if( f < 0.47 )
if( f < 0.25 )
if( f < 0.16 )
if( f < 0.13 )
if( f < 0.11 )
return"1/10";
else
return"1/9";
else
if( f < 0.14 )
return"1/8";
else
return"1/7";
else
if( f < 0.19 )
return"1/6";
else
if( f < 0.22 )
return"1/5";
else
return"2/9";
else
if( f < 0.38 )
if( f < 0.29 )
return"1/4";
else
if( f < 0.31 )
return"2/7";
else
return"1/3";
else
if( f < 0.43 )
if( f < 0.40 )
return"3/8";
else
return"2/5";
else
if( f < 0.44 )
return"3/7";
else
return"4/9";
else
if( f < 0.71 )
if( f < 0.60 )
if( f < 0.56 )
return"1/2";
else
if( f < 0.57 )
return"5/9";
else
return"4/7";
else
if( f < 0.63 )
return"3/5";
else
if( f < 0.66 )
return"5/8";
else
return"2/3";
else
if( f < 0.80 )
if( f < 0.74 )
return"5/7";
else
if(f < 0.78 )
return"3/4";
else
return"7/9";
else
if( f < 0.86 )
if( f < 0.83 )
return"4/5";
else
return"5/6";
else
if( f < 0.88 )
return"6/7";
else
if( f < 0.89 )
return"7/8";
else
if( f < 0.90 )
return"8/9";
else
return"9/10";
}

Let's say we have 0.33, we need to output"1/3". If we have"0.4", we
need to output"2/5".

在通常情况下是错误的，因为1/3 = 0.3333333 = 0.(3)
此外，不可能从上述建议的解决方案中找出十进制可以转换为具有定义精度的分数，因为输出始终是分数。

但是，我基于无限几何级数的概念，特别是基于公式，建议我使用多种功能的综合功能：

enter image description here

最初，此函数尝试查找字符串表示形式中的分数周期。之后，应用上述公式。

有理数代码是从C＃中的Stephen M. McKamey有理数实现中借用的。我希望将我的代码移植到其他语言上不是很困难。

/// <summary>
/// Convert decimal to fraction
/// </summary>
/// <param name="value">decimal value to convert</param>
/// <param name="result">result fraction if conversation is succsess</param>
/// <param name="decimalPlaces">precision of considereation frac part of value</param>
/// <param name="trimZeroes">trim zeroes on the right part of the value or not</param>
/// <param name="minPeriodRepeat">minimum period repeating</param>
/// <param name="digitsForReal">precision for determination value to real if period has not been founded</param>
/// <returns></returns>
public static bool FromDecimal(decimal value, out Rational< T > result,
int decimalPlaces = 28, bool trimZeroes = false, decimal minPeriodRepeat = 2, int digitsForReal = 9)
{
var valueStr = value.ToString("0.0000000000000000000000000000", CultureInfo.InvariantCulture);
var strs = valueStr.Split('.');

long intPart = long.Parse(strs[0]);
string fracPartTrimEnd = strs[1].TrimEnd(new char[] { '0' });
string fracPart;

if (trimZeroes)
{
fracPart = fracPartTrimEnd;
decimalPlaces = Math.Min(decimalPlaces, fracPart.Length);
}
else
fracPart = strs[1];

result = new Rational< T >();
try
{
string periodPart;
bool periodFound = false;

int i;
for (i = 0; i < fracPart.Length; i++)
{
if (fracPart[i] == '0' && i != 0)
continue;

for (int j = i + 1; j < fracPart.Length; j++)
{
periodPart = fracPart.Substring(i, j - i);
periodFound = true;
decimal periodRepeat = 1;
decimal periodStep = 1.0m / periodPart.Length;
var upperBound = Math.Min(fracPart.Length, decimalPlaces);
int k;
for (k = i + periodPart.Length; k < upperBound; k += 1)
{
if (periodPart[(k - i) % periodPart.Length] != fracPart[k])
{
periodFound = false;
break;
}
periodRepeat += periodStep;
}

if (!periodFound && upperBound - k <= periodPart.Length && periodPart[(upperBound - i) % periodPart.Length] > '5')
{
var ind = (k - i) % periodPart.Length;
var regroupedPeriod = (periodPart.Substring(ind) + periodPart.Remove(ind)).Substring(0, upperBound - k);
ulong periodTailPlusOne = ulong.Parse(regroupedPeriod) + 1;
ulong fracTail = ulong.Parse(fracPart.Substring(k, regroupedPeriod.Length));
if (periodTailPlusOne == fracTail)
periodFound = true;
}

if (periodFound && periodRepeat >= minPeriodRepeat)
{
result = FromDecimal(strs[0], fracPart.Substring(0, i), periodPart);
break;
}
else
periodFound = false;
}

if (periodFound)
break;
}

if (!periodFound)
{
if (fracPartTrimEnd.Length >= digitsForReal)
return false;
else
{
result = new Rational< T >(long.Parse(strs[0]), 1, false);
if (fracPartTrimEnd.Length != 0)
result = new Rational< T >(ulong.Parse(fracPartTrimEnd), TenInPower(fracPartTrimEnd.Length));
return true;
}
}

return true;
}
catch
{
return false;
}
}

public static Rational< T > FromDecimal(string intPart, string fracPart, string periodPart)
{
Rational< T > firstFracPart;
if (fracPart != null && fracPart.Length != 0)
{
ulong denominator = TenInPower(fracPart.Length);
firstFracPart = new Rational< T >(ulong.Parse(fracPart), denominator);
}
else
firstFracPart = new Rational< T >(0, 1, false);

Rational< T > secondFracPart;
if (periodPart != null && periodPart.Length != 0)
secondFracPart =
new Rational< T >(ulong.Parse(periodPart), TenInPower(fracPart.Length)) *
new Rational< T >(1, Nines((ulong)periodPart.Length), false);
else
secondFracPart = new Rational< T >(0, 1, false);

var result = firstFracPart + secondFracPart;
if (intPart != null && intPart.Length != 0)
{
long intPartLong = long.Parse(intPart);
result = new Rational< T >(intPartLong, 1, false) + (intPartLong == 0 ? 1 : Math.Sign(intPartLong)) * result;
}

return result;
}

private static ulong TenInPower(int power)
{
ulong result = 1;
for (int l = 0; l < power; l++)
result *= 10;
return result;
}

private static decimal TenInNegPower(int power)
{
decimal result = 1;
for (int l = 0; l > power; l--)
result /= 10.0m;
return result;
}

private static ulong Nines(ulong power)
{
ulong result = 9;
if (power >= 0)
for (ulong l = 0; l < power - 1; l++)
result = result * 10 + 9;
return result;
}

有一些用法的示例：

1
2
3
4
5

Rational<long>.FromDecimal(0.33333333m, out r, 8, false);
// then r == 1 / 3;

Rational<long>.FromDecimal(0.33333333m, out r, 9, false);
// then r == 33333333 / 100000000;

您的案例，右半部分为零修剪：

1
2
3
4
5

Rational<long>.FromDecimal(0.33m, out r, 28, true);
// then r == 1 / 3;

Rational<long>.FromDecimal(0.33m, out r, 28, true);
// then r == 33 / 100;

最小周期演示：

1
2
3
4

Rational<long>.FromDecimal(0.123412m, out r, 28, true, 1.5m));
// then r == 1234 / 9999;
Rational<long>.FromDecimal(0.123412m, out r, 28, true, 1.6m));
// then r == 123412 / 1000000; because of minimu repeating of period is 0.1234123 in this case.

最后四舍五入：

1 2	Rational<long>.FromDecimal(0.8888888888888888888888888889m, out r)); // then r == 8 == 9;

最有趣的情况：

1
2
3
4
5
6
7
8

Rational<long>.FromDecimal(0.12345678m, out r, 28, true, 2, 9);
// then r == 12345678 / 100000000;

Rational<long>.FromDecimal(0.12345678m, out r, 28, true, 2, 8);
// Conversation failed, because of period has not been founded and there are too many digits in fraction part of input value.

Rational<long>.FromDecimal(0.12121212121212121m, out r, 28, true, 2, 9));
// then r == 4 / 33; Despite of too many digits in input value, period has been founded. Thus it's possible to convert value to fraction.

每个人都可以在github上我的MathFunctions库中找到其他测试和代码。

我遇到了一个利用变形的特别优雅的Haskell解决方案。这取决于递归方案包。

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

{-# LANGUAGE AllowAmbiguousTypes #-}
{-# LANGUAGE FlexibleContexts #-}

import Control.Applicative (liftA2)
import Control.Monad (ap)
import Data.Functor.Foldable
import Data.Ratio (Ratio, (%))

isInteger :: (RealFrac a) => a -> Bool
isInteger = ((==) <*>) (realToFrac . floor)

continuedFraction :: (RealFrac a) => a -> [Int]
continuedFraction = liftA2 (:) floor (ana coalgebra)
where coalgebra x
| isInteger x = Nil
| otherwise = Cons (floor alpha) alpha
where alpha = 1 / (x - realToFrac (floor x))

collapseFraction :: (Integral a) => [Int] -> Ratio a
collapseFraction [x] = fromIntegral x % 1
collapseFraction (x:xs) = (fromIntegral x % 1) + 1 / collapseFraction xs

-- | Use the nth convergent to approximate x
approximate :: (RealFrac a, Integral b) => a -> Int -> Ratio b
approximate x n = collapseFraction $ take n (continuedFraction x)

如果您在ghci中进行尝试，它确实可以工作！