Дано действительное число 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 не с клавиатуры
Ещё одна реализация для сравнения результатов:
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
<script type="text/javascript" src="https://cdn.rawgit.com/brython-dev/brython/3.4.0/www/src/brython.js"></script><body onload="brython()"><script type="text/python">
def fraction(x, maxi=0x100):
def recur(i):
return x**2 + (i / recur(i << 1) if i <= maxi else 0)
return x / recur(2)
try your own input
from browser import document, html
@document["mybutton"].bind("click")
def on_click(event):
x = int(document['x'].value)
maxi = int(document['maxi'].value)
document <= html.P(f'fraction({x}, {maxi}) == {fraction(x, maxi)}')
</script><div><label for="x">x: <input id="x" value="10"></div><div><label for="maxi">maxi: <input id="maxi" value="256"></div><button id="mybutton">fraction(x, maxi)</button></body>
Для проверки можно независимо найти значение, используя обобщённую цепную дробь:
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.
<script type="text/javascript" src="https://cdn.rawgit.com/brython-dev/brython/3.4.0/www/src/brython.js"></script><body onload="brython()"><script type="text/python">
def fraction(x):
# https://en.wikipedia.org/wiki/Generalized_continued_fraction
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)
try your own input
from browser import document, html
@document["mybutton"].bind("click")
def on_click(event):
x = int(document['x'].value)
document <= html.P(f'fraction({x}) == {fraction(x)}')
</script><div><label for="x">x: <input id="x" value="10000000000"></div><button id="mybutton">fraction(x)</button></body>
Чтобы с произвольной заданной точностью посчитать значения, можно 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 подтверждает, что оба способа вычисления идентичны.
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
