我一直在研究欧拉项目问题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
我一直在寻找答案,但找不到答案。如果可以的话,请帮助我调试它,而无需对代码进行太多更改。
分数模块简化了这个问题:
>>> 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)
这是一个不使用分数的版本。 它甚至可以在非常旧的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
这并不能回答你的问题,但维基百科上有一些公式可以让你更有效地计算这个问题。