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