Продолжение от дроби к дроби неисправности

Question

Я работаю над 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

Я тщательно искал ответ и не могу его найти. Помоги мне отладить это, если сможешь, не сильно меняя код.

Answer 1

Модуль фракций быстро решает эту проблему:

>>> 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

Answer 2

Это не отвечает на ваш вопрос, но в Википедии есть некоторые формулы, которые могут позволить вам вычислить это более эффективно.