Время собирать камни
(о решениях мини-конкурса для программистов)
Константин Кноп
Начну с философской шутки: есть время разбрасывать деньги и время
собирать стулья. Если вас заинтересовали задачки, собранные мною в
статье "Мини-конкурс для программистов", пришло самое время узнать, как
же они решаются. В целях экономии журнальной площади я не повторяю
условия заданий, а ограничиваюсь только их названиями.
1.1 WEB-игра
Вася должен "вести" одновременно две цепочки адресов. Начав их с
одной и той же странички, он в одной цепочке будет двигаться вперед, как
обычно, а в другой - идти сразу на две ссылки вперед. Таким образом,
"расстояние" между цепочками за каждый ход увеличивается на 1. Если
Васиному путешествию суждено зациклиться и длина его цикла равна N, то
не позже чем через N шагов после попадания в цикл "расстояние" между
цепочками нацело разделится на N, то есть в обоих окнах браузера
окажется одна и та же страница. Если же цикла нет - такого совпадения
никогда не произойдет.
1.2 Аргентина манит негра
Надо просматривать строку посимвольно с двух концов, двигаясь
навстречу и при этом игнорируя пробелы. Если все непробельные символы
окажутся одинаковыми - строка является палиндромом.
1.3 Экономный обмен
Требуемая операция - это просто циклический сдвиг всей таблицы на M
элементов влево. Его удобно представить себе, расположив мысленно все
элементы по кругу. Мы можем начать выполнять этот сдвиг с любого
элемента и двигаться по цепочке от перемещаемого элемента к тому,
который переместился на его место (каждый раз - двигаясь на M по циклу).
Одновременно надо считать число выполненных перемещений.
Если, когда мы вернемся к исходному месту, число перемещений
окажется меньше N, то надо перейти к соседнему элементу (сдвинуться на
1) и продолжать перемещения от него.
1.4 Двумерный поиск
Красивое решение состоит в том, чтобы выполнять просмотр, начав с
правого верхнего угла массива. Сравнив текущий элемент A с величиной X,
мы должны сдвинуться влево, если A>X, и вниз, если A<X. Таким образом,
для массива MxN мы за M+N-2 хода попадем в левый нижний угол. Если при
этом элемент, равный X, не будет обнаружен, то его в массиве нет.
1.5 Среднестатистический китаец
Подсказка: диапазон возможных значений человеческого роста гораздо
меньше, чем число китайцев. А именно, от 40 сантиметров (лилипуты) до
240 сантиметров (говорят, и такие великаны бывают, хотя вряд ли они
есть в Китае). Достаточно завести вспомогательный массив и для каждого
роста подсчитать число китайцев, имеющих такой рост. После этого задача
становится тривиальной.
Справедливости ради надо отметить, что аналогичная задача и в общем
случае (когда ничего не известно о значениях элементов таблицы) может
быть решена за время, прямо пропорциональное длине таблицы. Но
соответствующий алгоритм чрезвычайно сложен и вряд ли пригоден для
использования на практике (см. Д.Кнут, "Искусство программирования для
ЭВМ", том 3, стр.251-262).
1.6 Казнь по кругу
Именно такой способ казни описан Иосифом Флавием в "Иудейской
войне". Сам Иосиф и его верный друг, попав в плен, выжили благодаря
тому, что сумели сообразить, в какие места они должны встать (двух
последних пленных враги обещали помиловать).
Задача быстро решается либо с использованием двусвязных списков,
либо рассмотрением процесса с конца - последовательно добавлять людей в
круг оказывается проще, чем исключать их из круга. (И еще одно замечание
для совсем крутых математиков: на самом деле она решается вообще без
рассмотрения процессов на круге. Достаточно немного повозиться с
двоичными записями чисел M и N).
1.7 Найти пропуск
Пожалуй, проще всего найти сумму всех элементов массива и вычесть
ее из суммы всех чисел от 0 до N. Результат, очевидно, равен
отсутствующему числу.
1.8 Плюс-минус
Здесь переборная программа требует очень большого времени - ведь
всего имеется 2^100 вариантов. Выручает алгебра: для любых восьми
последовательных квадратов целых чисел можно поставить между ними ровно
4 минуса (перед вторым, третьим, пятым и восьмым квадратами) и плюсы
перед остальными числами - полученный результат будет равен нулю. Таким
образом, последние 88 квадратов из 100 можно сразу отбросить, а в первых
двенадцати отыскать нужную расстановку минусов (даже полным перебором)
не составляет большого труда.
2.1 Переправа
Требуется 17 минут: сначала идут папа с мамой (2'), затем папа
возвращается с фонариком (1') и идут бабушка с младенцем (10'),
после чего мама снова возвращает фонарик папе (2') и они вместе
присоединяются к остальным (2').
2.2 Двенадцать монет
2.3 Тринадцать монет
Эти задачи решены во многих книгах по занимательной математике.
Общее решение (алгоритм, дающий минимальное число взвешиваний для случая
n монет) содержится, например, в книге Ж.Байифа "Логические задачи"
(Мир, 1983), гл. 4, задачи 13 и 14.
2.4 Настоящая монета
Да, можно. Ключевая идея здесь такова: если весы, на чашки которых
положено по одной монете, оказались не в равновесии, то можно выкинуть
обе этих монеты - при этом по-прежнему большинство из оставшихся монет
будут настоящими.
2.5 Пять предметов
Для полной сортировки пяти элементов требуется всего 7 сравнений.
(Зная это, отыскать решение с семью взвешиваниями уже не очень сложно).
2.6 Размен доллара
Правильный ответ в этой задаче - 77 монет. Я не совсем понимаю, на
какой подход к решению рассчитывали люди, дававшие эту задачу на
интервью.
2.7 Пропавший доллар
Это обманный трюк (увы, на собеседованиях бывают и такие. До того,
как я начал собирать материалы для своей статьи, я этого не знал)!
Доллар никуда не пропадал, просто условие содержит абсурдный подсчет: к
27 долларам, уплаченным гостями, прибавляются те два доллара (из них
же!), которые остались у посыльного.
2.8 Три пловца
Нет, никакой ошибки здесь нет. Например, в трех общих заплывах они
приходили к финишу в таком порядке: 1) А Б С; 2) Б С А; 3) С А Б.
Из-за нехватки места я не смог привести более полные решения.
Тем не менее, как говорили латиняне, "sapienti sat" - "мудрому
достаточно". Остается надеяться на мудрость читателей.
|