Алгоритмы неформально. Инструкция для начинающих питонистов - [38]
Листинг 5.3. Непрерывная дробь для представления 105/33
Процесс многократного деления двух целых чисел для получения частного и остатка кажется вам знакомым? Так и должно быть. Ведь это тот же процесс, который использовался нами в алгоритме Евклида в главе 2! Мы выполняем те же действия, но сохраняем разные ответы: для алгоритма Евклида последний ненулевой остаток сохранялся как окончательный ответ, а в алгоритме генерирования непрерывных дробей сохраняются все частные (буквы алфавита). Как часто бывает в математике, обнаружилась неожиданная связь — в данном случае между генерированием непрерывной дроби и поиском наибольшего общего делителя.
Ниже описана реализация алгоритма генерирования непрерывной дроби на языке Python.
Допустим, процесс начинается с дроби вида x/y. Сначала мы определяем, какое из чисел x и y больше, а какое меньше:
x = 105
y = 33
big = max(x,y)
small = min(x,y)
Затем мы берем частное от деления большего числа на меньшее, как было сделано с числом 105/33. Когда обнаруживается, что результат равен 3 с остатком 6, мы заключаем, что 3 является первой составляющей (a) в непрерывной дроби. Возьмем частное и сохраним результат следующим образом:
import math
output = []
quotient = math.floor(big/small)
output.append(quotient)
В данном случае мы собираемся получить результат в виде набора букв (a, b, c и т.д.), поэтому создаем пустой список output и присоединяем к нему первый результат.
Наконец, процесс необходимо повторить, как это было сделано для 33/6. Вспомните, что значение 33 ранее хранилось в переменной small, но теперь хранится в big, и остатком процесса деления становится новая переменная small. Так как остаток всегда меньше делителя, big и small всегда будут содержать правильные значения. На языке Python перестановка реализуется так:
new_small = big % small
big = small
small = new_small
В этот момент мы завершили один проход алгоритма, теперь нужно повторить его для следующего набора чисел (33 и 6). Чтобы компактно записать этот процесс, мы поместим его в цикл (листинг 5.4).
Листинг 5.4. Алгоритм выражения дробей в виде непрерывных дробей
import math
def continued_fraction(x,y,length_tolerance):
output = []
big = max(x,y)
small = min(x,y)
while small > 0 and len(output) < length_tolerance:
quotient = math.floor(big/small)
output.append(quotient)
new_small = big % small
big = small
small = new_small
return(output)
Программа получает x и y на входе и определяет переменную length_tolerance. Не забывайте, что одни непрерывные дроби имеют бесконечную длину, а другие просто очень длинные. Включая в функцию переменную length_tolerance , мы можем преждевременно прервать процесс, если вывод становится слишком громоздким, избегая тем самым зацикливания.
Вспомните, что при выполнении алгоритма Евклида использовалось рекурсивное решение. На этот раз вместо рекурсии задействован цикл while. Рекурсия хорошо подходила для алгоритма Евклида, поскольку для него необходимо только одно число — окончательный ответ, а здесь мы хотим собрать последовательность чисел в список. Цикл лучше подходит для подобного последовательного сбора данных. Новая функция continued_fraction вызывается следующим образом:
print(continued_fraction(105,33,10))
Вы получите следующий простой вывод:
[3,5,2]
Как видите, числа совпадают с ключевыми значениями в правой части листинга 5.3.
Возможно, вы захотите проверить, что та или иная непрерывная дробь правильно выражает интересующее вас число. Для этого следует определить функцию get_number(), которая преобразует непрерывную дробь в десятичное число (листинг 5.5).
Листинг 5.5. Преобразование непрерывной дроби в представление числа
def get_number(continued_fraction):
index = -1
number = continued_fraction[index]
while abs(index) < len(continued_fraction):
next = continued_fraction[index - 1]
number = 1/number + next
index -= 1
return(number)
Не обращайте внимания на подробности реализации этой функции, мы просто используем ее для проверки непрерывных дробей. Чтобы удостовериться в том, что функция работает, выполните команду get_number([3,5,2]) и убедитесь в том, что на выходе получен результат 3,181818... — другой способ записи 105/33 (исходное число).
От десятичных дробей к непрерывным
А если вместо некоторого x/y на вход алгоритма непрерывных дробей подается дробное число — например, 1,4142135623730951? Необходимо внести ряд изменений, но в целом можно следовать тому же процессу, которому мы следовали для дробей. Помните, что мы хотели найти a, b, c и остальные буквы в выражении следующего типа:
Найти a проще простого — это просто целая часть числа. Определим first_term (a в нашем уравнении) и leftover следующим образом:
x = 1.4142135623730951
output = []
first_term = int(x)
leftover = x - int(x)
output.append(first_term)
Как и прежде, последовательно вычисляемые результаты сохраняются в списке output.
После определения a имеется остаток, для которого необходимо найти представление в виде непрерывной дроби:
И здесь также можно перейти к обратным дробям:
