Вычисление дроби рекурсией. Python

#python

Дано действительное число x!=0. Вычислить дробь, используя рекурсивную подпрограмму:

def recurs(i,x):
    i*=2
    if i < 256:
        return x*x+i/i**x
    else:
        return x*x+i/x*x
print(recurs(int(input()),int(input()))


Ответ дает, но я не уверен в правильности программы. Может i не с клавиатуры
    

Ответы

Ответ 1

Ещё одна реализация для сравнения результатов:

def fraction(x, maxi=0x100):
    def recur(i):
        return x**2 + (i / recur(i << 1) if i <= maxi else 0)
    return x / recur(2)




Пример:

>>> fraction(3, 4)
0.3256704980842912
>>> fraction(10)  
0.09998001198642725




x: 
maxi:





Для проверки можно независимо найти значение, используя обобщённую цепную дробь:



def fraction(x):
    n = 9  # 2**(9 - 1) == 256
    a = [None] + [x] + [2**(i-1) for i in range(2, n + 1)]
    b = [0] + [x**2] * n

    # @cached()
    def A(n):
        return 1 if n == -1 else b[0] if n == 0 else b[n]*A(n-1) + a[n]*A(n-2)

    # @cached()
    def B(n):
        return 0 if n == -1 else 1 if n == 0 else b[n]*B(n-1) + a[n]*B(n-2)

    return A(n) / B(n)


Пример:

>>> fraction(10)
0.09998001198642727


Для больших значений: fraction(x) ~ 1/x. 



x: 




Чтобы с произвольной заданной точностью посчитать значения, можно decimal.Decimal
в обоих реализациях использовать:

>>> from decimal import Decimal
>>> fraction(Decimal(10))
Decimal('0.09998001198642726105630197652')


fractions.Fraction вычисления позволяет точно проводить в этом случае (return Fraction(A(n),
B(n))):

print(fraction(10))
# -> 1283224212628/12834807549355 


При использовании float, первое решение теряет точность (...725 вместо ...727). Но
проверка с использованием fractions.Fraction подтверждает, что оба способа вычисления
идентичны.


Ответ 2

def f(x, mx, n=2):
    if n == mx:
        return x**2 + n / x**2
    return x**2 + n / f(x, mx, n*2)

def func(x, i=256):
    return x / f(x, i, 2)


Проверка:

In [13]: 3 / ( 9 + 2 / ( 9 + 4/9) )
Out[13]: 0.3256704980842912

In [14]: func(3, 4)
Out[14]: 0.3256704980842912

In [15]: func(10, 256)
Out[15]: 0.09998001198642725