Алгоритмические задачи.
На этом занятии мы будем учиться решать задачи на алгоритмы. В таких задачах в качестве ответа требуется придумать и написать алгоритм, то есть некоторую последовательность действий, приводящую к нужной цели. Часто такие задачи имеют несколько вариантов решения, то есть можно придумать несколько алгоритмов, приводящих к одному результату.
Рассмотрим некоторые типы алгоритмических задач:
- задачи на переливание жидкостей,
- задачи на измерение времени с помощью песочных часов,
- задачи на взвешивание сыпучих веществ,
- задачи на определение фальшивых монет с помощью чашечных весов,
- задачи на переправы.
1. Переливания.
В таких задачах есть несколько сосудов разной вместимости и требуется получить некоторый объём жидкости, переливая ее из одного сосуда в другой. В одних задачах, кроме того, есть бесконечный источник жидкости (река, кран и раковина, большая бочка), откуда можно набирать и куда можно выливать жидкость сколько угодно раз. В других задачах уже дано определенное количество жидкости (обычно это особенная жидкость — сок, молоко, варенье), и набирать или выливать ее нельзя, можно только переливать.
С жидкостью в сосудах можно проделывать следующие операции:
- набрать полный сосуд жидкости (если есть источник),
- вылить полностью жидкость из сосуда (если есть куда вылить),
- перелить из меньшего сосуды в больший (и тогда в большем сосуде останется место для доливания),
- перелить из большего сосуда в меньший (и тогда в большем сосуде останется часть жидкости).
При этом предполагается, что сосуды могут иметь изогнутую форму и не имеют шкалы с делениями. То есть нельзя получить, например, 1 литр воды, наполнив наполовину двухлитровую кастрюлю. Или нельзя получить 3 литра воды, вылив из полной четырёхлитровой кастрюли ровно четверть воды.
Задача 1.
У мамы есть две кастрюли — на 5 литров и на 3 литра. Как ей с помощью этих кастрюль налить из крана ровно 4 литра воды?
Решение.
Назовём 5-литровую кастрюлю большой (Б), а 3-литровую — маленькой (М).
Заметим, что мы можем получить 4 литра воды, если удастся вылить из большой кастрюли ровно 1 литр воды. Но просто в раковину отлить 1 литр мы не можем. Зато можем перелить в маленькую кастрюлю, если если в ней уже находится 2 литра воды. А 2 литра воды мы можем получить, если из полной большой кастрюли перельем воду в пустую маленькую.
Итак, нужно сделать так:
1. Наполнить из крана большую кастрюлю.
2. Перелить воду из большой кастрюли в маленькую. При этом в большой кастрюле останется 5-3=2 литра.
3. Вылить всю воду из маленькой кастрюли в раковину.
4. Перелить воду из большой кастрюли в маленькую. При этом в маленькой кастрюле окажется 2 литра воды.
5. Наполнить из крана большую кастрюлю.
6. Перелить из большой кастрюли в маленькую столько воды, сколько еще поместится в маленькую кастрюлю. А в маленькую поместится только 1 литр. При этом в большой кастрюле останется 5-1=4 литра.
7. Вылить из маленькой кастрюли всю воду (это необязательный шаг, так как необходимые 4 литра мы уже получили, и задача решена.
Ответ: см. алгоритм.
2. Измерение времени с помощью песочных часов.
Песочные часы — это простейший прибор для отсчёта промежутков времени, состоящий из двух прозрачных сосудов, соединённых узкой горловиной, один из которых частично заполнен песком. С помощью одних песочных часов можно отмерить только такой промежуток времени, за который весь песок пересыпается из верхнего сосуда в нижний. Нельзя отмерить половину этого промежутка и любую другую часть, так как невозможно определить, когда же пересыпалась половина или другая часть песка. Но если есть несколько часов, отмеряющих разные промежутки времени, то, используя их, можно отмерить и другие промежутки.
При решении задач с песочными часами мы можем делать такие действия:
- поставить часы (то есть перевернуть их так, что весь песок окажется в верхнем сосуде),
- перевернуть часы (то есть поменять местами верхний и нижний сосуды),
- засечь время (сделать какую-то отметку, что время пошло).
Задача 2.
Миша решил сварить макароны. Макароны нужно забросить в кастрюлю с кипящей водой и варить ровно 5 минут. У Миши есть двое песочных часов — на 4 минуты и на 3 минуты. Как с помощью них отмерить 5 минут?
Решение.
5 минут — это 4 минуты и еще 1 минута. 1 минуту можно отмерить, если одновременно поставить двое часов: в тот момент, когда закончится песок в часах на 3 минуты, в часах на 4 минуты песка останется еще на 1 минуту.
Итак, Мише нужно действовать так:
1. Налить в кастрюлю воду и довести ее до кипения.
2. Поставить одновременно и те, и другие часы.
3. Когда в маленьких часах песок закончится, засыпать в кастрюлю макароны (начать отсчет времени).
4. Когда в больших часах песок закончится (пройдет 1 минута с начала отсчета), перевернуть их.
5. Когда в больших часах песок закончится (пройдёт 1+4=5 минут с начала отсчета), откинуть макароны на дуршлаг.
Ответ: см. алгоритм.
3. Взвешивание сыпучих веществ.
Задача состоит в том, чтобы, используя чашечные весы без гирь, отмерить некоторое количество груза. В таких задачах в качестве грузов используются сыпучие вещества (песок, крупа, мука). Подразумевается, что сыпучий груз можно разделить пополам, уравняв его части на чашах весов.
Задача 3.
У Кощея Бессмертного есть мешок с 8 кг золотого песка. Как ему, используя чашечные весы без гирь, отсыпать 6 кг песка в сундук?
Решение.
Кощею нужно действовать так:
1. Разделить песок из мешка пополам. Для этого сначала нужно высыпать часть песка на одну чашу весов, часть песка — на другую чашу. Если весы не в равновесии, то с более тяжелой чаши перекладывать понемногу (можно по 1 песчинке) на более лёгкую до тех пор, пока весы не придут в равновесие. Получится 2 кучи по 4 кг песка.
2. Одну из куч 4 кг высыпать в сундук.
3. Вторую кучу 4 кг разделить пополам. Получится 2 кучи по 2 кг песка.
4. Одну из куч 2 кг высыпать в сундук. Всего в сундуке будет 4+2=6 кг песка.
5. Вторую кучу 2 кг высыпать обратно в мешок.
Ответ: см. алгоритм.
4. Поиск фальшивых монет.
Это задачи о поиске фальшивых монет среди настоящих. Известно, что все монеты одинаковы по виду и на ощупь, но фальшивые чуть легче или чуть тяжелее настоящих. Разница в весе настолько мала, что определить ее можно только с помощью весов. В таких задачах требуется придумать алгоритм взвешиваний монет, чтобы найти фальшивые монеты как можно быстрее, за наименьшее число взвешиваний.
Задача 4.
Старик Хоттабыч наколдовал 3 монеты. Правда, настоящими оказались только две из них, а одна — фальшивая. Фальшивая монета легче настоящей, но никак не отличается от нее по внешнему виду. Как за одно взвешивание на чашечных весах без гирь найти фальшивую монету?
Решение.
Если бы Хоттабыч наколдовал только 2 монеты, то задача решалась бы очень легко: на одну чашу весов нужно было бы положить одну монету, на вторую — другую монету. На той чаше, которая перевесила, лежала бы настоящая монета, а на той, которая оказалась легче, — фальшивая.
Но в этой задаче 3 монеты. На первый взгляд кажется, что результатом одного взвешивания мы ничего не добьемся.
Если мы положим на одну чашу весов 2 монеты, а на другую — 1 монету, то это взвешивание не даст никакой информации о том, на какой чаше лежит фальшивая монета. Ведь две монеты в любом случае перевесят одну, будь она хоть фальшивая, хоть настоящая.
Значит, нужно на чаши весов класть одинаковое количество монет. Поэтому положим на чаши весов по одной монете, а третью отложим в сторону, она во взвешивании участвовать не будет. Сможем ли мы за одно это взвешивание определить, какая из монет фальшивая? Хорошо, если повезет, и фальшивую монету мы положим на одну из чаш весов. Тогда другая чаша перевесит, и более легкая монета будет искомой фальшивой. А если весы окажутся в равновесии? Тогда это значит, что обе монеты на весах одного веса, и это могут быть только настоящие монеты (так как фальшивая только одна). А фальшивая монета — та, которую мы отложили в сторону.
Итак, нужно действовать так.
Положить на чаши весов по 1 монете. Если одна из монет перевесила, то вторая монета на весах — фальшивая. Если весы находятся в равновесии, то фальшивая монета — та, которая во взвешивании не участвовала.
Ответ: см. алгоритм.
5. Переправы.
В этих задачах обычно требуется придумать алгоритм переправки людей, животных, грузов через реку или тоннель с соблюдением некоторых условий. Проблема заключается в том, что средство передвижения не вмещает всех пассажиров или все грузы одновременно, а оставлять некоторых пассажиров или некоторые грузы одних без присмотра нельзя по каким-либо причинам.
Самой известной задачей на переправы является задача про волка, козу и капусту. На её примере мы разберем решение и запись подобных задач.
Задача 5.
Мужику нужно перевезти через реку волка, козу и капусту. Лодка двухместная, в ней может поместиться только мужик и еще что-то одно: волк, коза или капуста. Грести может только мужик. Если оставить волка с козой без присмотра, то волк съест козу, а если оставить козу с капустой, то коза съест капусту. Как мужику перевезти свой груз?
Решение.
Если первым переправлять через реку волка, то оставленная без присмотра коза съест капусту. Если первую переправлять капусту, то оставленный без присмотра волк съест козу.
Значит, мужику нужно действовать так:
1. Переправить на другой берег козу, высадить ее там и вернуться обратно.
2. Взять капусту и отвезти её на другой берег. На другом берегу выложить капусту, посадить в лодку козу и вернуться обратно.
3. На этом берегу высадить козу, взять волка и отвезти его на другой берег. Высадить там волка и вернуться обратно.
4. На этом берегу забрать козу и отвезти её на другой берег. Таким образом, мужик переправит весь свой груз.
Алгоритм можно записать более, кратко, если ввести обозначения.
Обозначим мужика, волка, козу и капусту буквами М, В, К и к соответственно.
Решение задачи можно записать так:
МК туда, М обратно, Мк туда, МК обратно, МВ туда, М обратно, МК туда.
Ответ: см. алгоритм.
Уважаемые родители! Формат этого занятия предполагает ввод ответов в виде текстов. Пожалуйста, помогите вашим детям, введите их решения в поля ответов.