Какой элемент отсутствует в головоломке про переправу на лодке
Задачи типа: «Переправы», «Фальшивый объект», «Переливания»
§1. Задачи типа: «Переправы», «Фальшивый объект», «Переливания»
1.1. Задачи типа «Переправы»
Задачи типа «переправы» – одни из самых старинных логических задач. Например, самая древняя из них – «Волк, коза и капуста» – встречается в сочинениях VIII века в сочинениях англосакского математика Алкуина (ок. 735—804).
Задача 1.1.1. Волк, коза и капуста
Условие задачи: Один человек должен был перевезти через реку волка, козу и кочан капусты. И не удалось ему найти другого судна, кроме как такого, которое могло выдержать только двоих из них. Нельзя было волка оставить с козой, а козу с капустой. Задача – переправить всех невредимыми.
Принцип решения: Рассмотрим пары «волк – коза» и «коза – капуста».
В первой паре присваиваем волку индекс А1, а козе – П1.
Во второй паре присваиваем коз индекс А2, а капусте – П2.
Следовательно, у волка индекс – А1, у козы – П1А2, а у капусты – П2.
Сначала перемещаем объект, являющийся активным и пассивным одновременно (в данном случае козу), затем возвращаемся обратно, берём любой оставшийся объект (волка или капусту), перевозим на другой берег, берём объект с индексами А и П (козу), переправляем обратно, берём другой объект (капусту или волка), переправляем на другой берег, возвращаемся назад, забираем объект с индексами А и П (козу), и переправляем на другой берег.
Ещё одна любопытная задача – «Отцы и дети».
Задача 1.1.2. Отцы и дети
Условие задачи: Двое друзей отправились на экскурсию, и каждый взял с собой своего сына. В пути они должны были переправиться через реку с помощью лодки, которая могла перенести самое большее 100 кг. Каждый из друзей вместе с рюкзаком весит 100 кг, а каждый из мальчиков 50 кг. Каким образом они переправились через реку?
Принцип решения: Сначала переправляются оба сына, потом один из них возвращается. Переправляется один из друзей, а возвращается второй сын. Затем снова переправляются оба сына, один из них возвращается, переправляется второй друг, а второй сын возвращается. В конце переправляются оба сына.
Есть ещё одна старинная задача, немного похожая на предыдущую – «Воинский отряд»
Задача 1.1.3. Воинский отряд
Условие задачи: Небольшой воинский отряд подошёл к реке, через которую необходимо было переправиться. Есть лодка, в которой сидят два мальчика. Лодка может вместить двух мальчиков или одного солдата. Как перевезти всех солдат через реку?
Принцип решения: В данной задаче можно составить цикл: два мальчика на другой берег – один возвращается – один солдат переходит – второй мальчик возвращается – второй солдат переходит. В данной задаче количество солдат не имеет значения.
Четвёртая задача встречается в одном из сочинений XIII века.
Задача 1.1.4. Каприз трёх девочек
Условие задачи: Через реку хотят переправиться три отца и три дочери. Имеется одна двухместная лодка. Как им переправиться через реку, чтобы ни одна из дочерей не оказалась на берегу с чужими отцами без своего?
Принцип решения: Переправляются две девочки. Одна из них возвращается и перевозит третью. Одна из девочек возвращается и остаётся со своим папой, а два других папы переправляются на тот берег. Один папа со своей дочкой возвращается на первый берег, девочка остаётся, а два папы отправляются на второй берег. Переезжает девочка и забирает с собой вторую девочку и за последней девочкой едет либо ёё отец, либо её подруга.
Следующая задача – одна из самых лёгких задач данного типа.
Задача 1.1.5. Ночная переправа
Условие задачи: Семья ночью подошла к мосту. Папа может перейти его за 1 мин, мама – за 2 мин, сын – за 5 мин и бабушка – за 10 мин. У них есть один фонарик. Мост выдерживает только двоих. Как им перейти мост за 17 минут, при условиях, что если переходят двое, то они идут с меньшей из их скоростей, двигаться без фонарика нельзя, перебрасывать фонарик через реку нельзя, светить издали и носить друг друга на руках запрещено?
Принцип решения: Переходят папа и мама (2 мин), затем папа с фонариком возвращается (1 мин), переходят бабушка и сын (10 мин), мама с фонариком возвращается (2 мин), переходят папа и мама (2 мин).
1.2. Задачи типа «фальшивый объект»
Задачи этого типа также известны с давних времён. В основном они касаются монет, например, задача о 12 золотых монетах:
Задача 1.2.1. Задача о 12 монетах
Условие задачи: Имеется 12 золотых монет. Одна из них – фальшивая – легче остальных. Найти фальшивую монету за 3 взвешивания.
Принцип решения: Делим 12 монет на 3 равные части. Берём две любые группы и кладём на весы. Если весы в равновесии, значит фальшивая монета в третьей группе. Если весы не в равновесии, значит, дальнейшему исследованию подлежит группа монет, которая легче. Делим исследуемую группу монет пополам и взвешиваем. Дальше исследуем группу монет, которая оказалась легче после результата второго взвешивания. Снова делим пополам и взвешиваем в третий раз.
Есть усложнённый вариант этой задачи:
Задача 1.2.2. Бриллианты и весы
Условие задачи: Имеется 242 бриллианта. Один из них – природный – легче остальных. Найти природный бриллиант за 5 взвешиваний.
Принцип решения: Кладём на весы по 81 бриллианту для выделения 81 или 80 бриллиантов. Второй раз кладём по 27 бриллиантов для выделения 27 или 26 бриллиантов. Третий раз кладём по 9 бриллиантов для получения 9 или 8 исследуемых бриллиантов. Четвёртый раз кладём на весы по 3 бриллианта для выделения 3 или 2 исследуемых бриллиантов. И пятым взвешиванием выделяем природный бриллиант, опуская на весы по 1 бриллианту.
Также есть более сложный вариант задачи о 12 монетах:
Задача 1.2.3. Задача о 12 монетах (усложнённый вариант)
Условие задачи: Имеется 12 золотых монет. Одна из них – фальшивая, но не известно, легче она или тяжелее остальных. Найти фальшивую монету за 3 взвешивания и установить, легче она или тяжелее.
Принцип решения: Сложность задачи в том, что не известно, легче или тяжелее фальшивый объект. Делим на 3 группы. На чаши весов кладём монеты №№ 1, 2, 3, 4 и №№ 5, 6, 7, 8. Возможны два случая:
Случай 1. Весы в равновесии. Следовательно, фальшивая монета в третьей группе монет с №№ 9, 10, 11, 12. Сравним вес трёх из них, например, №№ 9, 10, 11 с монетами №№ 1, 2, 3. Если весы в равновесии, то фальшивая монета – № 12, и если сравнить её с № 1, то можно определить, легче она или тяжелее. Если же весы не в равновесии, то фальшивая монета – одна из №№ 9, 10, 11, причём по положению чашки сразу можно выяснить, легче или тяжелее фальшивая монета. Затем кладём на весы по одной монете и определяем фальшивую монету.
Случай 2. Первое взвешивание не привело к равновесию. Пусть перетянула чашка с монетами №№ 1, 2, 3 и 4. Тогда фальшивая монета среди №№ 1, 2, 3, 4 и более тяжёлая, или она среди монет №№ 5, 6, 7, 8 и более лёгкая. Следовательно, монеты №№ 9, 10, 11, 12 – настоящие. Вторым взвешиванием сравним монеты №№ 9, 10, 11 и 5 с монетами №№ 3, 4, 6, 7. Тогда возможны три случая:
Случай 2.1. Весы в равновесии. Следовательно, выбранные монеты настоящие, а фальшивая – либо среди монет под №№ 1, 2 и более тяжёлая, либо под № 8 и более лёгкая. Сравнивая монеты №№ 1 и 2, установим, что фальшивая монета – лёгкая под № 8, если весы останутся в равновесии или, что фальшивая – тяжёлая № 1 или № 2 – та, которая перетянет.
Случай 2.2. Перетянет группа монет №№ 9, 10, 11 и 5. Тогда в этой группе фальшивой монеты быть не может, так как монета № 5 взята из группы более лёгких, а монеты №№ 9, 10 и 11 – настоящие, и эта чашка весов не могла бы перетянуть с тремя настоящими и одной фальшивой монетой. Следовательно, фальшивая – одна из монет под №№ 3, 4, 6, 7 и именно из группы, которая при первом взвешивании оказалась легче, то есть либо № 6, либо № 7. Более лёгкая из них выявляется третьим взвешиванием.
Случай 2.3. Перетянет группа монет №№ 3, 4, 6 и 7. Тогда – фальшивая монета более тяжёлая и находится на перетянувшей чашке весов – № 3 или № 4, или фальшивая монета более лёгкая и, следовательно, находится в группе монет №№ 9, 10, 11 и 5. В последнем случае – это монета № 5, так как монеты №№ 9, 10 и 11 – настоящие.
Следовательно, фальшивой монетой может быть одна из трёх: № 3 или № 4 (и тогда она более тяжёлая) или № 5 (и тогда она более лёгкая). Взвешиваем монеты №№ 3 и 4, и тогда если одна из монет перетянет, она и будет фальшивой, или если весы будут в равновесии тогда монета № 5 фальшивая и тяжелее остальных.
1.3. Задачи типа «переливания»
Задачи типа «переливания» имели самую большую практическую ценность, как в древние времена, так и в наши дни. Самая известная задача – задача о двух вёдрах.
Задача 1.3.1. Задача о двух вёдрах
Условие задачи: Есть два ведра объёмом 5 и 9 литров. Необходимо с помощью этих двух вёдер получить 3 литра воды.
Принцип решения: Наполняем 9-литровое ведро, выливаем 5 литров из 9-литрового в 5-литровое ведро, выливаем, переливаем 4 литра в маленькое ведро, наполняем большое ведро, сливаем из него один литр в маленькое ведро, выливаем маленькое ведро и переливаем 5 литров воды в маленькое ведро. В большом ведре осталось 3 литра воды.
Аналогичная задача была придумана французским физиком и математиком Симеоном Дени Пуассоном (1781–1840)
Задача 1.3.2. Задача Пуассона
Условие задачи: Во время экскурсии один из её участников купил бутыль вина ёмкостью 8 четвертей. Купленное вино необходимо было разделить пополам. Как можно было это осуществить, если на постоялом дворе было только два сосуда – один ёмкостью 5 четвертей и второй ёмкостью три четверти?
Принцип решения: Решение показано в формате «исходный сосуд – сосуд объёмом 5 четвертей – сосуд объёмом 3 четверти»:;;;;;;
Логические задачи и головоломки
Всем известна задача про переправу с одного берега на другой волка, козы и капусты. Эта задача ее разновидность.
Итак, есть трехместная лодка, одно из мест забронировано человеком. Нужно переправить на другой берег козла, капусту, двух волков и собаку, причем собака в ссоре с волком, козел неравнодушен к капусте, а волк и собака не могут оставаться наедине с козлом.
Ответ: Переправляются по очереди (разумеется, человек все время находится в лодке):
- Козел+Собака
- Собака
- Собака+Капуста
- Козел
- Два волка
- Собака
- Собака+Козел
- Математические задачи – Алгоритмы
- Добавить комментарий
Комментарии
Оставлен Гость Пт, 07/15/2011 – 12:31
1 Волк и капуста
2 Волк и козел
3 Козел обратно
4 Козел и собака
Оставлен Гость Ср, 07/20/2011 – 19:29
Волк съедает всех и сам плывет, и все вместе с ним))
Оставлен Гость Втр, 08/16/2011 – 21:58
Да просто катать козла туда и обратно, а волки пусть свои проблемы с собакой за капусту решат сами.
Оставлен Гость Пт, 07/15/2011 – 19:56
у меня получился другой вариант
1. берем козла и собаку – плывем к берегу и высаживаем козла
2. плывем назад с собакой
3. высаживаем собаку – забираем волков ( в лодке волки , на одном берегу капуста с собакой , на другом козел), плывем с волками к козлу
4. высаживаем волков ,забираем козла
доплываем с козлом обратно , высаживаем его – берем капусту и собаку
5. плывем с капустой и собакой к волкам- высаживаем капусту
6. плывем обратно с собакой за козлом
7. к капусте и волкам с козлом и собакой
всё.
прошу проверить на правильность.
Оставлен Гость Вс, 08/28/2011 – 10:16
Оставлен Гость Сб, 07/16/2011 – 22:29
1 Два волка ,по условию задачи , переправляем на берег
2 Возвращаемся за капустой и оставляем капусту и волков вместе
3 Берём собаку и козла
И все дружим)))
Оставлен Гость Пнд, 07/18/2011 – 08:27
Не получается по Вашему ответу: собака и козел по условию задачи не могут оставаться наедине
Оставлен Гость Ср, 11/02/2011 – 17:45
НЕЛЬЗЯ – НАЕДИНЕ, а В ЛОДКЕ они С ЧЕЛОВЕКОМ, значит МОЖНО.
Оставлен Гость Ср, 08/24/2011 – 09:21
Собаку и козла нельзя вместе. 1
Оставлен Гость Пнд, 07/18/2011 – 14:36
1. два волка
2. собака + капуста
3. козел
Оставлен 3JlouBuHHunyx Вс, 08/21/2011 – 10:25
Оставлен Гость Вс, 08/28/2011 – 10:13
после второго действия два волка накинутся на собаку и поминай как звали!
Оставлен Гость Пнд, 07/18/2011 – 14:38
1. два волка
2. собака + капуста
3. козел
Оставлен Maria Чт, 07/21/2011 – 06:58
1) козёл + собака в лодке, высаживаем собаку
2) козёл + капуста в лодке, оставляем капусту
3) козла высаживаем на тот берег, где 2 волка, волков забираем на другой берег. Высаживаем там, забираем оттуда собаку
4) забираем козла с другого берега (собака была в лодке). Высаживаем их на другой берег.
Понадобилось 9 минут, чтобы решить!
Оставлен Кристина Пт, 12/09/2011 – 08:12
на втором шаге коза съест капусту пока человек переправится на другой берег, т.е. нарушение правила “незя коз+кап”
Оставлен Гость Сб, 07/23/2011 – 14:27
1. Козел+собака, собака остается на другом берегу, с козлом обратно
2. Забираем капусту, переправляем, оставляем ее на другом берегу, с козлом обратно
3.Высаживаем козла на исходный берег, забираем двух волков, переправляем
4. Забираем с другого берега собаку, плывем обратно, забираем козла и переправляем) усё)
Оставлен Гость Пнд, 08/22/2011 – 05:24
да у меня также.
и это правильно просто надо рисовать!
Оставлен Кристина Пт, 12/09/2011 – 08:06
на втором шаге коза съест капусту пока человек переправится на другой берег, т.е. нарушение правила “незя коз+кап”
Оставлен Гость Сб, 07/23/2011 – 14:28
блин, потом увидела предыдущий коммент) простите)
Оставлен Гость Сб, 07/23/2011 – 14:30
хаха, а потом еще и ответ увидела хДДДД
Оставлен Гость Втр, 07/26/2011 – 09:34
1. козел+собака
2. один
3. 2 волка
4. козел+собака
5. капуста
6. один
7. козел+собака
Оставлен Кристина Пт, 12/09/2011 – 07:53
на втором шаге ты оставил в одиночестве козла и собаку, т.е. нарушил правило “незя коз+с-чел”
Оставлен Л Втр, 07/26/2011 – 11:15
сначала берем козла и переправляем на другую сторону, возвращаемся за двумя волками и переправляем их туда-же куда и козла, но при забираем с собой козла чтобы не оставлять его волкам, затем садим собаку и капусту в лодку чтобы козел один остался на одной из переправ, последним шагом переправляем козла ко всем остальным.
Оставлен Гость Чт, 08/04/2011 – 12:03
собака и волк тоже в соре!
Оставлен Гость Втр, 08/02/2011 – 10:24
А нельзя всех по одиночке перевезти?!
Оставлен Неизвестно Чт, 08/04/2011 – 16:52
Оставлен Тормоз Пт, 08/19/2011 – 12:11
Искренне недоумеваю постановке вопроса. В каждой задаче. Либо авторы пишут далеко не все условия, либо мудрствуют лукаво с ответами.
Оставлен Кристина Пт, 12/09/2011 – 07:50
правила просты – их 4 штуки:
1)незя “в+с” = оставлять волка с собакой на каком-либо берегу и даже в лодке с человеком
2)незя “коз+кап” = оставлять козла с капустой на каком-либо берегу и даже в лодке с человеком
3)незя “коз+в-чел” = оставлять козла с волком на каком-либо берегу (в лодке с человеком конечно можнА)
4)незя “коз+с-чел” = оставлять козла с собакой на каком-либо берегу (в лодке с человеком конечно можнА)
вот и всё!
Дополнительно:
Сначала мы имеем всех на одном берегу = тут как бы сразу нарушены все правила и это не важно, т.к. такова исходная ситуация! Наша задача – не нарушать ни одно из правил ни на одном НАШЕМ ШАГЕ! Но в результате последнего шага все снова окажутся вместе на другом берегу = тут тоже как бы нарушены сразу все правила и на это тоже нам класть, т.к. такова наша цель! МожнА просто считать, что например, сущ-ет еще одно правило – можнА “в+в+с+коз+кап” = всех вместе можнА оставить (именно всех сразу!)
З.Ы. волк, капуста, козел, собака, человек = в, кап, коз, с, чел
Оставлен Холи Пт, 08/05/2011 – 14:02
1.Собаку(С) и козу(К)
2.Волка(В1) и волка(В2)
3.оставляем волков забираем С и К
4.Забираем капусту оставляем С и К
5.Перевозим капусту волкам плывём за С и К
Оставлен Кристина Пт, 12/09/2011 – 07:19
После первого шага ты сразу нарушил правило : коз+с-чел, т.е. козла и собаку оставлять одних (получается, что именно без человека) незя!
Оставлен Денра Пнд, 08/08/2011 – 15:53
Всем доброго время суток!!
Сначала берем Козла и Собаку, переправляем их. Затем с собой берем Козла и забираем Первого Волка, перевозим их. В заключение берем с собой Второго Волка и Капусту!
Все живы и довольны 🙂
Оставлен Кристина Пт, 12/09/2011 – 07:16
После “Затем с собой берем Козла и забираем Первого Волка, перевозим их.” ты на втором берегу оставил козла, волка и собаку, нарушив 3 из 4 правил: коз+в, коз+с и в+с.
Оставлен Гость Ср, 08/10/2011 – 08:44
вроде решил , обидно если не прав , ну ладно .
1Собака и Коза
2возвращаемся
3берем капусту
4увозим козу на первый берег
5с первого на второй везем волков
6собаку перевозим к козе .
получается что на первом у нас Пес и Коза , а на втором волки с капустой .
7ну и перевозим собаку с козой .
задача решена
Оставлен П.Р.Я.Н.И.К. Чт, 08/11/2011 – 23:02
Решение было проще чем у многих за 7 ходов. 1.перевозим капуста+собака 2.собаку везем обратно 3. Оставляем собаку и везем 2 волков. 4. Оставляем 2 волков и возвращаемся за оставшимися козлом+собака.
Оставлен Гость Вс, 08/14/2011 – 18:58
Козла и собаку нельзя оставлять вметсте.
Оставлен Сергей Пт, 08/26/2011 – 00:01
Взяв капусту и собаку в лодку – оставили козла и волков на берегу. Хана козленочку))))
Оставлен Гость Пнд, 08/22/2011 – 17:59
1 капуста и козел в лодку
2 капусту выгружаем, козла везем обратно
3 собака и козел в лодку
4 собаку выгружаем козла опять обратно
5 выгружаем козла берем волков
6 выгружаем волков берем собаку
7 берем козла и везем его вместе с собакой
Оставлен Гость Ср, 09/28/2011 – 07:48
после первого шага волки порвали собаку 🙂
Оставлен Гость Втр, 08/23/2011 – 14:06
я так понимаю что в условии задачи корректней было бы обозначить “СОБАКА В ССОРЕ С ВОЛКАМИ! а не с волком – тогда все логично
Оставлен воронеж Пт, 09/23/2011 – 14:50
а вы думаете на какой почве между собакой и волками непонятка произошла?? Конечно из-за капусты.. собака денег волку должна:)) он даже братана позвал долги вышибать.. Так что капусту с собакой никак нельзя оставлять, а тем более с волками:)) нарешали тут))
Оставлен Стасон Клим. Чт, 11/17/2011 – 04:45
)))) Короче, заберут за долги и лодку и козла трухлявого, А деда заставят утопить собаку, чтоб остальным не повадно было волков на лавэ брить. Таким образом происходит плавный, бесшовный переход к рассказу “Муму” ))))
Оставлен Hamo Вс, 06/19/2016 – 19:23
а я тоже думаю на между собакой и волками непонятка произошла?? Конечно из-за капусты.. собака денег волку должна:)) он даже братана позвал долги вышибать,а по моей версии..
собака утопит свидетеля лодочника (такая песня ест —я убью тебя лодочник),возьмёт капусту,а козла оставит с волками, отсюда и появился выражение —козёл отпущения– устроит, капусту с собакой никак нельзя оставлять,но вы же знаете ,что собаки всегда берут чужую капусту, —–вот и на решалься тут))
Оставлен Hamo Вс, 06/19/2016 – 19:24
а я тоже думаю на между собакой и волками непонятка произошла?? Конечно из-за капусты.. собака денег волку должна:)) он даже братана позвал долги вышибать,а по моей версии..
собака утопит свидетеля лодочника (такая песня ест —я убью тебя лодочник),возьмёт капусту,а козла оставит с волками, отсюда и появился выражение —козёл отпущения– устроит, капусту с собакой никак нельзя оставлять,но вы же знаете ,что собаки всегда берут чужую капусту, —–вот и на решалься тут))
Оставлен Гость Вс, 11/20/2011 – 02:18
Решил очень быстро
Взять с собой собаку и козла, отправиться на другой берег, оставить козла, собаку взять с собой, оставить собаку, взять двух волков, перебраться на другой берег, оставить волков, взять козла, вернуться, оставить козла, взять капусту и собаку, оставить капусту, вернуться за козлом
Оставлен Кристина Пт, 12/09/2011 – 08:33
есть несколько вариантов, а придумать можнА еще много (с нерациональными замкнутыми кругами и т.д.), а вот кратчайших вариантов два (по 7 шагов).
ВАРИАНТ 1:
берег1 река берег2
в+в+кап+коз+с
1) в+в+кап -> чел+коз+с ->
2) в+в+кап 3) кап+с -> чел+в+в -> коз
4) кап+с 5) коз -> чел+кап+с -> в+в
6) коз 7) -> чел+коз+с -> в+в+кап
в+в+кап+коз+с
ВАРИАНТ 2 (прост меняем две пары “кап+с” и “в+в” местами в шагах 3-4-5):
берег1 река берег2
в+в+кап+коз+с
1) в+в+кап -> чел+коз+с ->
2) в+в+кап 3) в+в -> чел+кап+с -> коз
4) в+в 5) коз -> чел+в+в -> кап+с
6) коз 7) -> чел+коз+с -> в+в+кап
в+в+кап+коз+с
В ответах дан второй вариант. Первый вариант молодечик догался тут написал кто-то =)
А я программер по профессии прост составила прогу быстро, которая мне и показала все варианты))) обожАю алгоритмы, проги, головоломки, статистику.
Оставлен Гость Ср, 11/19/2014 – 04:38
1. козёл + собака
2. 2 волка, козла и собаку обратно
3. какпусту
4 козёл + собака
Какой элемент отсутствует в головоломке про переправу на лодке
Эта задача аналогична задаче 2. Разница только в том, что вагоны не могут двигаться без помощи паровоза. Зато в тупичок помещаются сразу три вагона.
Сначала загоняем в тупичок последние три вагона товарного поезда, а паровоз с двумя оставшимися вагонами проезжает далеко направо. Следом за ним направо проезжает пассажирский поезд, подает назад, прицепляет три вагона, стоящие в тупичке, вытягивает их из тупичка и сдает назад вместе с ними по главному пути. Теперь паровоз с двумя товарными вагонами заезжают в тупичок задним ходом, а пассажирский поезд отцепляет от себя товарные вагоны и прродолжает свой путь. Наконец, паровоз с двумя товарными вагонами выезжает из тупичка, сдает назад по главному пути и снова цепляет осташиеся три вагона.
Дополнительные задачи
Сначала заметим, что в какой-то момент в лодке придется сидеть двум мальчикам одновременно, иначе один мальчик уплывет на лодке с самого начала, и некому будет вернуть ее обратно. Поэтому лодка должна иметь грузоподъемность не менее 80 кг (это минимальный вес пары мальчиков из нашей компании).
Теперь докажем, что лодки грузоподъемностью 80 кг хватит. Способ переправить нашу компанию мальчиков с помощью такой лодки аналогичен решению задачи 3. В роли двоих мальчиков из той задачи могут выступать любые два мальчика весом 40 кг (а по условию таких мальчиков не меньше двух), а остальные мальчики будут выступать в роли солдат. Лодка грузоподъемностью 80 кг выдерживат двух мальчиков весом 40 кг или одного «солдата» весом 50 или 60 кг (или даже двоих «солдат» весом по 40 кг, хотя это и не требуется).
Сначала Р забирает N, выезжает направо и подаёт задним ходом далеко налево. Там он оставляет вагон N, затем выталкивает М в промежуток А, возвращается, цепляет N и выезжает направо. Далее Р (вместе с N) задним ходом подъезжает к М и цепляет его позади N. Теперь Р c прицепленными к нему M и N выезжает направо, а затем задним ходом далеко налево. Там он оставляет вагон М и едет снова направо. Задним ходом Р заезжает в промежуток А и оставляет там вагон N. Затем он возвращается за вагоном М, уезжает с ним далеко направо, задним ходом подаёт на правую ветку, там оставляет вагон M, а сам уезжает на левую ветку и вытаскивает на неё из промежутка А вагон N. А сам возвращается на исходную позицию.
Совет. Чтобы понять это решение, нужно последовательно нарисовать все происходящее на картинках (каждую ситуацию нужно рисовать на отдельной картинке!). Если же вам (как и автору этого текста) лень рисовать столько картинок, нарисуйте на бумаге рельсы и катайте по ним машинки или ластики. Или используйте игрушечную железную дорогу (если она у вас есть).
Задача о переправе
На Тостере иногда встречаются вопросы о том, как научиться думать как программист. Год назад я ради развлечения решил написать программу которая решает всем хорошо известную задачку — головоломку о волке, козе и капусте. В англоязычных источниках известную как river crossing puzzle.
В этом посте я представлю вам пример мыслительного процесса от задачи к ee алгоритмическому решению.
Должен признаться, что из-за многолетнего влияния объектно-ориентированной парадигмы на мой мозг, первое, что мне пришло в голову, это для всех сущностей, участников задачи, написать классы. Проблемно-ориентированное программирование и все такое. Но я вовремя остановился, вспомнив старые учебники по паскалю, где оперировали понятиями фунцкия и процедура.
Чтобы перевести задачу в плоскость понятную машине, нам нужно избавиться от тех частей контекста задачи, который не имеет значения для ее решения.
Не имеет значения все, что нельзя выразить числами. Капуста это или мяч не имеет значения, важно, что участников четверо. Река перед ними или гора — неважно, есть два места где могут находиться участники этой задачи. На лодке они переправляются или на самолете — неважно, они могут перемещаться с одной точки в другую и наоборот, при чем в перемещении всегда задействован крестьянин (или «мужик») — особенный участник.
В полной абстракции условия будут выглядеть как-то так:
- Есть набор из трех элементов и один специальный элемент.
- Есть запрещенные комбинации элементов (при отсутствии специального элемента)
- В комбинации со специальным элементом все комбинации допустимы.
- Нужно перенести все элементы с одного места в другое, так чтобы никогда не образовывались запрещенные комбинации элементов.
- При этом переносить можно лишь один элемент, либо в одну, либо в другую сторону, поочередно. Т.е. нельзя сделать два переноса в одну сторону. — спасибо Dr_Dash за то, что заострил на этом внимание.
Чтобы различать элементы и их комбинации, нам нужно дать им идентификаторы. Машина лучше всего работает с числами — обозначим их числами. Мы хотим комбинировать элементы. Комбинировать числа значит делать над ними арифметические операции.
Тогда закодируем отдельные значения так, чтобы сумма чисел однозначно указывала на комбинацию:
0 — никого
1 — P Крестьянин(Peasant)
2 — G Коза (Goat)
4 — C Капуста (Cabbage)
8 — W Волк (Wolf)
Буквы тут только для мнемоники и никакой нагрузки не несут
То, что крестьянин обозначен числом 1 — важно. Изза этого «код конфигурации берега» с крестьянином всегда будет нечетным. Так можно будет понимать на с какой стороны он находится.
Запишем возможные комбинации на обеих берегах в виде таблицы, и отметим допустимые варианты распределения участников по берегам иксом:
Заметим, что возможные комбинации конфигурации берегов всегда в сумме дают 15, но не все из них допустимы.
Из визуального представления в виде таблицы становится ясно, что нам нужно перейти из одного угла таблицы в другой, переходя при этом только в допустимые состояния.
Какой берег левый, а какой правый, для задачи не имеет значения. Т.е указав код конфигурации например 11, мы говорим, что на одном берегу находятся крестьянин, коза и волк. То, что капуста на другом берегу не нужно особенно указывать. Поскольку в сумме оба берега дают 15, то 4 — капуста, на другом берегу.
Представим себе, что наши состояния это камни в воде, и мы перепрыгивая с камня на камень должны переместиться с одного конца в другой. Напоминает ленту машины Тьюринга, правда?
На ленте начало обозначено черным треугольником справа, а конец — перевернутым треугольником слева. Возможные промежуточные состояния обозначены черными точками. Недопустимые состояния помечены крестиком.
Перемещаться мы можем только в допустимые состояния. Также, из условия задачи известно, что в перемещении всегда участвует крестьянин и, что лодка умещает максимум двоих. Значит, мы можем оперировать числами 1 (крестьянин), 3 (крестьянин и коза), 5 (крестьянин и капуста), 9 (крестьянин и волк).
Получается, если мы начинаем из состояния 15, когда все на одном берегу — единственное из возможных следующих состояний это 12. Из состояния 12 у нас нет другого выхода, кроме как вернуть крестьянина на другой берег, делаем +1. Переходим в состояние 13. Отсюда мы можем сделать либо -5 (перевезти капусту) либо -9 (перевезти волка). Если мы сделаем -9 то попадем в состояние 4, но крестьянина после этого надо вернуть. Одного его мы вернуть не можем, иначе мы окажемся в состоянии 5, но мы можем вернуть его с козой т.е. +3, и окажемся в состоянии 7(коза капуста и крестьянин). Отсюда мы можем сделать либо -3 (эвакуировать козу) либо -5 (спасти капусту). Поскольку -3 было бы откатом предыдущего действия, остается -5. Мы переходим в состояние 2. Отсюда мы можем сделать только +1, и +9 (поскольку +5 было бы откатом предыдущего действия, a +3 недопустимое состояние).
Заметьте, +3 невозможно здесь не потому, что «коза ведь на другом берегу» (это обьяснение понятное человеку), а потому, что это переход в недопустимое состояние («обьяснение» понятное машине). Делаем +1. Переходим в состояние 3. Делаем -3. Готово.
Но это не единственно возможное решение. Заметьте, что человеку трудно отслеживать все перемещения. Для машины же, существует набор допустимых и недопустимых состояний, и набор правил.
Давайте заставим машину найти все возможные решения задачи. T.e. найти все возможные цепочки состояний которые ведут к решению. Воспользуемся рекурсией и питоном в качестве языка.
Для хранения цепочек переходов возьмем массив. Первое состояние в массиве 15. Передадим его в фунцкию рекурсии. Определим условие окончания рекурсии. Это когда конечный элемент цепочки будет 0.
Если состояние четное (крестьянин на другом берегу), то мы выполняем одну из возможных операций с положительным знаком (+1, +3, +5 или +9).
Для каждой возможной операции должны выполняться условия:
— она не ведет в недопустимое состояние,
— она не ведет за максимальную положительную границу ленты
— она не ведет в состояние в котором мы уже были.
Если такая операция имеется, выполни ее, и добавь новое состояние к цепочке состояний.
Передай новую цепочку состояний в рекурсивную фунцкию.
Если же состояние нечетное, то мы следуем тем же соображениям, но со знаком минус.
На выходе получим
[15, 12, 13, 4, 7, 2, 3, 0]
END
[15, 12, 13, 8, 11, 2, 3, 0]
END
None
Заметим, что в решении четные и нечетные числа чередуются. Это перемещения крестьянина с одного берега на другой. Не зря выше мы обозначили его единицей.
Также обратим внимание на то, что изначальные условия задачи, понятные человеку, в программном решении превратились в цифры и операции над ними.
Надеюсь, кому-то эта статья окажется полезной.