1

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

私は答えを徹底的に探してきましたが、まったく見つけることができません。可能であれば、コードをあまり変更せずに、これをデバッグするのを手伝ってください。

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

これはあなたの質問への回答ではありませんが、ウィキペディアには、これをより効率的に計算できる数式がいくつかあります。

于 2013-01-24T15:27:14.797 に答える