Меню

Задача переправа через реку информатика



Задачки на переправу через реку

Коза, волк и капуста

лодка

Крестьянин купил на базаре козу, кочан капусты и волка. По дороге домой надо было переправиться через реку. У крестьянина была маленькая лодка, в которую кроме него могла поместится только одна из его покупок.
Как ему переправить все товары через реку, если нельзя оставлять козу наедине с капустой и волка наедине с козой?

Людоеды и миссионеры

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

Семья

Отец, мать и двое детей – сын и дочь, должны переравиться через реку. Поблизости случился рыбак, который мог бы одолжить им свою лодку. Однако, в лодке могут поместится только один взрослый или двое детей.
Как семье переправиться через реку и вернуть рыбаку его лодку?

Люди и обезъяны

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

Боязнь темноты

Одной семье надо пройти на другую сторону длинного, узкого и очень тёмного тоннеля. Отец может пройти сквозь тоннель за 1 минуту, мать – за 2, сын – за 4 и дочь за 5 минут. У них есть один факел, которого хватит ровно на 12 минут. В тоннеле могут идти не больше двух человек с факелом.
Как всей семье перебраться на другую строну тоннеля, если все боятся темноты?

Переправа через реку – игра

Цель игры – переправить всех людей через реку соблюдая следующие правила:

  1. На пароме могут находится не более 2-х человек.
  2. Только взрослые (отец, мать и полицейский) могут упралять паромом.
  3. Отец не может находится вместе с девочками в отсутствии матери.
  4. Мать не может находится вместе с мальчиками в отсутствии отца.
  5. Вор не может находится вместе с любыми членами семьи в отсутствии полицейского.

Click кружок, чтобы начать игру.
Click персонаж, чтобы переправить его на паром.
Click красную ручку, чтобы отправить паром на другую сторону.

Прыгающие лягушки – игра

Поменяйте местами лягушек. Три лягушки слева должны переместиться на 3 камня справа, а три лягушки справа – на 3 камня слева.

Каждая лягушка может прыгать только вперёд на соседний камень, если он пустует, или на пустующий камень позади соседней лягушки.
Click «REINICIAR», чтобы начать.

Цветы

Сколько у меня цветов, если все из них, за исключением двух, розы; а также все из них, за исключением двух, тюльпаны; помимо этого, все из них, за исключением двух, маргаритки?

Вычитание

Сколько раз можно вычесть число 2 из числа 32?

Парикмахерские

Парикмахерские

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

Убийство в пустыне

А, B и С переходили через пустыню. А задумал убить С, подлил ночью в его воду яда и уехал от каравана. В тоже хотел убить С. Не зная, что вода уже отравлена, той же ночью он проделал дыру в бурдюке с водой С и уехал от каравана. С остался один без воды и через несколько дней умер от жажды.
Кто является убийцей, А или В?

Старший близнец

В один прекрасный день у Керри был день рождения. А через два дня день рождения был у её брата-близнеца Терри. Как так получилось?
Эта загадка заняла первое место на конкурсе «Как так?» в журнале «Гэймз магазин» (“Games Magazine”) в 1992 году.

Источник

Комплексы задач разного уровня сложности для формирования алгоритмического стиля мышления школьников

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

Знакомство с понятием алгоритма обычно начинается с задачи о Перевозе (задача Алкуина) [1, 4, 5]. Далее решается ряд классических алгоритмических этюдов, в том числе о переливаниях.

В данной работе представлены комплексы задач, составленные на основе задач для исполнителей Перевозчик и Переливашка. Они представляют из себя цепочки задач от простейших до трудных. В эти комплексы вошли задачи из различных сборников [2, 3, 6], а также авторские. Наиболее полно решения задач приведены в [8, 9].

Комплекс задач о переправах содержит более 60 задач о перевозе, которые дополнены 22 задачами, основанными на тех же алгоритмах решения, но имеющими оригинальные сюжеты (как сказочные, так и современные). Задачи на переправы разделены на несколько групп по возрастанию сложности.

Рассматривается разное количество героев, участвующих в переправе, и различная вместимость лодки. При этом условная сложность отдельной задачи внутри той или иной группы оценивается количеством действий, необходимых для решения задачи. Итоги для каждой группы задач представлены в виде таблиц, в которые внесены информация о количестве переправляющихся, вместимости лодки, наличии острова, количестве необходимых переправ [9].

Переправы без условий. Переправляющиеся находятся на одном берегу.

Начальный этап, стандартные формулировки задач.

Двухместная лодка: перевоз двух, трех, четырех героев.

Трехместная лодка: перевоз трех, четырех, пятерых, шестерых героев.

1. Три поросенка, три братца пошли погулять. На их пути встретилась глубокая канава. Через нее была положена доска, по ней можно переправляться вдвоем. Однако после переправы двоих поросят останется один поросенок, которому придется переходить мостик в одиночку. А Нуф-Нуф и Ниф-Ниф категорично отказались идти по одному – они боялись потерять равновесие и упасть в канаву. Наф-Наф оказался смелее и сказал, что он всем поможет. Что придумал Наф-Наф?
2. Утке Крякуше подложили куриные яйца, и она высидела пятерых утят и четырех цыплят. Однажды все семейство отправилось гулять на речку. На другом берегу зеленела аппетитная трава, а в воде у другого берега было большое количество ряски. Утята с радостью бросились в воду и переплыли речку. Мама утка умела перевозить на спине двоих цыплят. Как она перевезла всех четверых?
3. В другой раз цыплята и утята играли во дворе в искусственном водоеме. Цыплята нашли маленькую игрушечную лодочку и решили повторить переправу через речку без мамы утки. Цыпленок Командир сказал, что он будет Крякушей и всех цыплят перевезет, только не сам, как мама, а с помощью двухместной лодочки. Сколько раз ему пришлось переплывать с берега на берег?
4. Семеро гномов возвращались домой. И вдруг дорогу перегородила огромная лужа. Она была не очень широкой, но очень длинной, не было видно ее конца ни слева, ни справа. Гномы увидели кусок коры и быстро соорудили подобие лодочки. В ней могло поместиться трое. Как быстрее всего можно им переправиться на другой берег?

Переправы без условий. Переправляющиеся находятся на разных берегах.

Начальный этап, стандартные формулировки задач.

Переезжают три героя. На первом берегу два героя, на втором – один.

Переезжают пять героев. На первом берегу три героя, на втором – два.

Переезжают семь героев. На первом берегу четыре героя, на втором – три.

5. Ежик нашел в лесу грибы и решил отнести их белке. Белка заготовила для ежика на угощение лесные яблоки. На спине у ежа помещается один грибок или одно яблоко. Если грибов 2 (3, 4) и яблок 2 (3, 4), то сколько раз будет ходить ежик к белке и обратно?
6. Дорога из деревни Отмичи в деревню Кокошки пересекает реку Тьму (названия можно поменять на местные). Обычно речку переходили вброд, а в один год лето было особенно дождливым и для переправы приспособили одноместную лодку. Как-то раз к реке подошли 3(4) человек с первого берега и 2(3) со второго. Можно ли всем переправиться? За сколько переездов состоится переправа пешеходов?
7. Во дворе играли четверо детей. К ним присоединился пятый. У него был велосипед (самокат). Всем очень хотелось покататься на нем. Дети заспорили и никак не могли разобраться, кто поедет раньше. Тут подошла мама одного мальчика и организовала игру. Дети разбились на две группы и встали на расстоянии. Группам надо поменяться местами с помощью велосипеда (самоката). Игра повторяется несколько раз на скорость и определяется рекордное (самое короткое) время. Как могли разделиться на группы дети, у какой группы был вначале велосипед (самокат) и за сколько переездов игра заканчивается?

Начальный этап, стандартные формулировки задач.

Переезжает четыре человека. На первом берегу три героя, на втором – один.

Переезжает четыре человека. На первом берегу один герой, на втором – три.

Переезжает пять человек. На первом берегу четыре героя, на втором – один.

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

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

Переезжает пять человек. На первом берегу один герой, на втором – четыре.

8. В зимние каникулы ребята из соседних деревень отправились в гости к бабушкам. В деревне Отмичи гостит трое ребят, а в деревне Кокошки – один. Но в последний день снегу выпало так много, что вернуться домой можно было только на санях (снегоходе). Сани (снегоход) находятся в Отмичах. Управляет ими взрослый, а еще уместиться может только двое детей. За сколько поездок все ребята вернутся домой?
9. Как изменится решение задачи, если в Отмичах гостил один, а в Кокошках трое ребят?
10. Муравей перетаскивает зернышки из одного домика в другой. Одновременно он может нести два зернышка. В первом домике лежит два (одно) зернышка, а во втором – три (четыре). За сколько переходов он выполнит свою работу?

Начальный этап, стандартные формулировки задач.

Переезжает пять человек. На первом берегу четыре героя, на втором – один.

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

11. В конце учебного года необходимо сдать старые учебники в школьную библиотеку и получить новые. Эта работа была поручена пяти ученикам. Один ученик может одновременно взять три комплекта. Если в классе 30 учеников, то за сколько походов в библиотеку управятся дети?
12. В лифт вмещается три человека. Лифт имеет особенность: он управляется только из кабины и перемещается только между двумя этажами: первым и последним. На первом этаже находится 4 человека, которым надо подняться на последний этаж, а на последнем 1, который ждет спуска. За сколько поездок все люди смогут переместиться? Как изменится решение, если внизу находится 1 человек, а вверху 4? Начальное положение лифта на первом этаже.
13. На острове устроили лагерь для туристов. Наступил конец одной смены и начало другой. В распоряжении лагеря имеется трехместная лодка. Каждая смена состояла из 9 (12, 15, 18) туристов. Как быстрее всего вывезти одних туристов с острова, а других перевезти на остров?

Переправы с условиями. Условия на вместимость лодки.

Читайте также:  Долгопрудный какая река протекает

Начальный этап, стандартные формулировки задач.

Папа с двумя сыновьями отправился в поход. На их пути встретилась река. У берега – плот. Он выдерживает на воде только папу или двух сыновей. Как переправиться на другой берег папе и сыновьям?[6]

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

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

14. Два (три) спортсмена-байдарочника подошли к переправе, около которой они увидели лодку и двух мальчиков. В лодке может плыть один взрослый или два мальчика. За сколько переездов спортсмены переправятся на другой берег?
15. Спортсмены-байдарочники (из предыдущей задачи) хорошо плавают, поэтому часть из них решила речку переплыть самостоятельно, без лодки. Скорость спортсмена в 2 (3, 4) раза меньше скорости лодки. Скорость лодки одинакова, кто бы в ней не плыл. Как организовать самую быструю переправу? Скольким спортсменам лучше переплыть реку и скольким имеет смысл плыть на лодке? При одинаковом времени переправы предпочтительнее максимальное количество перевезенных на лодке, т. е. оставшимся “сухими”.
16. Коза и семеро козлят пошли в лес за ягодами. На пути им пришлось перебираться на лодке через реку. Лодка вмещает либо одну козу, либо двух козлят. Если один переезд занимает 3 минуты, то сколько времени будет длиться переправа?
17. На городском туристическом слете во время соревнований устроили необычную переправу. Команде из 8 человек надо переплыть на другой берег реки. В их распоряжении имеется две лодки и четыре помощника. Лодка вмещает либо одного туриста либо двух помощников. Помогите туристам правильно (быстрее всего) переправиться на другой берег.

Переправы с условиями. Затрудненные переправы. Возможно наличие острова.

Начальный этап, стандартные формулировки задач.

Задача Алкуина относится к данному разряду задач. Более простой по сравнению с этой задачей является задача о разбойниках [6].

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

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

Переправа трех разбойников и трех путешественников с одного берега.

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

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

18. Троих пленников отправили на остров. На берегу за островом следят трое охранников. Пленникам пообещали, что они будут свободны, если сумеют с помощью двухместной лодки организовать переправу троих охранников на остров, а сами окажутся на берегу. При этом в любой момент времени количество охранников не должно быть больше количества пленников. Лодка находится у охранников. Как переправиться пленникам? Какие действия недопустимы для освобождения пленников?
19. Три кошки и три собаки ищут переправу через реку. Они одновременно увидели на берегу – плот, но он вмещает только двоих. Как только на берегу собак будет больше, чем кошек, начнется драка. Как им всем переправиться без проблем?
20. Внучка, Жучка, Мурка и мышка Торопыжка торопятся к дедушке, чтобы помочь ему вытащить репку. Идут они, а перед ними река. На берегу лодка. Когда внучка находится рядом со своими подопечными — никто не ссорится. Без внучки и Жучки Мурка норовит Тропыжку поймать, а без внучки и мышки Жучка за Муркой гоняется. Если же внучка всех троих оставит – беда, бегают друг за другом и норовят подраться. Помогите всем перебраться на другой берег. Лодка вмещает двоих. Переправа должна быть мирной!

Среди задач о затрудненных переправах часто приводятся задачи о рыцарях и оруженосцах.

Начальный этап, разбор стандартных задач.

Переправа двух рыцарей с оруженосцами. Лодка для переправы двухместная.

Переправа трех рыцарей с оруженосцами.

Задачи про переправу ревнивых жен с мужьями, про купцов со слугами, про девочек с папами [2, 3, 5].

Переправа четырех рыцарей со своими оруженосцами решается при наличии возможности высаживаться на промежуточном пункте – острове.

Задача о четырех рыцарях и оруженосцах решается также при наличии трехместной лодки и ее решение оказывается короче решения задачи о трех парах

Для желающих разобраться с большим количеством переезжающих и лодками большей вместимости предлагается обратиться к [2].

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

21. Три пирата, каждый со своим помощником хотят захватить клад на острове. У каждого пирата свой план поиска. Им надо переправиться с корабля на остров с помощью лодки. Лодка двухместная. Но пираты боятся оставлять своих помощников в присутствии других пиратов – вдруг помощники проговорятся о деталях поиска? Помощники друг с другом не общаются. Как им всем переправиться, чтобы каждый действовал по своему плану?

И еще одна задача, первоисточник которой пока остался не известным. Эту задачу предложили дети.

22. Бабушка, мама, папа и сын торопятся домой. Но время позднее, а они подошли к реке и должны переправиться по ветхому мостику. В темноте можно передвигаться только с фонариком. Мостик не выдерживает более двух человек. Фонарик можно передавать только из рук в руки. Папа переходит через речку за 1 минуту, мама за 2, сын за 5, а бабушка за 10. За какое минимальное время все они смогут переправиться?

Задачи для исполнителя Переливашка разделены на два типа.

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

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

Комплекс задач первого типа содержит более 80 задач на переливания (пересыпания) с различным уровнем сложности. Эти задачи формируются на основе предложенных 10 оригинальных сюжетных задач. Итоговая таблица показывает, какое количество жидкости можно получить за определенное количество переливаний (от 1 до 12) для каждой из 10 задач. Это позволяет учителю быстро подобрать задачу требуемой сложности.

Распределение задач по сложности (в зависимости от сложности – количества ходов – приведены объемы жидкости, которые можно получить путем переливаний с помощью трех сосудов заданного объема)

1. Две группы альпинистов готовятся к восхождению. Для приготовления еды они используют примусы, которые заправляют бензином. В альплагере имеется 10–литровая канистра бензина. Имеются еще пустые сосуды в 7 и 2 литров. Как разлить бензин в два сосуда по 5 литров в каждом?
2. Как разделить поровну между двумя семьями 12 литров хлебного кваса, находящегося в двенадцатилитровом сосуде, воспользовавшись для этого двумя пустыми сосудами: 8-литровым и 3–литровым? [1]
3. У Карлсона есть ведро варенья, оно вмещает 7 литров. У него есть 2 пустых ведерка – 4–литровое и 3–литровое. Помогите Карлсону отлить 1 литр варенья к чаю в меньшее (3–литровое) ведерко, оставив 6 литров в большом (7–литровом) ведре.
4. Летом Винни Пух сделал запас меда на зиму и решил разделить его пополам, чтобы съесть половину до Нового Года, а другую половину – после Нового года . Весь мед находится в ведре, которое вмещает 6 литров, у него есть 2 пустые банки – 5-литровая и 1–литровая. Может ли он разделить мед так, как задумал?
5. На другой год Винни Пух запасся 10 литрами меда. Под руками у него два ведра – 7–литровое и 4–литровое. Как ему разделить мед пополам?
6. (Пересыпашка) Разбойники раздобыли 10 унций (1 унция – примерно 30 см 3 ) золотого песка. У них имеется две пустые коробки, емкостью 6 и 4 унции. Как им разделить песок пополам? Если на одно пересыпание требуется 1 минута, то сколько времени они будут делить свою добычу?
7. Некто имеет полный бочонок сока емкостью 12 пинт (пинта – 0,57 литра) и хочет подарить половину своему другу. Но у него нет сосуда в 6 пинт, а есть два сосуда в 8 пинт и 5 пинт. Каким образом можно налить 6 пинт в сосуд емкостью 8 пинт? [1]
8. Белоснежка ждет в гости гномов. Зима выдалась морозной и снежной, и Белоснежка не знает наверняка, сколько гномов решатся отправиться в далекое путешествие в гости, однако знает, что их будет не более 12. В ее хозяйстве есть кастрюлька на 12 чашек, она наполнена водой, и две пустых – на 9 чашек и на 5. Можно ли приготовить кофе для любого количества гостей, если угощать каждого одной чашкой напитка?
9. Разрешима ли предыдущая задача, если в хозяйстве у Белоснежки имеются кастрюлька с водой на 12 чашек и пустые кастрюльки на 9 и 7 чашек?
10. Для путешествия по морю необходим запас пресной воды. В плавании вода расходуется со скоростью 1 бочка в сутки. В некоторый момент времени запас воды на берегу составлял 8 бочек, и вода находилась в баке, заполненном до краев. На яхте имеется такой же бак, объемом 8 бочек, но пустой. На сколько дней можно планировать путешествие, если с собой нельзя брать лишнюю воду, а в распоряжении имеется еще две пустых емкости объемом 3 и 6 бочек и их можно использовать для переливания воды?

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

Читайте также:  Какие реки в калининградском регионе

Комплекс задач второго типа содержит 7 задач.

1. Для разведения картофельного пюре быстрого приготовления “Зеленый великан” требуется 1 л воды. Как, имея два сосуда емкостью 5 и 9 литров, налить 1 литр воды из водопроводного крана?
2. Для марш-броска по пустыне путешественнику необходимо иметь 4 литра воды. Больше он взять не может. На базе, где имеется источник воды, выдают только 5-литровые фляги, а также имеются 3-литровые банки. Как с помощью одной фляги и одной банки набрать 4 литра во флягу?
3. В походе приготовили ведро компота. Как, имея банки, вмещающие 500г и 900г воды, отливать компот порциями по 300 г?
4. Нефтяники пробурили скважину нефти. Необходимо доставить в лабораторию на экспертизу 6 литров нефти. В распоряжении имеется 9– литровый и 4– литровый сосуды. Как с помощью этих сосудов набрать 6 литров?
5. Как решить предыдущую задачу, если на экспертизу необходимо доставить 5 литров нефти, а емкости сосудов составляют соответственно 7 литров и 3 литра?
6. Как с помощью двух бидонов емкостью 17 литров и 5 литров отлить из молочной цистерны 13 литров молока? [6]
7. Современный вариант старинной задачи [7].

К продавцу, стоящему у бочки с квасом, подходят два веселых приятеля и просят налить им по литру кваса каждому. Продавец замечает, что у него есть лишь две емкости в 3 л и 5 л, и поэтому он не может выполнить их просьбу. Приятели продолжают настаивать и дают продавцу 100 рублей (сумма зависит от финансово-экономической ситуации в стране и соответственно варьируется) с одним условием, что они получат свои порции одновременно. После некоторого размышления продавец сумел это сделать. Каким образом?

Приведенные комплексы задач позволяют:

1. Провести пропедевтику циклических, условных структур, метода нисходящего проектирования.
2. Обеспечить индивидуальный подход к ученикам разной степени подготовленности.
3. Использовать эти задачи для домашних, самостоятельных работ и внеурочных занятий.
4. Продолжить формирование комплексов собственными задачами.
5. Включить учащихся в процесс конструирования задач.

  1. Звонкин А.К., Кулаков А.Г., Ландо С.К., Семенов А.Л., Шень А.Х. Алгоритмика – М.: Дрофа, 1997
  2. Доморяд А.П. Математические игры и развлечения – М.: ГИФМЛ, 1961
  3. Игнатьев Е.И. В царстве смекалки – М.: Наука, ФизМатЛит, 1987
  4. Первин Ю.А. Алгоритмические этюды, тетрадь № 2 – М.: АО КУДИЦ, 1993
  5. Первин Ю.А. Информатика в школе и дома – СПб.: БХВ, 2003
  6. Русанов В.Н. Математические олимпиады для младших школьников – М.: Просвещение, 1990
  7. Шарыгин И.Ф. Математический винегрет. – М.: Издание агентства “Орион”, 1991
  8. Шумилина Н.Д. Задачи для “шустриков” и “мямликов” //3-я научно-методическая телеконференция “Информационные технологии в общеобразовательной школе” (25.11.2002 – 31.03.2003 г.) – Новосибирск, НООС
  9. Шумилина Н.Д. Переправа, переправа (Задачи разного уровня сложности)//Информатика в школе. 2003. №6

Источник

Задачи типа: «Переправы», «Фальшивый объект», «Переливания»

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

Источник

Основы алгоритмики. Разбор задач «Переправы и переезды».

Содержимое публикации

Переправы и разъезды

ПЕРЕПРАВЫ

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

Задач, в которых речь идет о переправах, очень много. Приведем два известных сюжета.

ПУТНИКИ И ДВУХМЕСТНАЯ ЛОДКА

Путник подошел к реке, по которой на лодке катались двое мальчиков. Как ему переправиться на другой берег и вернуть лодку детям, если лодка вмещает либо только одного взрослого, либо двоих детей? А как быть, если путников двое? Трое? Очень много?

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

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

ВОЛК, КОЗА И КАПУСТА

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

Сперва крестьянину придется перевезти козу (если взять волка, то коза съест капусту, а если взять капусту, то волк съест козу). Затем он оставляет козу пастись на противоположном берегу и возвращается к волку и капусте. Теперь крестьянин может забрать, например, волка и перевезти его на противоположный берег. Осталось вернуться за капустой, но нельзя же оставить волка наедине с козой! Поэтому козу придется забрать с собой обратно на исходный берег. Далее крестьянин оставляет ее еще немного погулять и перевозит капусту. А затем возвращается за козой.

Канатная дорога

К кабинке канатной дороги на гору подошли четверо с весами 50, 75, 75 и 100 кг. Смотрителя нет, а в автоматическом режиме кабинка ходит туда-сюда только с грузом от 110 до 260 кг (в частности, пустой не ходит), при условии, что пассажиров можно рассадить на две скамьи так, чтобы веса на скамьях отличались не более, чем на 30 кг. За какое наименьшее количество переездов они все смогут подняться на гору? (Переезд – движение кабинки вверх или вниз).

За какое наименьшее количество переездов они все смогут подняться на гору?

Конец формы

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

Всех перевезти за одну поездку не удастся: 50+75+75+100>260. Ехать в первую поездку только двоим бессмысленно — им же придется и вернуться. Следовательно, в первый раз едут трое, и это люди весом 50 кг, 75 кг и 100 кг. Затем можно, например, спуститься тем, кто весит 50 кг и 75 кг. Затем вверх поднимаются оба весящие 75 кг. Вниз спускаются весящие 75 кг и 100 кг. И, наконец, вверх поднимаются люди весом 50 кг, 75 кг и 100 кг. Итого 5 переездов.

Есть еще второй (аналогичный) вариант, когда во второй поездке вниз спускаются те, кто весит 75 кг и 100 кг.

Горная река

К бурной горной реке подошли трое путников, первый весом 50 кг, второй весом 45 кг, а сколько весит третий – точно он не помнит, но где-то от 70 до 80 кг. Около берега стоит старая лодка, на которой есть надпись “Больше 100 кг не выдержит!”. За какое наименьшее количество переправ путники смогут переправиться через реку?

За какое наименьшее количество переправ путники смогут переправиться через реку?

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

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

Атос, Портос, Арамис и Д’Артаньян сидели за круглым столом (именно в такой последовательности), заспорили, и каждый поссорился со своими двумя соседями. Чтобы ехать дальше, им надо переправиться через реку в двухместной лодке. Каждый из мушкетеров отказывается оставаться вдвоем на берегу или быть в лодке с тем, с кем он в ссоре. Как им переправиться за как можно меньшее количество переездов?

Ниже заглавными латинскими буквами обозначены возможные комбинации мушкетеров в лодке. Выведите в качестве ответа последовательность букв, соответствующую наискорейшей переправе. Например, последовательность AAEA соответствует тому, что сначала переправился один Д’Артаньян и затем вернулся обратно, после этого на лодке переехали Д’Артаньян и Арамис, Арамис остался на противоположном берегу, а Д’Артаньян вернулся назад к Портосу и Атосу.

Д’Артаньян
B. Атос
C. Арамис
D. Портос
E. Д’Артаньян и Арамис
F. Д’Артаньян и Атос
G. Д’Артаньян и Портос
H. Арамис и Атос
I. Арамис и Портос
J. Атос и Портос

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

Сначала переезжают мушкетеры, которые сидят напротив друг друга, то есть, либо Атос и Арамис, либо Д’Артаньян и Портос. Пусть это будут Атос и Арамис. Теперь один из них, например, Атос, остается на берегу, а второй (Арамис) возвращается обратно. Он остается на исходном берегу, а переправляется вторая пара мушкетеров, сидевших напротив (Д’Артаньян и Портос). Теперь Д’Артаньян и Портос и остаются на конечном берегу, а Атос возвращается за Арамисом. Получаем такую последовательность: HCGBH.

Еще три возможных варианта ответа: HBGCH, GAHDG, GDHAG.

Эльфы и гномы

Эльфы и гномы не любят друг друга, и если где-то одних оказывается по-крайней мере вдвое больше, чем других, они обязательно нападают. К левому берегу реки подошли 3 гнома, а к правому — 3 эльфа. Каждому нужно на противоположный берег. У левого берега есть двухместная лодка. Грести умеют один гном и один эльф.

За какое наименьшее количество переездов через реку им удастся переправиться без нападений?

Конец формы

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

Задача решается однозначно. Сначала обязательно переправляются два гнома (если поплывет один, эльфы на него нападут). Теперь на правом берегу 2 гнома и 3 эльфа. Если обратно поплывут два эльфа, гномы нападут на оставшегося эльфа. Если обратно поплывут гном и эльф, эльфы нападут на оставшегося гнома. Следовательно, обратно плывет один эльф (который умеет грести). Он забирает оставшегося гнома и перевозит его на правый берег. Совершены три поездки и теперь все на правом берегу.

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

Фонарик на мосту

Семья (папа, мама, сын и бабушка) ночью подошла к мосту, способному выдержать только двух человек одновременно. По мосту можно двигаться только с фонариком. Известно, что папа может перейти мост в одну сторону за минуту, мама – за три, сын – за шесть и бабушка – за десять минут. Если по мосту движутся двое, время перехода определяется более медленным из двоих. За какое наименьшее время они сумеют переправиться? (Фонарик у них один, кидать его нельзя, светить издали тоже нельзя.)

Если всех будет по очереди переводить папа, то получится слишком долго.

Поэтому поступим так: папа переведет маму (3 минуты) и вернется обратно (1 минута). Затем пойдут два самых медленных — сын и бабушка (10 минут), а обратно фонарик принесет мама (3 минуты). Затем перейдут мама и папа (3 минуты). Итого: 3 + 1 + 10 + 3 + 3 = 20 минут.

Источник