Эдвард Шейнерман - Путеводитель для влюбленных в математику

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] Несколько простых примеров: НОД (10, 15) = 5; НОД (12, 16) = 4; НОД (13, 11) = 1; НОД (10, 20) = 10; НОД (17, 17) = 17. .

Описанный выше метод дает незамысловатый и неоспоримый алгоритм поиска наибольшего общего делителя. Его слабая сторона – неэффективность. Для поиска НОД двух трехзначных чисел придется перебрать сотни вариантов. Может быть, есть что-нибудь попроще?

Присмотримся к числам 986 и 748 повнимательней. Мы ищем наибольший общий делитель, поэтому естественно разложить оба числа на простые множители [134] Разложение на множители при поиске НОД ( a, b ) гораздо эффективнее, чем поиск делителей вплоть до меньшего из двух чисел a и b . Поиск простых множителей числа a потребует самое большее операций деления. Это значительное усовершенствование первоначального алгоритма, но в случае стозначных чисел даже наш новый метод становится уже чертовский сложной задачей. (см. главу 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 – 3 yd = ( x – 3 y ) d .

Таким образом, d – делитель 748 – 3 × 238 = 34. И наоборот: если e – делитель 34 и 238, это также делитель 748. Вернемся к алгебре.

238 = ue , 34 = ve ,

где u и v – целые числа. Таким образом,

748 = 3 × 238 + 34 = 3 ue + ve = (3 u + 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 больше b . Мы должны вычесть b из a как можно большее число раз. Чтобы выяснить, сколько именно, поделим a на b . Мы получим частное q и остаток c . На языке алгебры:

a – qb = c .

Если окажется, что b – делитель a , тогда остаток будет равен нулю. В ином случае c больше нуля и меньше b (если бы c оказалось больше b , мы смогли бы вычесть b из a еще раз [135] Например, если a = 100 и b = 40, частное q = 2 и остаток c = 20. Иными словами, 100 – 2 × 40 = 20. ).

Теперь предположим, что d – общий делитель a и b . Тогда

a = xd, b = yd,

где x и y – целые числа. Следовательно,

c = a – qb = xd – q ( yd ) = ( x – qy ) d ,

и c тоже без остатка делится на d (потому что x – qy входит в множество целых чисел).

С другой стороны, если e – общий делитель b и c , тогда