Алгоритмы неформально. Инструкция для начинающих питонистов - [37]
Этот процесс можно продолжать до бесконечности. Результат показан в листинге 5.2.
Листинг 5.2. Непрерывная дробь, выражающая значение φ, продолжающаяся до бесконечности
Теоретически после бесконечной последовательности 1, знаков + и дробных черт, представленной многоточием, можно вставить φ в листинг 5.2 по аналогии с тем, как это сделано в правом нижнем углу листинга 5.1. Но мы никогда не доберемся до конца последовательности единиц (поскольку она продолжается до бесконечности), поэтому о значении φ, вложенном в правой части, можно полностью забыть.
Подробнее о непрерывных дробях
Только что приведенные выражения называются непрерывными дробями. Такая дробь состоит из сумм и дробей, вложенных на многих уровнях. Непрерывные дроби могут быть как конечными, как дробь из листинга 5.1, завершавшаяся после семи уровней, так и бесконечными, как в листинге 5.2. Непрерывные дроби особенно полезны для наших целей, поскольку позволяют выразить точное значение φ, не вырубая целые леса для производства достаточного количества бумаги. Математики иногда используют специальную, более компактную запись для выражения непрерывной дроби в одной пустой строке. Вместо того чтобы записывать все дробные черты в непрерывной дроби, можно воспользоваться квадратными скобками ([]) для обозначения того, что мы работаем с непрерывной дробью, и отделить двоеточием «отдельную» цифру от цифр, стоящих вместе в дроби. Такой записью можно записать непрерывную дробь для φ в следующем виде:
phi = [1; 1,1,1,1 . . .]
В этом случае многоточие уже не приводит к потере информации, так как в непрерывной дроби для φ проявляется явная закономерность: она состоит только из 1, поэтому мы точно знаем ее 100-й или 1000-й элемент. Это один из тех случаев, когда математика предоставляет возможность, которая на первый взгляд кажется волшебной: способ компактной записи числа, которое в нашем представлении является бесконечным и не имеет закономерностей, без словесного описания. Однако φ — не единственная непрерывная дробь. Возможен и другой вариант записи непрерывной дроби:
mysterynumber = [2; 1,2,1,1,4,1,1,6,1,1,8, . . .]
В данном случае после нескольких первых цифр обнаруживается простая закономерность: пары единиц, чередующиеся с возрастающими четными числами. Следующими значениями будут 1, 1, 10, 1, 1, 12 и т.д. Начало этой непрерывной дроби можно записать в более традиционном стиле:
На самом деле это загадочное число есть не что иное, как наш старый знакомый — число e, основание натуральных логарифмов! Константа e, как и φ, и другие иррациональные числа, имеет бесконечное разложение без очевидной закономерности и не может быть представлена конечной дробью. Похоже, точно выразить ее числовое значение невозможно. Но используя новую концепцию непрерывных дробей и новую компактную запись, мы можем записать эти вроде бы непреодолимые числа в одну строку.
Кроме того, существуют несколько интересных способов использования непрерывных дробей для представления числа π. И это можно назвать победой для сжатия данных, а также победой в бесконечной борьбе между порядком и хаосом: если прежде нам казалось, что интересными для нас числами правит только всепроникающий хаос, то сейчас выясняется, что где-то внизу всегда существовал скрытый порядок.
Наша непрерывная дробь для φ происходит из специального уравнения, которое работает только для φ. Но в действительности для любого числа возможно сгенерировать представление в виде непрерывной дроби.
Алгоритм генерирования непрерывных дробей
Ниже описан алгоритм, который строит разложение произвольного числа в непрерывную дробь.
Проще всего найти разложение в непрерывную дробь для чисел, которые уже являются простыми дробями. Для примера рассмотрим задачу нахождения представления 105/33 в виде непрерывной дроби. Наша цель — выразить это число в следующей форме:
где многоточием может стать конечная серия (а не бесконечная). Наш алгоритм сначала сгенерирует a, потом b, потом c и т.д., пока не будет достигнуто последнее слагаемое или пока не будет выполнено условие остановки.
Если интерпретировать пример 105/33 как задачу на деление, а не как дробь, то выясняется, что результат 105/33 равен 3 с остатком 6. Перепишем 105/33 в форме 3 + 6/33:
Левая и правая части этого уравнения состоят из целого числа (3 и a) и дроби (6/33 и остаток правой части). Заключаем, что целые части равны, Так что a = 3. После этого необходимо найти подходящие b, c и т.д., чтобы вся дробная часть выражения давала результат 6/33.
Чтобы найти b, c и т.д., посмотрим, какую задачу предстоит решить после вывода о том, что a = 3:
Если перейти к обратной дроби в обеих частях этого выражения, то получается следующее уравнение:
Требуется определить b и c. Деление можно повторить; 33/6 = 5 с остатком 3, поэтому 33/6 записывается в виде 5 + 3/6:
Мы видим, что в обеих частях уравнения присутствуют целое число (5 и b) и дробь (3/6 и остаток правой части). Можно заключить, что целые части равны, так что b = 5. Мы определили еще одну букву, и теперь для дальнейшего продвижения необходимо упростить 3/6. Если вы не можете немедленно сказать, что 3/6 — это 1/2, то можно повторить тот же процесс, что и для 6/33: 3/6 выражается в виде обратной дроби 1/(6/3), и мы видим, что результат 6/3 равен 2 с остатком 0. Алгоритм, по которому мы действуем, должен завершиться при достижении нулевого остатка, поэтому можно сделать вывод, что процесс завершен, и вся непрерывная дробь записывается так, как показано в листинге 5.3.
