Алгоритмы неформально. Инструкция для начинающих питонистов - [36]
Резюме
Задачи сортировки и поиска могут показаться чем-то обыденным, словно вас оторвали от кругосветного круиза для посещения семинара по методике складывания отглаженного белья. Возможно, это так, но помните, что если вы умеете эффективно складывать белье, то сможете упаковать больше снаряжения для подъема на Килиманджаро. Алгоритмы сортировки и поиска — ваши подручные, которые помогают открывать более новые и интересные возможности. Кроме того, эти алгоритмы заслуживают вашего внимания из-за своей фундаментальной роли и популярности и еще пригодятся на протяжении вашей жизни. В этой главе мы рассмотрели некоторые фундаментальные и интересные алгоритмы сортировки, а также метод бинарного поиска. Помимо этого, мы изучили способы сравнения алгоритмов и нотацию «О большое».
В следующей главе мы обратимся к нескольким способам применения алгоритмов из области чистой математики. Вы научитесь использовать алгоритмы для исследования мира математики и узнаете, как мир математики помогает нам разобраться в нашем собственном мире.
5. Чистая математика
Благодаря своему формальному характеру алгоритмы естественно подходят для применений в области математики. В этой главе мы исследуем некоторые алгоритмы, применяемые в области чистой математики, и посмотрим, как математические идеи помогают улучшать наши алгоритмы. Начнем с обсуждения непрерывных дробей — несложной, на первый взгляд, темы, которая поможет найти порядок в хаосе. Мы рассмотрим квадратные корни — тему более прозаическую, но, возможно, более практичную. Наконец мы перейдем к обсуждению случайности, включая математическое обоснование случайности и некоторые важные алгоритмы для генерирования случайных чисел.
Непрерывные дроби
В 1597 году великий ученый Иоганн Кеплер написал, что он считает двумя «великими сокровищами» геометрии теорему Пифагора и число, которое с тех пор получило название «золотое сечение». Оно часто обозначается греческой буквой φ и равно приблизительно 1,618, и Кеплер был лишь одним из десятков великих мыслителей, которых оно приводило в восторг. Число φ, как и π с другими знаменитыми константами (такими как основание натуральных логарифмов e), нередко появляется в совершенно неожиданных местах. Ученые нередко сталкивались с золотым сечением, обозначаемым числом φ, в природе и скрупулезно документировали его проявления в искусстве — например, в снабженной аннотациями версии «Венеры с зеркалом» Диего Веласкеса, показанной на рис. 5.1.
На рис. 5.1 энтузиаст добавил разметку, которая показывает, что соотношения некоторых длин (таких как b/a и d/c) равны φ. Подобные проявления золотого сечения встречаются во многих шедеврах живописи.
Рис. 5.1. Золотое сечение на картине «Венера с зеркалом» (https://commons.wikimedia.org/wiki/File:DV_The_Toilet_of_Venus_Gr.jpg)
Компактное представление числа 
Точное значение числа φ на удивление трудно представить. Можно сказать, что оно равно приблизительно 1,61803399... Многоточие можно считать своего рода обманом; оно означает, что далее идут другие цифры (на самом деле бесконечное количество цифр), но я не привожу их, так что вы не знаете точное значение φ.
Для некоторых чисел с бесконечными дробными разложениями возможно точное представление. Например, число 0,11111... равно 1/9 — здесь дробь предоставляет простой способ выражения точного значения дроби, продолжающейся до бесконечности. Даже если точное представление неизвестно, вы можете заметить закономерность с повторяющимися единицами в 0,1111…, а следовательно, понять точное значение. К сожалению, «золотое сечение» относится к так называемым иррациональным числам; это означает, что не существует двух целых чисел x и y, для которых φ равно x/y. Более того, никто еще не смог выявить какую-либо закономерность в его последовательности цифр.
Итак, имеется бесконечное десятичное разложение без очевидных закономерностей, которое не имеет дробного представления. Может показаться, что четкое выражение точного значения φ невозможно. Но когда вы больше узнаете об этом числе, появляется возможность четкого и компактного его выражения. Одна из особенностей φ, о которых необходимо знать, — это число является решением следующего уравнения:
φ2 – φ – 1 = 0
Казалось бы, точное значение числа можно было бы выразить как решение уравнения, записанного над этим абзацем. Конечно, такая формулировка компактна и технически точна, но означает, что уравнение придется как-то решить. Кроме того, описание ничего не сообщает о том, какой будет 200-я или 500-я цифра в разложении φ.
Разделив обе части уравнения на φ, получаем следующий результат:
После перестановки получаем:
А теперь представим странную подстановку этого уравнения внутри самого себя:
Здесь φ в правой стороне переписывается в виде 1 + 1/φ. Ту же подстановку можно выполнить снова; почему нет?
Подстановку можно выполнять сколько угодно раз без каких-либо ограничений. При этом φ все дальше продвигается на более низкие уровни, в угол растущей дроби. В листинге 5.1 приведено выражение φ с семью уровнями.
Листинг 5.1. Непрерывная дробь с семью уровнями, выражающая значение φ
