5

我编写了这段代码来使用欧几里得算法计算有理数 N 的连分数展开式：

from __future__ import division

def contFract(N):
    while True:
        yield N//1
        f = N - (N//1)
        if f == 0:
            break
        N = 1/f

如果说 N 是 3.245，则函数永远不会结束，因为显然 f 永远不会等于 0。展开的前 10 项是：

[3.0、4.0、12.0、3.0、1.0、247777268231.0、4.0、1.0、2.0、1.0]

这显然是一个错误，因为实际的扩展只是：

[3;4,12,3,1] 或 [3;4,12,4]

是什么导致了这里的问题？是某种舍入误差吗？

4

3 回答 3

4

问题是您正在测试f == 0（整数 0），这对于浮点数几乎是不正确的。所以循环永远持续下去。

相反，检查一些等于 0 的精度（有时可能是错误的）：

>>> from __future__ import division
>>>
>>> def contFract(N):
...     while True:
...         yield N//1
...         f = N - (N//1)
...         if f < 0.0001:  # or whatever precision you consider close enough to 0
...             break
...         N = 1/f
...
>>>
>>> list(contFract(3.245))
[3.0, 4.0, 12.0, 3.0, 1.0]
>>>

如果f可能是负数，请执行-0.0001 < f < 0.0001或abs(f) < 0.0001。这也被认为是不准确的，请参阅链接文章。

并使用我的评论int(N)而不是N//1因为它更清晰 - 它的效率略低：

>>> import timeit
>>> timeit.timeit('N = 2.245; N//1', number=10000000)
1.5497028078715456
>>> timeit.timeit('N = 2.245; int(N)', number=10000000)
1.7633858824068103
于 2016-06-29T11:08:17.977 回答
1

您正在使用float您的操作，不幸的是，有些数字不能表示为二进制表示的数字。

有两种方法可以解决它，首先 - 假设您的数字“足够接近”（甚至引入了新的 Python 3.5.2 math.isclose），或者您正在使用不同的浮点实现，例如Decimal您可以获得正确的结果。

注意这就是为什么对于所有金融系统，没有人使用浮点数，只有 int/bigint 或 Decimals。

 In [21] > N = decimal.Decimal('3.245')

 In [22] > while True:
    print 'N: %s' % (N//1,)
    f = N - N//1
    print 'f: %s' % f
    if f == 0:
        break
    N = 1/f

N: 3
f: 0.245
N: 4
f: 0.081632653061224489795918367
N: 12
f: 0.25000000000000000000000005
N: 3
f: 0.999999999999999999999999200
N: 1
f: 8.00E-25
N: 1250000000000000000000000
f: 0
于 2016-06-29T11:33:31.390 回答
-1

显然，该错误是由于 4.0 除以 1 的整数除法。浮点表示中的 4.0 涉及错误（如果您对浮点表示有所了解）。所以实际上 int(4.0) < 4。这导致 N//1 变为 3.0 并且分数 f 类似于 0.999999 .... 所以这永远不会结束。在每次迭代中打印 N 和 f 并进行尝试。你会意识到。

于 2016-06-29T11:32:04.403 回答