Логические задачи : Людоеды и миссионеры на переправе

	"Логические задачи" - это познавательно-развлекательный проект для непрокисших мозгов. Задачи на логику, нестандартное мышление. Не всегда самое очевидное решение - правильное. Но иногда всё оказывается проще, чем кажется на первый взгляд.
Задачи на логику и сообразительность
Главная \| О проекте \| Все задачи-1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C \| Добавить задачу

О сайте
Гостевая книга
ЧаВо

Пользователи
RSS

Поиск на сайте

запомнить меня

Задачи

Переливания и взвешивания

Теорвер, комбинаторика

Задания на наблюдательность

требуется помощь

Чисто поржать

Детские с подковыркой

Данетки

Текущие:

  Мой любимый грех (с)
  Математика в архитектуре
  Не сыпь мне соль на рану
  «Геометрическая»
  Высказывание Ломоносова
  Наверное, не про яблоки
  Комерция
  Везде градусы
  Вагончик тронется, вагончик тронется..
  Спасибо медикам и католикам))
  Специальная купюра
  Студенческая смекалка
  Эллипс vs Круг
  Современные технологии. Немецкий стандарт.
  Спортивная
  философская
  Про газету
  печатная монета
  Купюра евро
  Древние изобретения
  Биометрические паспорта
  Новый глава
  В далеком созвездии тау Кита... 8)))
  Огородное
  Средневековое строительство
  Жестокое наказание
  Их нравы - 4
  Европейский стандарт

Разгаданные недавно:

  этот модный тандыр
  Из Что-Где-Когда
  Может ли такое быть?
  Что изображено?
  Да на тебе пахать надо!

Справочная

Признаки делимости
Площади фигур

Реклама

Версия для смартфонов

задача: Людоеды и миссионеры на переправе

Задачу прислал: ди

Племя из M миссионеров и L людоедов находится по одну сторону реки, через которую необходимо переправиться. В распоряжении имеется одна лодка, которая может выдержать вес только K представителей этого племени (все имеют одинаковый вес). Кроме того, если в какой-то момент времени число людоедов станет больше числа миссионеров, миссионеры будут съедены независимо от того, на каком берегу или в лодке это случится. Сформулировать алгоритм решения.


+ 2 -

решение

Ваши ответы на задачу

ответов: 8

Асылбек 2012-09-29 14:09:32 пишет:

[скрыто]

Вася Пупкин 2012-09-01 04:07:33 пишет:

Растак-перетак, да что ж такое-то... Я всяду перепутал К и Л, считая, что К -- от "каннибалы" а Л от "лодка"(а в оригинале Л было от "людоедов", а для емкости лодки К). Пожалуйста, учитывайте или поправьте.

Вася Пупкин 2012-09-01 04:03:55 пишет:

А, блин, сонный был. Минус единицу всюду вычеркнуть либо сделать неравенства нестрогими. В последней строчке, про раздуваниое -- вместо K читать Л(емкость лодки).

Вася Пупкин 2012-08-31 09:22:17 пишет:

Кокос, Вам бы кликуху на Репейник сменить :)). Да, это я накосячил, насчет негодности двушки при К=M. Ссылку Вашу поглядел, решения там нечитабельны, но из задачки понятно, что решение есть, и понятен принцип -- сперва, надо думать, все плохие переходят, потом один пригоняет лодку, и начинается переправа хороших с подержкой баланса: переезжают двое хороших, обратно едут плохой и хороший, двое хороших сваливают, и дальше единственный оставшийся на трагетном берегу плохой перетаскивает своих собратьев. Я сейчас засыпаю, поэтому конспективно: имеются, значит, три места -- два берега и лодка. Понятно, что если все три заполнены гетерогенно, то все три должны быть строго пополам. Лодка может быть заполнена чисто хорошими, только если в пункте ее назначения гомогенная злодейская компания той же мощности, а за спиной -- гомогенная злодейская, либо гетерогенная пополамная. При этом, если таких гомогенных рейсов больше одного, имеет место возврат лоски с гетерогенным пололамным экипажем. Отсюда следует, что лодка емкости Л решает задачу при К меньшем, чем 2*Л-1. Двойка, в частности, обслуживает К до тройки. Для четверки и пятерки тот же трюк сделает лодка-трешка(для примера с пятеркой: трое плохих уже переправлены, к ним едут трое хороших, обратно пара плохой-хорошй, туда опять три хороших, и дальше плохие уже опять сама-сама-сама), но для шестерки она уже не работает(2*Л-1 строго больше К). Нужна лодка-четверка. Но лодка-четверка, о радость, банальным образом обслужит дальше любые К, без всяких подвыпердов: просто туда два злых, два добрых, обратно пара злой-добрый, и так пока все не переедут. Хотя, конечно, с дальнейшим раздуванием К можно побыстрее, но пофиг уже.

KoKos 2012-08-30 10:43:29 пишет:

:) Вася Пупкин, существует решение для жесткого варианта при M=L - я на него-то и ссылался. ;) Но тогда дополнительное условие должно быть наложено на грузоподьемность лодки K.

Вася Пупкин 2012-08-30 10:12:51 пишет:

Ну, для начала обрежем лишнее, потом найдем решение для обрезанного случая, а потом его усилим. Во-первых, понятно, что М >= L, иначе миссионеров съедят сразу. Во-вторых, понятно, что в лодке д.б. мест не меньше двух. В третьих, понятно, что если решение найдено для двухместной лодки, так оно сойдет и для большеместной, используемой как двухместная. В четвертых, понятно, что при данном L должно быть минимальное M, при котором есть решение -- ну, а если мы его найдем, так лишние миссионеры постоят в сторонке, мы потом отправим один раз за ними людоеда, и дальше они подтянутся. Так что будем искать наверняковое решение, а оптимизация -- пес с ней пока. Дальше, не уточнено, что происходит, когда лодка причаливает к берегу -- объединяются ли люди в ней с береговыми. Или же лодка всегда отдельно от берега, и объединения нет. Это существенно для пограничных съели-не съели ситуаций. Второй вариант назовем мягким, первый жестким. При мягком вариате миссионеров изначально может быть ровно столько же, сколько людоедов, и решение такое: людоед перевозит на другую сторону по очереди миссионеров и людоедов, начиная с миссионера. Тогда на каждом берегу миссионеров и людоедов попеременно то поровну, то миссионером больше, в лодке тоже все безопасно, все пучком. При жестком же варианте эта схема не проходит. Заметим, что вообще равные количества миссионеров и людоедов при жестком варианте не перевозимы. А если M=L+1? Тогда решение существует. На противоположный берег всегда плывет пара миссионер-людоед, а назад лодку пригоняют попеременно то миссионер(если на исходном берегу осталось поровну тех и других; тогда на таргет-береге есть лишний миссионер для посылки), то людоед(если на исходном миссионеров на одного больше, и, сталть, он не поменяет расклада, причалив; на таргетном же в это время осталось на одного миссионера больше, чем людоедов). На таргетном же берегу прибытие пары миссионер-людоед ситуацию ухудшить не может. Ну, вот, собственно, и все. Общий же случай -- ну, грю ж, неинтересно оптимизировать, и как -- тоже сразу не видно. Но так или иначе, границы мы очертили и для них решение описали.

KoKos 2012-08-30 02:36:55 пишет:

не представился (или ди?), сорри был целый день плотно занят, трактат писать было некогда. :( Если еще не поздно, то вот... Сперва очевидные факты: Либо M, либо L больше нуля (иначе переправляться-то и некому); если M - ненулевое, то M обязано быть больше или равно L - иначе они и до лодки-то не доберутся :))); также K обязано быть больше единицы - иначе имеем патовую ситуацию, пригнать лодку обратно будет некому. К сожалению, у меня был трудный день сегодня, и мне даже не столько лень, 8))) сколько мозг просто оказывает. Еще раз сорри. :((( Если бы не просьба о срочности, я вообще бы не отписывался, подождав до лучших времен... Посмотрите решение для частного случая вот здесь http://lprobs.ru/prob1087solve.html - надеюсь, Вы поймете суть прикола.

не представился 2012-08-29 15:20:16 пишет:

ну очень срочно надо

Добавьте комментарий:

Обсуждаем

Задача Задача с собеседования в Adobe:
не представился : [скрыто]
Чушь : [скрыто]
Чушь : [скрыто]
Задача Кратчайший путь к дороге:
Роман : [скрыто]
Гостевая книга:
EverettOxick : <a href=https://vk.com/med_ ooks_by>Медициснкие книги скачать</a>. Библиотека медицинско...
Так, по старой памяти заглянул :) : Евгений, чтобы увидеть комментарии, нужно ткнуть в ссылку "решение" под условием задачи. Н...
Задача Спички. Не стандартное мышление.:
Евгений : [скрыто]
Задача Если.. то..:
Шавкат : [скрыто]
Задача Что изображено 2?:
Димыч : [скрыто]
ZAUDIN : [скрыто]
Задача Площади:
;4;;4 : [скрыто]
Гостевая книга:
EverettOxick : <a href=https://online-kart .ru/>Блядями выссаный, засраный хуедав моржовый, пиздюк блошиный, ...
EverettOxick : <a href=https://online-kart .ru/>займы онлайн на карту без проверок москва</a>: п&...
EverettOxick : На нашем <a href=https://www.youtube com/@vicktop2881>yout be канале</a> Ёбан й в рыл...
EverettOxick : На нашем <a href=https://www.youtube com/@vicktop2881>yout be канале</a> сук ты тут с м...

Реклама

© 2009-201x Логические задачи

Задачи на логику и сообразительность

Поиск на сайте

Задачи

Данетки

Справочная

Реклама

задача: Людоеды и миссионеры на переправе

Ваши ответы на задачу

Обсуждаем

Реклама