Некоторые считают, что программирование появилось с изобретением компьютеров. Это не так. Умение работать с современными компьютерами и современным программным обеспечением — важное, но не главное умение программиста. Более важна способность к алгоритмическому мышлению, иногда ещё называемому вычислительным или цифровым. Эта способность означает уметь и быть готовым в любой ситуации размышлять, планировать свои действия, предусматривать различные обстоятельства, возникающие при выполнении планов, и поступать соответственно с ними. Все эти умения и способности понадобились людям задолго до того, как был изготовлен первый компьютер. Само слово «алгоритм» происходит от имени средневекового учёного Мухаммеда ибн Мусы аль-Хорезми (787—850), жившего в Средней Азии. В XIII веке, когда труды аль-Хорезми были переведены с арабского языка на латынь, его имя записали так: Algorithmus. Но, конечно, люди изобретали алгоритмы и до Мухаммеда ибн Мусы. Например, все математики знают так называемый алгоритм Евклида, а Евклид жил больше двух тысяч лет назад!

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

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

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

После выполнения первой команды в сосуде B будет 3 литра воды, а на втором шаге Водолей переливает 2 литра воды из B в пустой сосуд A, после чего в B остается 1 литр воды. И после выливания воды из A остается один непустой сосуд, в котором ровно один литр воды. Казалось бы, последнюю команду Водолею можно было бы и не давать. Но программисты, разработчики игры «Водолей», предложили уточнить, дополнить условие достижения успеха в игре. А именно, они предложили потребовать, чтобы в одном сосуде «Водолей» получил нужное количество воды, а другие сосуды сделал пустыми. Это требование упрощает проверку правильности решения задачи и потому введено в игру «Водолей» как обязательное. Профессиональные программисты часто предлагают заказчикам уточнить условие решаемой задачи, и заказчики часто с такими предложениями соглашаются. Именно это и случилось при разработке игры «Водолей» по заказу авторов учебника.

Прежде всего, мы предполагаем, что в распоряжении Водолея, кроме сосудов, есть неограниченный резервуар с водой. Из этого резервуара Водолей будет брать нужную ему воду. Дальше нужно заметить, что слово Водолей отсылает не к конкретному исполнителю, а к целому классу однотипных исполнителей с похожими командами и правилами работы. Чтобы задать конкретного Водолея, нужно указать, сколькими сосудами он распоряжается и каков объём каждого из этих сосудов. У нас, как правило, будут Водолеи, распоряжающиеся двумя или тремя сосудами, и мы будем обозначать эти сосуды латинскими буквами A, B, C. В игре «Водолей» на каждом уровне игры (в каждом задании) речь идёт о конкретном Водолее, то есть задаются и вместимости сосудов, и их содержимое в начальный момент. Задаётся и цель данного уровня – количество литров воды, которое нужно отмерить. На рисунке показано, как объёмы сосудов и их содержимое изображаются на экране игры «Водолей».

Команды Водолея бывают трёх видов.

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

Команд такого вида столько же, сколько сосудов.

В компьютерной игре «Водолей» команды задаются и словами, и картинками. Эти картинки называются пиктограммами.

Вот пиктограмма команды наполни А

Сосуды A, B и C на экране раскрашены в жёлтый, голубой и зелёный цвета соответственно. Буквы A, B и C на пиктограммах изображаются на фоне треугольника соответствующего цвета. Даже если бы на этих цветных треугольниках не были написаны буквы, по цвету треугольника можно догадаться, какой сосуд будет наполняться по данной команде.

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

Вот как выглядят пиктограммы для команд второго вида:

Цель Водолея при выполнении команды второго вида — добиться того, чтобы сосуд стал пустым. Исходя из этой цели, Водолей без возражений выполнит команду вылей из А и в случае, когда сосуд А уже пуст.

Опишем результат выполнения этой команды в зависимости от того, достаточно ли в сосуде B свободного объёма для всей воды из сосуда А. Если объёма достаточно, то сосуд А становится пустым, а в B оказывается вся вода, которая была в А и B вместе до переливания. Если же объёма в B недостаточно, то B становится полным, а в А остаётся столько воды, сколько не поместилось в B. Возможна и ситуация, когда для наполнения B до краев нужно ровно столько воды, сколько налито в А. В этом случае после выполнения команды сосуд А окажется пустым, а сосуд B наполненным до краёв.

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

Число команд третьего вида равно числу пар различных сосудов. Для трёх сосудов число этих команд равно 6.

Подведём итоги описания команд Водолея для двух сосудов.

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

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

Условие задачи отображается на экране: указываются объёмы сосудов Водолея и число литров воды, которое нужно отмерить.

Задача 1 (задание 7 игры «Водолей»). Отмерь 1 литр воды с помощью одного 5-литрового сосуда и одного 3-литрового сосуда.

Сначала мы подумаем над решением задачи без компьютера, а потом проверим решение на компьютере в игре «Водолей». Придумать решение этой задачи можно таким способом. Если бы у Водолея были 5-литровый сосуд и 6-литровый сосуд, то мы наполнили бы 6-литровый сосуд и перелили бы его содержимое в пустой 5-литровый сосуд. Тогда в 6-литровом сосуде остался бы как раз один литр. Но у нас в задаче 5-литровый сосуд есть, а вместо 6-литрового сосуда у нас 3-литровый сосуд В. Ничего страшного, 6 литров — это два раза по 3 литра. Сначала наполним 3-литровый сосуд и перельём его в 5-литровый. Затем снова наполним 3-литровый сосуд и после, переливания его в 5-литровый, в 3-литровом сосуде В останется ровно один литр. Мы уже отмерили все, что нужно, но по правилам игры «Водолей» нужно ещё опустошить сосуд А. Таким образом, отмерить 1 литр можно, дав Водолею 5 команд:

наполни B
перелей из B в A
наполни B
перелей из B в A
вылей из A

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

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

Введём эту цепочку в виде программы на алгоритмическом языке в игре «Водолей» — так мы увидим наглядно, как Водолей выполняет запланированные нами переливания.

Правила ввода и выполнения программ в игре «Водолей».

После входа в игру вы увидите список всех заданий:

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

Выше программы расположены 4 кнопки управления — они нужны, чтобы запустить или остановить выполнение программы:

Введём программу из нашего решения задачи 1 и для проверки запустим её выполнение — нажмём зелёную кнопку. Программа на наших глазах выполнится, и мы увидим, что она правильная — получен нужный результат, в сосуде B отмерен 1 литр:

В XXI веке перед человеком всё чаще возникают задачи, которые «непонятно, как решать». Наверное, такие задачи вам тоже встречались и в курсе математики, и в жизни. Это — хорошо, надо привыкать к решению таких задач, тренироваться. При этом человек приобретает опыт и в использовании некоторых общих подходов, методов решения задач, применимых в различных ситуациях.

2. Попробовав разные варианты, вы постепенно нащупали решение. Опять-таки, надеемся, что решение — правильное. Вероятно, вы получили при этом больше удовольствия, чем, скажем, при решении примера «78302 х 239 =?». И очень важно, что вы приобрели опыт решения чего-то нового.

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

Теперь мы расскажем вам об одном общем подходе к решению самых разных задач, совсем не обязательно из информатики. Вот в чём он состоит:
• Предположите, что задача уже решена. В нашем случае —
что нужное количество воды отмерено, то есть состояние
наших сосудов — требуемое.
• Подумайте, какое состояние могло быть до этого, из которого
можно перейти в требуемое. Сделайте мысленный «шаг назад»
(чтобы сделать «шаг вперёд», может потребоваться несколько
команд).
• Подумайте, из какого состояния можно попасть в то, которое
вы себе представили.
• И т. д.

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

Может быть, вы уже знали этот способ или изобрели его в ходе решения задачи (что ещё лучше).

Можно представить себе наш ход мысли и несколько иначе. Мы можем, не сумев сразу решить какую-то задачу, свести её к другой, которая кажется нам более простой. «Свести» означает, что если мы решим более простую задачу, то решим и первоначальную.

Давайте попробуем так решать нашу задачу о переливании.

0. Наша исходная задача — получить 4 л в любом сосуде, например, в сосуде B.

1. Глядя на наши сосуды, мы видим, что достаточно получить 7 литров в сосуде A. После этого надо выполнить пару команд:
наполни B
перелей из B в A

При переливании из B в A сосуд A вместит дополнительно только 1 л
(7+1=8), а 5–1=4 л останется в сосуде B,и исходная задача решена.

2. Как получить 7 литров в сосуде A? Можно, например, сначала получить 2 л в сосуде A. Если в сосуде A 2 л воды, то после выполнения команд
наполни B
перелей из B в A
в сосуде A окажется 2+5=7 л воды.

3. Задача получения 2 л в сосуде A сводится к задаче получить 2 л в сосуде B. Если в сосуде B 2 л, то нужно выполнить пару команд:
вылей из А
перелей из B в A

4. А как можно получить 2 л в сосуде B? Эта задача сводится к задаче получить 5 л в сосуде A. Если в сосуде А 5 л, то нужно выполнить пару команд:
наполни B
перелей из B в A
При переливании из B в A сосуд A заполнится до краёв и в B останется 2 л.

5. А задача получить 5 л в A совсем простая и решается так: если сосуд A пуст, то достаточно выполнить две команды:
наполни B
перелей из B в A

Но в начальный момент, по условию задачи, сосуд A пуст.

Проверим, привёл ли наш способ сведения задач и хода в обратную сторону к решению.

Итак, в условии задачи дано, что в начальный момент сосуд A пуст. Поэтому:
– выполнение в начальный момент пары команд из п. 5 решит задачу
получить 5 литров в сосуде A;
– последующее выполнение пары команд из п. 4 решит задачу
получить 2 литра в сосуде B;
– последующее выполнение пары команд из п. 3 решит задачу
получить 2 литра в сосуде A;
– последующее выполнение пары команд из п. 2 решит задачу
получить 7 литров в сосуде A;
– последующее выполнение пары команд из п. 1 решит исходную задачу
получить 4 литра в сосуде B.

Таким образом, исходная задача получить 4 л в сосуде B решается такой последовательностью из 10 команд:
наполни B
перелей из B в A
наполни B
перелей из B в A
вылей из А
перелей из B в A
наполни B
перелей из B в A
наполни B
перелей из B в A

Чтобы проверить эту программу в игре «Водолей», нужно еще по завершении программы опустошить сосуд A, то есть добавить в конец программы команду

вылей из А

Проверим это решение на компьютере. Компьютер подтверждает, что всё правильно (см. рисунок на следующей странице).

Итак, мы познакомились с одним из приёмов алгоритмического мышления — это решение задачи «с конца». Мы представляем себе цель, дальше понимаем, что цель будет достигнута, если мы дойдём до предыдущей цели и т. д. Этот приём является частным случаем более общего подхода: мы выделяем некоторую промежуточную цель, о которой можем не знать точно, а только надеяться, что она достижима. И дальше мы решаем уже две задачи: как достичь промежуточной цели и как из промежуточной достичь конечной.

Наконец, и этот подход можно обобщить: можно по исходной задаче создать систему новых задач, решение которых может нас привести к искомой цели. По ходу дела некоторые новые задачи могут оказаться нерешаемыми или ненужными, а заключительную цель приходится менять. Но в конце концов мы находим решение исходной задачи. И это всё — алгоритмическое мышление! Конечно, в алгоритмическом мышлении есть и другие элементы. О них будет идти речь на протяжении всего нашего учебника.

Предположим, нам дали решение задачи «отмерить», показанное на рисунке выше:

наполни B
перелей из B в A
наполни B
перелей из B в A
вылей из А
перелей из B в A
наполни B
перелей из B в A
наполни B
перелей из B в A
вылей из А

Как проверить, что это решение правильное?

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

Заполнять эту таблицу будем последовательно, сверху вниз. Заполним строку 1. До выполнения команды наполни B оба сосуда были пусты. После выполнения команды сосуд A останется пустым, сосуд B наполнится до краёв, значит, вносим в таблицу в строку 1 числа 0 и 5. Повторяя эти действия, получаем такую таблицу:

Из таблицы видно, что после выполнения последней команды программы в сосуде B будет 4 л, а сосуд A будет пуст. Таким образом, таблица доказывает, что наша программа действительно даёт нужное решение задачи.

При составлении таблицы человек мог допустить ошибку. Как проверить, правильно ли составлена таблица? Можно попробовать составить её ещё раз и потом сравнить, что получилось. Можно поступить иначе. А именно, попросим кого-нибудь (но можем сделать это и сами) прочитать состояние сосудов в каждой строке (начиная с нулевой). Например (какая там команда — неважно):

Затем прочитать в следующей строке команду и состояние сосудов:

Теперь выполним команду. Видим, что состояние сосудов в следующей строке записано правильно: мы из B перелили в A 3 л, больше в A не поместилось, сосуд A заполнился, в B осталось 2 л. Значит, строка 4 заполнена правильно.

При решении задачи 2 Водолей израсходовал 20 л воды из резервуара и вылил 16 л воды. А 4 л остались в сосуде B в качестве результата работы. Чтобы отмерить 4 л, мы израсходовали целых 20 л воды. Если бы мы попробовали получить 4 л с помощью сосудов 8 л и 7 л, то, как показывают эксперименты, пришлось бы израсходовать ещё больше воды (потребовалось бы не меньше 40 л). А что, если Водолей не будет выливать воду на землю, а будет аккуратненько возвращать её в тот резервуар, откуда он воду берёт? Оказывается, в этом случае удастся обойтись гораздо меньшим количеством воды. А именно, если в начальный момент у Водолея два пустых рабочих сосуда A и B и в резервуаре запасено ровно столько воды, сколько нужно для одновременного заполнения A и B, то Водолей может спокойно проводить все операции с сосудами A и B, не беспокоясь о том, что в резервуаре не хватит воды.

Действительно, суммарное количество воды в сосудах и резервуаре остаётся постоянным. Поэтому переполнение резервуара случиться не может, ведь в начальный момент вся вода помещалась в резервуаре. Стать пустым резервуар может. Но только в том случае, когда оба сосуда A и B полностью заполнены. Но в этом случае необходимости брать воду из резервуара нет, поскольку в сосудах нет свободного места.

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

Если в условии задачи этого раздела не указано начальное количество воды в сосудах, то это означает, что все сосуды пусты.

Задачи 4–14 предназначены для тех, кто хочет взяться за решение следующей сложной проблемы:

Конечно, для некоторых объёмов сосудов сразу ясно, что программу написать можно, а для некоторых — сразу ясно, что программу написать нельзя. Например, если объём сосуда А равен 1 л, а объём сосуда В равен 2 л, то программа будет состоять из одной команды наполни А. А вот если объём каждого сосуда равен 2 л или объёмы сосудов будут 2 и 4 л, то 1 л отмерить не удастся.