Есть идея! - [54]
Во многих классических процедурных задачах, аналогичных задачам о переправах, фигурирует переброшенная через блок длинная веревка, к каждому концу которой прикреплено по корзине. Льюис Кэрролл очень любил следующий вариант такой задачи.
Пленная королева вместе со своим сыном и дочерью заточены в каморке на самом верху высокой башни. Снаружи у их окна прикреплен блок, через который перекинута веревка. На каждом конце веревки висит по корзине. Вес обеих корзин совершенно одинаков. Верхняя корзина, находящаяся как раз против окна темницы, пустая, в нижней корзине, достающей до земли, лежит камень массой 30 кг, служащий противовесом.
Блок сильно заржавел и вращается со скрипом достаточно медленно для того, чтобы спуск в корзине был безопасен для каждого, чья масса превышает массу противовеса не более чем на б кг. При большей разности масс удар о землю может причинить тяжкие увечья. Разумеется, если одна корзина поднимается, то другая опускается.
Масса королевы 78 кг, масса ее дочери 66 кг и масса сына 36 кг. Укажите простейший, то есть состоящий из наименьшего числа шагов, алгоритм побега. Корзины достаточно велики, чтобы вместить либо 2 людей, либо одного человека и камень. При побеге августейшим пленникам никто не помогает, и они не могут помочь себе, потянув за веревку. Иначе говоря, блок действует только в том случае, если масса в одной корзине превосходит массу в другой корзине.
Простейшее решение легко найти, если воспользоваться «аналоговым устройством»: написать массы на отдельных карточках и подвигать их вверх и вниз. Вам не удастся организовать побег всех трех узников менее чем за 9 шагов. Вот как выглядит наиболее экономичный алгоритм побега:
1. Сын вниз, камень вверх,
2. Дочь вниз, сын вверх.
3. Камень вниз.
4. Королева вниз, камень и дочь вверх.
5. Камень вниз.
6. Сын вниз, камень вверх,
7. Камень вниз.
8. Дочь вниз, сын вверх.
9. Сын вниз, камень вверх,
Задачи этого типа иногда усложняются введением животных, которые не могут самостоятельно влезать в корзины и вылезать из корзин. Льюис Кэрролл предлагает следующий вариант предыдущей задачи. На вершине башни вместе с королевой находились не только ее сын, дочь и груз, но и свинья массой 24 кг, собака массой 18 кг и кошка массой 12 кг. Спускать четвероногих нужно с теми же предосторожностями, что и людей, но теперь кто-нибудь непременно должен быть и наверху и внизу, чтобы класть животных в корзины и доставать их оттуда.
Удастся ли вам построить алгоритм побега короче 13 шагов? В обеих задачах тому, кто последним выйдет из корзины, следует поторапливаться, иначе он рискует получить по голове падающим противовесом!
Катастрофа на острове
Орвилл поставил свою машину на берегу небольшого озера.
Орвилл. Какой ровный берег! Для запуска моей радиоуправляемой авиамодели лучшего места не найти. Ни тебе деревьев, ни скал. Единственное дерево — на островке посреди озера.
Орвилл хотел было заставить модель облететь вокруг дерева, но не рассчитал расстояние. Модель врезалась в дерево и упала на землю.
Орвилл не на шутку встревожился. Оставлять модель на острове не хотелось: слишком много сил и средств было израсходовано на нее. Озеро было глубоким, а плавать Орвилл не умел. В багажнике машины у Орвилла на всякий случай хранилась веревка, длина которой на несколько метров превышала поперечник озера в самой широкой части, но как воспользоваться веревкой Орвилл не знал.
И вдруг Орвилла осенила простая и в то же время остроумная идея.
Орвилл. Делать нечего, придется намокнуть, зато модель будет спасена.
Как Орвилл достал свою модель?
Орвилл достал свою модель следующим остроумным способом. Он подогнал свою автомашину к самому краю воды и привязал к переднему бамперу длинную веревку. Держась за свободный конец веревки, он обошел дважды вокруг озера, отчего веревка обвилась вокруг ствола дерева, и, как следует натянув веревку, привязал свободный конец к бамперу. Получилась подвесная дорога: двойная веревка, натянутая между деревом на острове и бампером автомашины на берегу. Держась за веревку, Орвилл добрался до острова и, захватив модель, благополучно вернулся на берег.
В другой старинной головоломке речь идет о том, как, используя подручные средства, перебраться с суши на остров, который расположен в центре квадратного озера (рис. 8). Путешественнику необходимо побывать на острове. Плавать он, как и Орвилл, не умеет. На берегу путешественник нашел две одинаковые доски, но каждая из них слишком коротка и немного не достает до острова.
Как, пользуясь двумя досками, путешественник может попасть на остров? Решение показано на рис. 9.
Обобщим классическую задачу: предположим, что путешественник нашел на берегу несколько досок. Сможет ли он добраться до острова, если доски окажутся более короткими, чем в классической головоломке?
С тремя досками вы справитесь довольно легко, построив мост, изображенный на рис.
