1

我一直在研究 Project euler Problem 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

我一直在彻底寻找答案，但找不到答案。如果可以的话，请帮助我调试它，而无需过多更改代码。

4

2 回答 2

2

分数模块简化了这个问题：

>>> 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
于 2013-01-24T04:30:17.757 回答
0

这不能回答您的问题，但是Wikipedia上有一些公式可以让您更有效地计算它。

于 2013-01-24T15:27:14.797 回答