连分数转分数故障

Question

我一直在做Project Euler的第57题（我很喜欢这个网站！）。这个问题需要把一个有限的连分数转换成普通的分数。我想出了一个算法，基本上是把列表中最后一个数字的倒数加到倒数第二个数字上，然后继续这个过程，直到得到最后的分数。对于第67题，这个方法效果很好，但这次在第二次迭代后就不再有效了（我需要对多个连分数进行这个算法）。

这是我写的代码片段（我用了一个外部模块，叫做sympy）：

import time
from sympy import *
from sympy import fraction, Rational, Symbol

def cont_fract_to_fraction(cont_frac_list):
    a=cont_frac_list[-1]
    b=cont_frac_list[-2]
    new_reduced=Rational(b,1)+ Rational(1,a)
    cont_frac_list[-2]=new_reduced
    del cont_frac_list[-1]
    if len(cont_frac_list)==1:
        print cont_frac_list #To check
        return cont_frac_list
    else:
        cont_fract_to_fraction(cont_frac_list)

def numerator_higher_denominator(fraction):
    num=str(fraction[0])
    den=str(fraction[1])
    if len(num)>len(den):
        return 1
    else:
        return 0

start=time.time()

tally=0

for k in xrange (1, 101):
    sqrt_eval=[1]
    for x in xrange (1, k+2):
        sqrt_eval.append(2)
    sqrt_eval=cont_fract_to_fraction(sqrt_eval)
    print sqrt_eval ##To double check
    #fraction_result=fraction(soln[0]) To introduce later
    #tally+=numerator_higher_denominator(fraction_result) To introduce later

elapsed=time.time()-start

print "Solution: ", tally, "Solved in: ", elapsed

我基本上是想测试一下，看看能否得到所有的最终分数，函数返回之前的打印结果给出了答案，但在我把值赋给sqrt_eval后，打印的结果却是None。这里是一次测试运行的结果：

###Test run####
[3/2] #--> function print
[3/2] #--> sqrt_eval print
[7/5]
None
[17/12]
None
[41/29]
None
[99/70]
None
[239/169]
None
[577/408]
None
[1393/985]
None
[3363/2378]
None
[8119/5741]
None
[19601/13860]
None

我已经仔细寻找答案，但还是找不到。如果可以的话，帮我调试一下这个问题，不要大幅修改代码。

Answer 1

这虽然没有直接回答你的问题，但在维基百科上有一些公式，可能会帮助你更高效地计算这个。

Answer 2

fractions模块可以很简单地解决这个问题：

>>> from fractions import Fraction
>>> def normal_fraction(continued_fraction):
         n = Fraction(0)
         for d in continued_fraction[:0:-1]:
             n = 1 / (d + n)
         return continued_fraction[0] + n

>>> cf = [3,7,15,1,292,1,1,1,2,1,3,1]
>>> normal_fraction(cf)
Fraction(5419351, 1725033)
>>> float(_)
3.1415926535898153

如果你喜欢函数式编程和简洁的代码，上面的逻辑可以用一行代码来实现，使用reduce()：

>>> cf[0] + reduce(lambda d, n: 1 / (d + n), cf[:0:-1], Fraction(0))
Fraction(5419351, 1725033)

这里有一个不使用Fraction的版本。它甚至可以在很旧的Python版本上运行：

def normal_fraction(continued_fraction):
    n, d = 0, 1
    for a in continued_fraction[:0:-1]:
        n, d = d, a*d + n
    return continued_fraction[0]*d + n, d