04. Табличная форма записи плана действий. Задачи о переливаниях

Введение. Ханойская башня

Сегодня я хочу начать наш урок с легенды о Великом храме в городе Бенарес.

Этот собор отмечает середину мира (в мифологии — центральную часть Вселенной), а под ним находится бронзовый диск, на котором укреплены 3 алмазных стержня в один локоть высотой и толщиной с пчелу (подобным образом до появления измерительных приборов и универсальных единиц измерения измеряли различные величины).

От локтя до скорости света

С незапамятных времён человеку в быту нужно было мера: нужно было отмерить определённое количество муки для хлеба, определённое расстояние от одного саженца до другого, удобную длину лопаты и так далее. Выходом из ситуации стало измерения величин при помощи подручных средств.

Поговорим о длине. Удобнее всего измерять её тем, что всегда есть под рукой, ведь носить с собой какие-то приборы неудобно. А что у нас всегда с собой? Вообще говоря, это мы сами. Действительно, человек придумал меры длины, соответствующие, например, расстоянию от локтя до конца среднего пальца. Называется эта мера локоть.

Расстояния от мизинца одной руки до мизинца другой, при вытянутых в сторону руках, — это сажень.

Длинна ступни — это фут.

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

Такие меры и измерения величины неточны. Поэтому решено было привязать меры к чему-нибудь универсальному, сначала к физическим предметам или вещам. Например, килограммом считали массу цилиндра определённых размеров из специального сплава.

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

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

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

Как только все 64 диска будут переложены со стержня, на который Брахма положил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль, и под громовые раскаты погибнет мир.

При этом важно, чтобы соблюдались некоторые правила, например:

• снять можно только один диск за один раз и при этом обязательно зафиксировать его на каком-то стержне;

• на меньший диск нельзя положить больший.

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

Если вы успешно справились, добавьте на первом этапе еще одно — четвертое. Посмотрите, как усложнилась задача и увеличилось количество операций.

А количество ходов-перекладываний, которые необходимо было совершить монахам, соблюдая все правила, можно вычислить. Это сделали математики, используя имеющийся в их распоряжении аппарат. Количество оказалось равным 18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, их работа продолжалась бы почти 585 миллиардов лет.

Конечно, ничего подобного в реальной жизни не происходило и происходить не могло, это только легенда, придуманная французским математиком Эдуардом Люка — создателем головоломки, но основана эта легенда на одной из самых популярных головоломок XIX века, которая называется «Ханойская башня».

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

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

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

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

Представление информации в форме таблиц

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

Давайте это утверждение проверим, разобрав 2 типа задач на переливания.

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

Первый тип задач — когда мы имеем очень много жидкости (например, в большой бочке, озере или водопроводе) и нам нужно наполнить некоторое количество сосудов. Важно, что воду можно переливать сколько угодно раз и при необходимости выливать её.

В то время как второй тип задач основан на том, что жидкости у нас строго определенное количество — столько, сколько налито в сосудах (например, 2 кувшина молока или 3 бочки меда).

Кроме того, необходимо помнить один важный принцип, который одинаково работает для любого типа таких задач: наливать жидкость в сосуды можно только полностью (т. е. нельзя налить ¾ кувшина или вылить из банки 60 % жидкости). Почему? — спросите вы. Ну хотя бы потому, что мы не знаем, какой формы наши сосуды, они могут быть несимметричны. А вдруг перед нами замысловатая древняя амфора? Да и, конечно, мало на каких сосудах есть шкала делений, чтобы точно отмерять нужное количество. (Такие задачи могут встретиться, например, в походе, а точность измерения может иметь важное или критическое значение — нужно приготовить еду или развести в нужном соотношении лекарство.)

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

Рассмотрим задачу.

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

Конечно, мы можем наливать воду в 5-литровую кастрюлю и опустошать её или наливать 3-литровую банку и опустошать её. Но есть еще один хитрый способ: если налить из 5-литровой кастрюли воду в банку, то в кастрюле останется 2 литра. То есть мы можем получить 2 литра воды.

Для удобства мы договорились отражать наши действия в таблице. С нее и начнём — выделим 2 столбца (в первом будем отмечать, сколько литров в кастрюле, а во втором — фиксировать количество воды в банке).

1. Итак, для начала наполним 3-литровую банку водой и перельем ее в кастрюлю. На этом этапе в кастрюле окажется 3 литра воды.

2. Наполним банку снова и выльем в кастрюлю столько, сколько в нее поместится (т. е. 2 литра). Тогда получим 5 литров воды в кастрюле и 1 литр воды в банке.

3. А теперь всю воду из кастрюли выльем. В банке по-прежнему 1 литр воды.

4. Его мы и перельем в опустошенную кастрюлю. Теперь в ней 1 литр, а банка пуста.

5. Ну и теперь мы наполним банку в последний раз и добавим в кастрюлю нужные три литра воды. Теперь в банке ничего нет, а в кастрюле ровно те нужные нам 4 литра воды!

Задача решена, и её решение наглядно представлено в виде таблицы.

Решение задачи методом математического бильярда

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

Мы не будем объяснять, почему этот метод работает, а просто разберём его применение.

В нашей задаче стороны параллелограмма должны иметь длины 3 единицы и 5 единиц. По горизонтали 0 количество воды в 5-литровом сосуде, а по вертикали — в
3-литровом.

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

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

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

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

Обратимся к другой задаче.

У туристов есть канистра с топливом объёмом 8 литров и банка в 3 литра. Чтобы облегчить рюкзаки, они хотят оставить ровно 2 литра, а остальное вылить. Как отмерить нужное количество?

Снова будем иллюстрировать решение таблицей. В первом столбце будем отмечать количество топлива в 3-литровой банке, а во втором — в 8-литровой канистре.

1. Из 8-литровой канистры наполним доверху 3-литровую банку. (Получим 5 литров в канистре и 3 литра в банке.)

2. Выльем топливо из банки. В канистре по-прежнему 5 литров топлива, а банка пустая.

3. Наполним снова трехлитровую банку. Теперь в 8-литровой канистре остается ровно 2 литра топлива.

Всего 3 хода нам потребовалось, чтобы решить эту задачу!

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

Рассмотрим новую задачу.

Из-за пандемии в школе запретили посещать столовую всем классам одновременно. Повара сварили 8 литров супа на все классы. Но 1-ый «Б» придёт на полчаса позже 1-го «А». Поварам нужно отмерить для раздачи 4 литра для 1-го «А», но у них есть только кастрюли объёмом 3 литра и 5 литров. Как им отмерить нужное количество супа, не пролив его при этом?

Итак, рассуждаем следующим образом.

1. Наполним 3-литровую кастрюлю супом, а затем перельём его в 5-литровую кастрюлю.

2. Снова наполним 3-литровую кастрюлю, а затем перельем его в 5-литровую, пока та не станет полной. В меньшей кастрюле у нас при этом останется 1 литр супа.

3. Перельём содержимое 5-литровой кастрюли обратно в кастрюлю, где у нас уже было 2 литра, а 1 литр из 3-литровой кастрюли перельем в большую.

4. Теперь наполним 3-литровую кастрюлю из большой кастрюли. Теперь в ней осталось ровно 4 литра!

Рассмотрим 2-й способ, взяв за основу ту же таблицу.

1. Наполним 5-литровую кастрюлю из большой кастрюли, после чего в ней останется 3 литра.

2. Перельем из 5-литровой кастрюли в 3-литровую 3 литра супа. В 5-литровой кастрюле останется 2 литра.

3. Опустошим меньшую кастрюлю, перелив её содержимое в большую кастрюлю.

4. А 2 литра из 5-литровой кастрюли перельём в 3-литровую.

5. Суп из большой кастрюли перельем в 5-литровую кастрюлю и из неё заполним 3-литровую кастрюлю (в которой уже налито 2 литра).

6. В результате переливаний в 5-литровой кастрюле останется 4 литра супа.

Мы рассмотрели, конечно, только один тип задач. Но на самом деле табличный способ имеет большое применение. И мы будем учиться работать с таблицами в течение всего школьного курса информатики.

Список литературы

1. Босова Л. Л., Босова А. Ю. Информатика. 5 класс: учебник. — М.: БИНОМ; Лаборатория знаний, 2019.

Дополнительные рекомендованные ссылки на ресурсы сети Интернет

1. Интернет-портал «yaklass.ru» (Источник)

Домашнее задание

1. Приведите пример ситуации из жизни, в котором необходимо составление плана действий.

2. Можно ли получить 2 литра воды за два переливания, если у нас есть два сосуда 5 литров и 4 литра?

3. В каком случае следует использовать табличную форму записи плана действий?

4. Босова Л. Л., Босова А. Ю. Информатика. 5 класс: учебник. — М.: БИНОМ; Лаборатория знаний, 2019. С. 90–93.