Метод перебора

36

Ф. Бартенев, А. Савин

Метод перебора

Рассказывают, что однажды племянник Шерлока Холмса Джек образили к своему знаменитому дяде с просьбой помочь в решении следующего задачи*): Купили несколько одинаковых книг и одинаковых альбомов. За книги заплатили 10 руб. 56 коп. Сколько купили книг, если цена одной книги более чем на 1 рубль превосходит цену альбома, а книги купили на 6 больше, чем альбомов?

Прочтя условия, знаменитый сыщик прошел от стола к окну, затем вернулся к столу, постоял около него, установился в потолок, и, наконец, сказал: «Книг было куплено 8 штук».

«Как вы это установили?» — в один голос воскликнул Джек

*) В такой формулировке задача в действительности давалась на применных экзаменах по математике на физической факультете МГУ (1968 г.).

и присутствовавший при этом мистер Уотсон.

«О, это было совсем просто! — ответил Шерлок Холмс, усаживаясь в кресло. — Посмотрев на слова «книг купили на 6 больше, чем альбомов», я тут же понял, что книг купили не меньше 7. Из того, что «цена одной книги более чем на 1 рубль превосходит цену альбома», я сделал вывод, что каждая книга стоит больше 1 рубля, а поскольку за них заплачено 10 руб. 56 коп., книг купили не больше 10. Таким образом, все числа, больше 10, и все числа, меньше 7, оказались вне подозрений. Проверив каждое из чисел 7, 8, 9, 10, я установил, что искомое число может быть только 8: остальные не делят 1056».

Метод перебора, который воспользовался здесь Шерлок Холмс, видимо, является древнейшим из методов решения задач. Долго время его относил к методам «второго сорта», «переборные» решения считались некрасивыми. Однако в последние годы метод перебора применяется все чаще и чаще в задачах, где искомая величина принимает только целочисленные значения.

37

Перебор ведет ЭВМ

Известно много серъезных задач, которые математики не могут решать иначе, чем метод перебор. Правда, при этом перебор произойдет электронная вычислительная машина, а математик лишь инструкрует ее, как этот перебор нужно сделать. Известный американский математик С. Голомб пишет по этому поводу*): «В отличие от человека машина, решая задачи, произойдет однозобразные вычисления, которые каждятся нам столь скучными, с невообразимой быстротой. Но вместе с тем она не заметит способа просчитать или улучшить решение, если этот способ не будет заранее учтен программистом, составляющим детальные инструкции для работы ЭВМ».

Тем не менее в последние годы рост быстроействия и объема памяти компьютеров, их большая доступность и дешевизна позволяют все чаще использовать их для решения переборных задач. Так, знаменитая «задача о четырех красках» (Всякую ли географическую карту можно раскрасть четырьмя красками так, чтобы страны одинакового цвета не имели общих участков границ?) была решена — очень хитрым перебором — лишь при помощи ЭВМ. Недавно одна из наиболее известных задач о полимино из книги С. Голомба тоже была решена метод перебора с участием компьютера.

Турист укладывает рюкзак

К числу задач, решаемых методом перебора, относится так называемая «задача об укладке рюкзака»: Уложить в рюкзак предметы из заданного набора так, чтобы их суммарная масса была наиболее (и суммарный объем не превысил объема рюкзака).

В такой постановке задача выглядит игрушечной, но замените «риокзак» на «отскек в триом теллохода» и вы躬мете, что эта задача имеет существенное народное значение.

Уражде для 5 городов количество вариантов равно 24, для 6 городов их 120, для семи — 720, для десяти — 362880. Чтобы избежать полного перебора, математики придумали различные ухищения**. Делается это не зря — решение подобной задачи необходимо для нахождения налучшего маршрута для фургона, развозящого журналы и газеты по киоскам, автовуса, под-

*) С. В. Голомб. «Полимино» (М., «Мир», 1975).

Коммивояжер отправляется в путь

Другой ширококое известной задачей, решаемой перебором вариантов, является «задача коммивояжера»*): Как обжать несколько городов, между каждыми двумя из которых имеется железнодорожное сообщение, затратив как можно меньше времени, если задан город, в котором начинается и кончается путь?

*) Коммивояжер — путешествующий представитель торговой фирмы.
*) См., например, «Квант», 1978, № 6, с. 11.

38

бирающего сельских жителей на работу, и т. п.

Упражнение 2. На рисунке показана карта местности, на которой расположены 5 городов: Ax, Ox, Эх, Ух и Их, а в таблице указаны расстояния между ними по железной дороге. Найдите кратчайший путь коммувяжера, который должен выехать из города Ух, объехать остальные города и вернуться в Ух.

| | Ax | Их | Ox | Ух | Эх |
| :— | :— | :— | :— | :— | :— |
| Ax | 0 | 60 | 40 | 50 | 20 |
| Их | 60 | 0 | 30 | 35 | 45 |
| Ox | 40 | 30 | 0 | 55 | 50 |
| Ух | 50 | 35 | 55 | 0 | 20 |
| Эх | 20 | 45 | 50 | 20 | 0 |

Сократим перебор

Для решения подобных задач были созданы сложные методы, сокращшие перебор вариантов. Они составляют новую математическую науку, которая носит название «целочисленное программирование».

Некоторые представление о возможностях сокращения перебор может быть решено такой задачи:

Известно, что $\sqrt[3]{****3}$ есть натуральное число. Найдите его.

Первое, что приходит в голову, — это перебирать пятизначные числа, оканичивающиеся на 3, и смотреть, нет ли среди них точных кубов: 10003, 10013, 10023,… Но когда еще мы доберемся до 99993, да и как узнать, является данное число кубом или нет?

Лучше будем возводить число в куб и посмотрим, какие из них будут пятизначными и оканичивающимися на 3. Получим $1^3=1$, $2^3=8$, $3^3=27$, $4^3=64$, $5^3=125$, $6^3=216$, $7^3=343$, $8^3=512$, $9^3=729$, $10^3=1000$.

Так дело тоже неойдет. Зачем нам нужны кубы маленьких чисел? Посмотрим, чем равно наименьшее число $x$, куб которого является пятизначным числом. Оно не меньше чем $\sqrt[3]{10000}=10\sqrt[3]{10}$, но $\sqrt[3]{10}$ больше 2, так как $2^3=8$; поэтому $x$ больше 20. Оценим число сверху, то есть посмотрим, какого числа оно не может превышать. Такое число, очень видно, равно $\sqrt[3]{10000}=10\sqrt[3]{100}$. Но $\sqrt[3]{100}$ меньше 5, так как $5^3=125$. Значит, нужно перебирать числа от 21 до 49.

Посмотрим, не поможет ли нам сократить перебор то, что число под радикалом оканичивается на 3. Изучим выписанные нами кубы первых десяти натуральных чисел. Из них на 3 оканичивается лишь 7. Если теперь немного подумать, то нетрудно сообщить, что куб натурального числа будет оканичаться на 3 в том и только в том случае, если оно оканичивается на 7.

Теперь нам осталось для перебор лишь три числа: 27, 37 и 47. $27^3=19683$, $37^3=50653$, $47^3=103823$, но последнее число уже шестизначное, поэтому осталось лишь числа 27 и 37.

Упражнение 3.

В составлении 40 задач (для школьников) прияло участие 30 студентов (пединститута) со всех пяты курсов. Любые два однокурсника придумали одинаковое число задач. Любые студенты разных курсов придумали разное число задач. Сколько студентов придумало по одному задаче?

4. Сколько нулями может оканичивать число $9^n+1$?

5. В буфете продавалисьippiки по 5 коп., буфели по 6 коп., буфели по 7 коп., слойки по 8 коп., и коржки по 10 коп. Группа ребят купила на рубль 14 изделия в видов. Если взят по одному представителю каждой купленного вида, то их суммарная цена будет равна 21 коп. Сколько и каких изделий было куплено, если дополнительно известно, что никаких изделий не было куплено больше шести и никаких изделий не было куплено поровну?

6. Найдите два целых положительных числа, разность между квадратами которых равна 455.

7. Студент за 5 лет учebы сделал 31 экзамен. В каждом следующем году он сдавал экзаменов больше, чем в предыдущем. На пятом курсе экзаменов было второе больше, чем на первом. Сколько экзаменов было на четвертом курсе?