Project euler Problem 57 (このサイトが大好き!) に取り組んでいます。この問題では、有限連分数と通常の分数の間の変換が必要です。基本的にリストの最後の数字の逆数を取り、それを最後から 2 番目の数字に追加し、最後の分数が残るまで継続するアルゴリズムを考案しました。問題 67 では見事に機能しましたが、今回は 2 回目の反復後に機能しなくなりました (複数の連続した分数に対してアルゴリズムを実行する必要があります)。
これはコードの一部です(外部モジュール、つまり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
私は答えを徹底的に探してきましたが、まったく見つけることができません。可能であれば、コードをあまり変更せずに、これをデバッグするのを手伝ってください。