Алгоритмы неформально. Инструкция для начинающих питонистов - [9]

В книге мы исследуем много разных алгоритмов. Одни сор­тируют списки или обрабатывают числа. Другие делают возможной обработку естественного языка и искусственный интеллект. Учтите, что алгоритмы не растут на деревьях. Каждый алгоритм до того, как пошел в массы и был представлен для широкого обозрения в этой книге, был кем-то изобретен или найден — как это произошло с Чепменом, который проснулся в мире, где его алгоритм не существовал, а в конце дня лег спать в изменившемся мире. Я постараюсь сделать так, чтобы вы попытались поставить себя на место этих героических изобретателей. Иначе говоря, я рекомендую рассматривать алгоритмы не только как инструменты, но и как трудноразрешимую проблему, которая была успешно решена. Полная карта мира алгоритмов еще не построена — остается еще немало неизученных областей, и я искренне надеюсь, что вы можете стать одним из участников процесса их изучения.

Резюме

В этой главе были представлены два подхода к решению задач: аналитический и алгоритмический. Рассматривая два способа решения задачи аутфилдера, мы исследовали различия этих подходов и в конечном итоге пришли к алгоритму Чепмена. Ученый нашел простую закономерность в сложной ситуации (постоянное ускорение тангенса θ) и использовал ее для разработки концепции итеративного процесса, который получает только один простой ввод (поворот головы за мячом) и приводит к определенной цели (пойманный мяч). Если вы хотите разрабатывать и использовать алгоритмы в своей работе, то можете попытаться встать на путь Чепмена.

В следующей главе мы рассмотрим некоторые примеры алгоритмов в истории. Эти примеры должны углубить ваше понимание алгоритмов; в частности, вы узнаете, что они собой представляют и как работают. Речь пойдет об алгоритмах из истории Древнего Египта, Древней Греции и императорской Японии. Каждый новый изучаемый вами алгоритм можно добавить в арсенал алгоритмов, которыми вы сможете пользоваться в своей работе, пока со временем не дойдете до точки, когда сможете разрабатывать и совершенствовать собственные алгоритмы.

1 Аутфилдер — общий термин, которым в бейсболе обозначается один из трех игроков, занимающих оборонительную позицию на внешнем поле. — Примеч. пер.

2. Алгоритмы в истории

Алгоритмы часто ассоциируются с компьютерами. И в этом есть резон; компьютерные операционные системы могут использовать множество алгоритмов высокой сложности, и программирование хорошо подходит для точной реализации всех видов алгоритмов. Однако алгоритмы имеют более фундаментальную природу, чем компьютерная архитектура, на которой они реализуются. Как упоминалось в главе 1, слово «алгоритм» появилось более тысячи лет назад, однако алгоритмы описывались в древних рукописях еще задолго до этого. Даже вне памятников письменности существуют многочисленные данные, свидетельствующие о применении сложных алгоритмов в Древнем мире — например, технологии строительства.

В этой главе представлены несколько алгоритмов древнего происхождения. В них проявляется выдающаяся изобретательность и оригинальность мышления, особенно если учесть, что они создавались и проверялись без помощи компьютеров. Начнем с обсуждения русского крестьянского умножения — метода арифметических вычислений, который, несмотря на свое название, может происходить из Египта и не иметь никакого отношения к крестьянам. Затем рассмотрим алгоритм Евклида — важный «классический» алгоритм для нахождения наибольшего общего делителя. Напоследок рассмотрим изобретенный в Японии алгоритм для построения волшебных квадратов.

Русское крестьянское умножение

Изучение таблицы умножения многим запомнилось как особенно трудный этап образования. Дети спрашивают своих родителей, почему так важно учить таблицу умножения, и родители обычно отвечают, что без этого нельзя умножать. Как же они ошибаются! Существует русское крестьянское умножение (Russian Peasant Multiplication, RPM) — метод, позволяющий перемножать большие числа, обходясь без знания большей части таблицы умножения.

Происхождение RPM остается неясным. Древнеегипетский свиток, называемый папирусом Ринда, содержит разновидность этого алгоритма. Некоторые историки предложили гипотезы (большей частью неубедительные) о том, как метод мог перей­ти от древнеегипетских ученых к крестьянам необъятной российской глубинки. Как бы то ни было, алгоритм RPM весьма интересен.

RPM вручную

Представьте, что хотите умножить 89 на 18. RPM работает так: сначала нарисуйте два расположенных рядом друг с другом столбца. Первый называется столбцом деления, сначала в нем находится число 89. Второй называется столбцом умножения, и в исходном состоянии в нем находится число 18 (табл. 2.1).

Таблица 2.1. Таблица деления/умножения, часть 1

Столбец деления

Столбец умножения

89

18

Начнем с заполнения столбца деления. Для каждой его строки берем предыдущее значение и делим его на 2, остаток при этом игнорируется. Например, при делении 89 на 2 мы получаем 44 с остатком 1, поэтому во второй строке столбца деления записывается число 44 (табл. 2.2).

Таблица 2.2. Таблица деления/умножения, часть 2