Логические игры загадки через реку должны переплыть. Задача про семью и лодку

Кружок 5 класса

Руководители Евгений Александрович Асташов и Ирина Сергеевна Засыпкина
2011/2012 учебный год

Занятие 8. Переправы

Основные задачи

Решение.

Сначала Р забирает N, выезжает направо и подаёт задним ходом далеко налево. Там он оставляет вагон N, затем выталкивает М в промежуток А, возвращается, цепляет N и выезжает направо. Далее Р (вместе с N) задним ходом подъезжает к М и цепляет его позади N. Теперь Р c прицепленными к нему M и N выезжает направо, а затем задним ходом далеко налево. Там он оставляет вагон М и едет снова направо. Задним ходом Р заезжает в промежуток А и оставляет там вагон N. Затем он возвращается за вагоном М, уезжает с ним далеко направо, задним ходом подаёт на правую ветку, там оставляет вагон M, а сам уезжает на левую ветку и вытаскивает на неё из промежутка А вагон N. А сам возвращается на исходную позицию.

Совет. Чтобы понять это решение, нужно последовательно нарисовать все происходящее на картинках (каждую ситуацию нужно рисовать на отдельной картинке!). Если же вам (как и автору этого текста) лень рисовать столько картинок, нарисуйте на бумаге рельсы и катайте по ним машинки или ластики. Или используйте игрушечную железную дорогу (если она у вас есть).

На одной стороне реки находятся три человека и три льва. Все они должны оказаться на другом берегу реки. Есть лишь одна лодка, в которой могут поместиться лишь два живых существа одновременно (человека или льва). Вы не можете оставлять на том или другом берегу реки больше львов, чем людей, так как в этом случае животные съедят людей, оставшихся в меньшинстве. Как вы переправите всех через реку?

Решение

Есть пять возможных вариантов первой поездки: один человек, один лев, человек и лев, два человека, два льва.

Так как львы не могут грести, а лодка сама не поплывет, значит, это исключает варианты с одним и двумя львами. Один и два человека тоже исключается, так как на одном берегу львов станет больше. Поэтому для первой поездки остается только один вариант: в лодке окажутся человек и лев.

Они переправляются на дальний берег.

Но лодка сама вернуться не может. Из этого следует, что человек возвращается вместе с лодкой.

Рассмотрим варианты следующей поездки. Отправить двух людей мы не можем, иначе на берегу останется один человек и два льва. Поэтому единственным вариантом являются человек и лев. Человек отвозит льва на другой берег и тут же возвращается обратно. Поскольку в противном случае он останется на берегу с двумя львами.

После этих двух поездок на дальнем берегу оказываются два льва, а на ближайшем берегу останутся три человека и один лев.

В следующей поездке у нас появляется возможность выбора. Мы можем отправить двух людей или человека вместе со львом. Если мы отправим человека и льва, то на дальнем берегу окажутся три льва, и безопасно перевести остальных людей уже не получится. Поэтому данный вариант отпадает.

Вместо этого отправляем на другой берег двух людей, поскольку они по численности не уступают львам.

Но лодку надо вернуть обратно. Перевозить одного человека нельзя, поскольку на дальнем берегу останется человек и два льва. Поэтому обратно возвращаются человек и лев.

Теперь единственным разумным и безопасным вариантом является отправка двух человек на дальний берег.

Отправим обратно только одного человека. Он заберет льва (заманить его в лодку можно куском мяса) и вернется обратно.

Я считаю, вы не правы по поводу задачи. Напротив, это бы показало как вы умеете моделировать. Такого скилла очень не хватает среди разработчиков, порой уделяется слишком много внимания инфраструктуре (=== инструментам), не утруждая себя такими вещами, как выделение «чистой» модели, без всякого инфраструктурного говна. Нейминг, выделение наиболее подходящих понятий из предметной области - это очень важные скиллы, если человек обладает таковыми, то с ним приятнее работать. Проще находить проблемы/противоречия в бизнес-логике, проще понимать эти бизнес-требования, модифицировать их и т.д.

В этой лабе прежде всего стоит еще раз вернуться к самой задаче: обобщить её решение вплоть до создания блок-схемы на уровне N детей и M взрослых (по-моему, рыбак в данной задаче ничем от других взрослых не отличается), найти ограничения (например, минимум нужно 2 ребенка, если я правильно понял), а потом уже заняться моделированием.

Мне вспомнилась задача с одного из CTF, где нужно было что-то похожее (по части получения списка действий): имея несколько кувшинов разных объемов, получить определенное количество галлонов воды, чтобы открылась дверь, используя фиксированный набор команд а-ля «взять кувшин», «наполнить», «перелить» и т.д. Если не принимать во внимание, что это был CTF, то на ООП такое решение на порядок доступнее и гибче. Никаких переборов, нужен был алгоритм со минимальным количеством шагов. Если такое сделать в виде лабы, то, мне кажется, в этом что-то есть.

Public function converse(){ for($i=$this->numOfChildren; $i>0; $i--){ $arr[$i] = $i; $arr_rev = array_reverse($arr); echo "

";
 print_r ($arr_rev);
 echo "

Оно выдавало два массива вместо одного.
Если бы я этот пункт правильно реализовал, то мне бы оставалось создать функцию, в которой через цикл прогнать переменные(элементы массива) с одного берега на другой, меняя им флаг, если бы у всех флаг стал 1, то задача была решена.
Именно про то, как это реализовать я спрашивал.
Спасибо за то, что вы мне посоветовали дальше изучать ооп, я этим и займусь. Как говорится поспешишь - людей насмешишь, поэтому отправил работодателю письмо с тем, что у меня имелось и со словами "спасибо за предложенную работу, я буду учиться, а после уже буду пробывать устраиваться еще раз".

§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 четверти»:;;;;;;

Сможете ли вы разгадать сегодняшнюю загадку?

Двое взрослых и двое детей хотят переправиться через реку.

Они смастерили плот, но он может выдержать либо одного взрослого, либо пару детей.

Сколько переправ потребуется, чтобы всех перевезти на другой берег?

Ответ

Плот необходимо переправить как минимум девять раз.

Возможно, ваше решение будет отличаться, но вот один из вариантов. Мы предположим, что все находятся на ближнем берегу и хотят переправиться на дальний.

Если взрослый переправится на дальний берег, то там уже должен находиться ребенок, который переправит плот назад (если только это не сделает взрослый, но в этом случае поездка будет потрачена впустую).

Решение будет возможно лишь в том случае, если в первых двух путешествиях на плоту будут только дети. Оба ребенка переправляются на другой берег, один из них остается там, а второй возвращает плот.

В третьем путешествии на другую сторону переправляется взрослый, а в четвертом ожидавший на другом берегу ребенок возвращается назад с плотом. Итак, после четырех поездок один взрослый находится на другом берегу, все остальные - на этом.

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