Мне предстоит доделать сортировку, когда постдоки выполнят задание. Нужно превратить две упорядоченные стопки в одну. Насколько это будет трудно? Допустим, у меня есть две стопки тетрадей в алфавитном порядке. Я смотрю на верхние тетради в той и другой стопке, выбираю первую по алфавиту и кладу в итоговую стопку. Диаграмма иллюстрирует процесс.
Когда одна из стопок иссякает, я просто-напросто кладу оставшуюся в конец итоговой стопки. В худшем случае придется проделать 99 операций. Это потребует всего несколько минут!
Но как насчет моих постдоков? У каждого стопка с 50 тетрадями. Постдоки – люди смышленые, поэтому не станут сортировать тетради самостоятельно. Они, в свою очередь, поделят свои стопки пополам (таким образом, в каждой окажется по 25 тетрадей) и передоверят сортировку аспирантам! Когда те закончат, постдокам останется соединить две отсортированные стопки по 25 тетрадей в одну общую по 50. Это потребует максимум 49 операций.
Но четыре аспиранта тоже не дураки. Они делят свои стопки на две части (в одной 12, в другой 13 тетрадей) и находят восемь старшекурсников, чтобы передоверить работу. В результате каждому аспиранту остается соединить две маленькие стопки и отдать их постдокам.
Как старшекурсники сортируют тетради? Несложно догадаться: они делят свои стопки на две части (в одной 6 тетрадей, в другой 7), ловят 16 третьекурсников и отдают им эти стопки. Те находят 32 второкурсника и отдают им раздербаненные стопки (в одних по 3, в других по 4 тетради). Наконец, второкурсники отлавливают 64 первокурсника и отдают им стопки по 1 и по 2 тетради. Первокурсникам делать нечего: они быстро сортируют свою часть и отдают обратно.
Очевидно, эта «схема Понци[130]» экономит мое время, но насколько она эффективна в целом? Посмотрим, как много операций она потребует в худшем случае. Занесем все данные в таблицу:
Максимальное количество операций оказывается существенно меньше, чем при сортировке пузырьковым методом.
К несчастью, в этой схеме есть изъян: у меня сейчас нет постдоков! Так что вместо вербовки целой армии помощников придется работать самому.
Для начала я найду большой незагроможденный стол. Я поделю стопку из 100 тетрадей пополам и положу две стопки по краям стола. Как я их отсортирую? По тому же алгоритму! Поделю две стопки по 50 тетрадей на четыре по 25, а их буду сортировать тем же методом. В худшем случае понадобится 645 операций. Правда, на сей раз мне придется действовать в одиночку. Однако это лучше, чем почти что 10 000 операций при сортировке пузырьковым методом.
Словарное определение не должно включать определяемого слова. Вообразите, что вы ищете в словаре слово оскудение и находите такое определение:
Оскудение: результат оскудения[131].
Что за чушь! Однако наш алгоритм сортировки и слияния грешит именно этой ссылкой на самого себя. Вот более точное определение.
На входе: объекты a1, a2, a3, …, an.
На выходе: те же объекты в отсортированном виде.
1. Если n = 1, сортировка закончена. Пускаем данные на выход. В противном случае переходим к пункту 2.
2. Поделить множество объектов на равные подмножества, если их количество четно, или на подмножества, отличающиеся на единицу, если количество нечетно. Использовать алгоритм сортировки и слияния.
3. Соединить подмножества[132] и пустить результат на выход.
Алгоритм, ссылающийся сам на себя, называют рекурсивным. В отличие от неудачного определения слова оскудение, наш алгоритм работает, потому что рано или поздно дойдет до конечной точки. Когда-нибудь множество объектов сведется к одному, и больше не придется проделывать процедуру заново. Поэтому нет опасности уйти в «бесконечный цикл».
Каково наибольшее среди чисел, на которые нацело делятся одновременно 986 и 748? Простейший способ ответить на вопрос – перепробовать все варианты. Разумеется, 986 и 748 делятся на 1. Несложно видеть, что на 2 они тоже делятся. Но ни то ни другое число не делится на 3. Одно из них, 748, делится на 4, а другое нет. Нам «всего-навсего» нужно перебрать все делители и сравнить их. Мы остановимся после 748, потому что дальше числа не могут быть делителями 748. Наконец мы выясним, что у 748 и 986 четыре общих делителя: 1, 2, 17 и 34. Наибольший общий делитель 748 и 986 равен 34. Для любых положительных целых чисел a и b запись НОД (a, b) означает их наибольший общий делитель[133].
Описанный выше метод дает незамысловатый и неоспоримый алгоритм поиска наибольшего общего делителя. Его слабая сторона – неэффективность. Для поиска НОД двух трехзначных чисел придется перебрать сотни вариантов. Может быть, есть что-нибудь попроще?
Присмотримся к числам 986 и 748 повнимательней. Мы ищем наибольший общий делитель, поэтому естественно разложить оба числа на простые множители[134] (см. главу 1). Вот результат:
986 = 2 × 17 × 29;
748 = 2 × 2 × 11 × 17.
С помощью этого разложения на простые множители мы можем найти НОД, пуская в дело все простые числа, на которые делятся оба наших числа. Оба делятся на 2 и на 17, потому наибольший общий делитель очевидным образом равен 2 × 17 = 34.
Как разложить число на простые множители самым эффективным способом? Ответ неутешителен: мы этого не знаем (как уже отмечалось в главе 1). Нам нужна идея получше.
Еще одну идею нам подсказал Евклид. Допустим, d – общий делитель 986 и 748. Это означает, что
986 = xd, 748 = yd,
где x и y – целые числа. Следовательно, d также является делителем разности 986 – 748. Это следует из нехитрых алгебраических выкладок:
986 – 748 = xd – yd = (x – y) d.
Так как x и y целые числа, их разность тоже целое число. Потому разность 986 и 748 тоже нацело делится на d. Заметим, что 986–748 = 238.
Точно так же общий делитель 748 и 238 является делителем 986. Почему? Если e – общий делитель 748 и 238, то
748 = ue, 238 = ve,
где u и v – целые числа. Таким образом,
986 = 748 + 238 = ue + ve = (u + v) e,
откуда мы делаем заключение, что e – делитель 986.
Вывод: общие делители 986 и 748 являются также общими делителями 748 и 238. Для иллюстрации запишем делители всех трех чисел, подчеркивая общие делители:
делители 986 → 1, 2, 17, 29, 34, 58, 493, 986;
делители 748 → 1, 2, 4, 11, 17, 22, 34, 44, 68, 187, 374, 748;
делители 238 → 1, 2, 7, 14, 17, 34, 119, 238.
Отсюда следует, что
НОД (986, 748) = НОД (748, 238). (A)
Таким образом, поиск наибольшего общего делителя 986 и 748 свелся к поиску наибольшего общего делителя 748 и 238. Прогресс, теперь мы имеем дело с числами поменьше. Проделаем то же самое еще раз.
Если некое d – общий делитель 238 и 748, оно также делитель их разности. Этим дело не ограничивается. Мы можем вычесть 238 из 748 несколько раз, и d будет оставаться делителем разностей. Точнее говоря, если 238 и 748 делятся на d, разность 748 – 3 × 238 тоже делится на d. Обратимся к алгебре, чтобы доказать это.
748 = xd, 238 = yd,
где x и y – целые числа. Следовательно,
748 – 3 × 238 = xd – 3yd = (x – 3y) d.
Таким образом, d – делитель 748 – 3 × 238 = 34. И наоборот: если e – делитель 34 и 238, это также делитель 748. Вернемся к алгебре.
238 = ue, 34 = ve,
где u и v – целые числа. Таким образом,
748 = 3 × 238 + 34 = 3ue + ve = (3u + v) e.
Таким образом, e – делитель 748. Следовательно, у 748, 238 и 34 есть общие делители, и мы можем сделать вывод, что
НОД (748, 238) = НОД (238, 34). (B)
На основе тождеств (A) и (B) мы имеем:
НОД (986, 748) = НОД (748, 238) = НОД (238, 34).
Мы почти у цели. Обратим внимание, что 238 делится на 34 (потому что 238 = 34 × 7), и поэтому НОД (238, 34) = 34. Финальный аккорд:
НОД (986, 748) = НОД (748, 238) = НОД (238, 34) = 34.
Подытожим: через какие этапы мы пришли к этому результату? Мы вычли 748 из 986 и получили 238. Мы трижды вычли 238 из 748. Почему мы совершили одну операцию вычитания в первом случае и три операции во втором? Мы хотели свести задачу к операциям с как можно меньшими числами, потому что так удобнее. Поэтому мы вычитали меньшее число из большего до упора. Заметим: 748 умещается в 986 всего один раз, и разница между ними равна 238. Однако 238 умещается внутри 748 три раза, и остаток равен 34. Мы можем вычесть 748 из 986 всего один раз, и в то же время мы можем вычесть 238 из 748 три раза.
Теперь мы обобщим этот пример и построим алгоритм вычисления наибольшего общего делителя для двух целых положительных чисел. Нам даны два целых положительных числа a, b, и мы хотим определить НОД (a, b). При этом a