Алгоритмы неформально. Инструкция для начинающих питонистов - [39]
Следующий результат b будет целой частью нового числа — в данном случае 2. После этого процесс повторяется: переход к обратной дроби для дробной части, определение целой части и т.д.
На языке Python каждая итерация может быть записана следующим образом:
next_term = math.floor(1/leftover)
leftover = 1/leftover - next_term
output.append(next_term)
Весь процесс объединяется в одну функцию, приведенную в листинге 5.6.
Листинг 5.6. Вычисление непрерывных дробей для дробных чисел
def continued_fraction_decimal(x,error_tolerance,length_tolerance):
output = []
first_term = int(x)
leftover = x - int(x)
output.append(first_term)
error = leftover
while error > error_tolerance and len(output) next_term = math.floor(1/leftover) leftover = 1/leftover - next_term output.append(next_term) error = abs(get_number(output) - x) return(output) Как и в предыдущем случае, в программу включается порог length_tolerance. Добавляется и переменная error_tolerance, которая позволяет выйти из алгоритма, если приближение «достаточно близко» к точному ответу. Чтобы узнать, подошли ли мы достаточно близко к решению, мы вычисляем разность между x (аппроксимируемым числом) и значением непрерывной дроби, вычисленной на текущий момент. Для получения этого значения можно воспользоваться той же функцией get_number() из листинга 5.5. Опробовать новую функцию достаточно просто: print(continued_fraction_decimal(1.4142135623730951,0.00001,100)) Вы получите следующий результат: [1, 2, 2, 2, 2, 2, 2, 2] Эту непрерывную дробь можно записать следующим образом (с использованием знака приближенного равенства, поскольку непрерывная дробь является аппроксимацией в пределах крошечной погрешности, а у нас нет времени для вычисления каждого элемента бесконечной последовательности):
Обратите внимание: вся диагональ дробей справа заполнена двойками. Мы нашли первые семь результатов для бесконечной непрерывной дроби, бесконечное разложение которой состоит только из двоек. Разложение непрерывной дроби может быть записано в виде [1,2,2,2,2...]. Это разложение в непрерывную дробь √2 — другого иррационального числа, которое не может быть представлено в виде простой дроби, а в цифрах его дробной части нет закономерностей. Тем не менее это число имеет легко запоминающееся представление в виде непрерывной дроби.
От дробей к корням
Если вас интересуют непрерывные дроби, то я бы рекомендовал почитать о математике, которого звали Сриниваса Рамануджан, — за свою короткую жизнь он мысленно путешествовал к пределам, ведущим в бесконечность, и вернулся оттуда с сокровищами, которыми поделился с нами. Помимо непрерывных дробей, Рамануджан интересовался непрерывными квадратными корнями (также называемыми вложенными) — приведу примеры трех квадратных корней с бесконечной вложенностью:
Оказывается, x = 2 (давно известный анонимный результат), y = 3 (доказано Рамануджаном), а z — не что иное, как φ, золотое сечение! Попробуйте придумать способ генерирования представлений вложенных корней на Python. Квадратные корни, безусловно, интересны в бесконечных формулах, но, как выясняется, интересны и сами по себе!
Квадратные корни
Мы считаем калькуляторы чем-то обыденным и привычным, но если подумать, что делают эти устройства, то они весьма впечатляют. Наверное, вы помните из уроков геометрии, что синус определяется через длины сторон прямоугольных треугольников — как отношение длины противолежащего катета к длине гипотенузы. Но если это определение синуса, то как на калькуляторе может быть кнопка Sin, которая мгновенно выполняет это вычисление? Может, калькулятор где-то внутри рисует прямоугольный треугольник, достает линейку, измеряет длины сторон и делит их? Аналогичный вопрос можно задать и о квадратных корнях: квадратный корень является операцией, обратной по отношению к возведению в квадрат, и не существует никакой прямолинейной аналитической формулы, которую мог бы использовать калькулятор. Наверное, вы уже догадались: существует алгоритм для быстрого вычисления квадратных корней.
Вавилонский алгоритм
Предположим, вы хотите найти квадратный корень числа x. Как и в любой математической задаче, можно воспользоваться стратегией предположений и проверки. Допустим, вы предполагаете, что квадратный корень из x равен y. Далее вы вычисляете y2, и если результат равен x, то задача решена (редкий случай одношагового «алгоритма удачной догадки»).
Если гипотеза y отличается от квадратного корня x, то нужно представить следующую догадку, и следующее предположение должно привести нас ближе к истинному значению квадратного корня x. Вавилонский алгоритм позволяет последовательно улучшать предположения с постепенным схождением к правильному ответу. Это простой алгоритм, для которого не требуется ничего, кроме деления и вычисления среднего.
1. Предположить, что квадратный корень из x равен y.
2. Вычислить z = x / y.
3. Вычислить среднее для z и y. Среднее становится новой оценкой y, то есть новым предположением для квадратного корня из x.
4. Повторять шаги 2 и 3, пока разность
