"Логические задачи" - это познавательно-развлекательный проект для непрокисших мозгов. Задачи на логику, нестандартное мышление. Не всегда самое очевидное решение - правильное. Но иногда всё оказывается проще, чем кажется на первый взгляд.

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




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

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

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





запомнить меня
Зарегистрироваться


Задачи



Данетки


Текущие:

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

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

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


Справочная



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


Реклама






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

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


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



Ответ





Решение задачи





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


ответов: 8

Асылбек 2012-09-29 14:09:32 пишет:
Я так понимаю М больше Л, а К меньше и М, и Л. Переправляем на тот берег К/2 миссионеров и K/2 людоедов, оставляем там людоедов, миссионеров забираем с собой, берем еще K/2 людоедов и переправляем на тот берег, оставляем там миссионеров, и забираем K/2 людоедов, таким образом мы переправили К представителей этого племени, причем мисс. и люд. поровну, в лодке К/2 людоедов, плывем за таким же кол-вом миссионеров, переправляем их на другой берег и опять с людоедами переплываем на исходный берег, на этот раз забрав K/2 людоедов, таким образом в лодке К представителей людоедов, переправив их и оставив половину плывем за миссионерами и так далее

Вася Пупкин 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 пишет:
ну очень срочно надо

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

Комментарий:

Пожалуйста, введите символы с картинки:
(подтверждение не требуется для зарегистрированных пользователей)



 





Обсуждаем

  Задача Секретный пароль:
Дмитрий : [скрыто]
Задача Кофе с молоком:
KoKos : [скрыто]
ivana2000 : [скрыто]
ivana2000 : [скрыто]
ivana2000 : [скрыто]
Гостевая книга:
Ganckasl : These enhanced sensors would prompt many more codes at a high straight as a replacement for take exc...
Ganckasl : Enquire of give imminent stressors such as kindergarten concerns, conflicts with parents, dating iss...
Задача Кофе с молоком:
не представился : [скрыто]
не представился : [скрыто]
Гостевая книга:
LarryDrent : Howdy! [url=http://trustnlineph rmacy.us/]best online pharmacy mexico[/url] very good web page
Sanuyemsl : Feeding disorders or nutriment rejection may occur in infants or children who arrange required prolo...
Sanuyemsl : Manufacture sure to explain what you are doing to the young man, especially in the vanguard the pinp...
Aschnutut : Atonic bladder leads to fastidious urinary retention, refractory urinary infec- tions, and even pers...
Задача магия умножения:
скажите откуда вы взяли эту задачу : [скрыто]
Гостевая книга:
HjalteSr : The trunk is aligned withtrunk/hip guides, straps, or pads. ThisMessage carried descending pathway s...



Реклама



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