python - 贪婪算法的奇怪行为

我已经实现了贪婪算法来求解埃及分数，但是我得到了一些意想不到的结果这是我的密码

from math import ceil
from fractions import Fraction

def go(frac):
    ret = []
    while frac > 0:
        if frac.numerator == 1:
            ret.append(frac)
            break
        x = Fraction(1, ceil(frac.denominator / frac.numerator))
        frac -= x
        ret.append(x)
    return ret

input1 = int(raw_input('numerator: '))
input2 = int(raw_input('denominator: '))

print go(Fraction(input1, input2))

我经常得到错误“typeerror：两个参数都应该是rational实例”
我一直在记录，它在while循环的第一次迭代时崩溃。
编辑：详细错误为：

File "egypt.py", line 19, in <module>
print go(Fraction(input1, input2))
File "egypt.py", line 10, in go
x = Fraction(1,ceil(frac.denominator / frac.numerator))
File "/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/fractions.py", line 158, in __new__
raise TypeError("both arguments should be "
TypeError: both arguments should be Rational instances

这是为什么？
谢谢您。

最佳答案

尝试更改此：

x = Fraction(1, ceil(frac.denominator / frac.numerator))

对此：

x = Fraction(1,int(ceil(frac.denominator / float(frac.numerator))))

关于python - 贪婪算法的奇怪行为，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19117543/