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


+ -

решение

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

ответов: 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 пишет:

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

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

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