Наши занятия опираются на учебник:

Звонкин А. К. Информатика : алгоритмика : учеб. для 6 кл. общеобразоват. учреждений / А. К. Звонки, С. К. Ландо, А. Л. Семенов. – М. : Просвещение, 2006. – 239 с. : ил. – ISBN 5-09-014569-5.

Глава 1. Исполнитель и его команды

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

1. Волк, коза и капуста с точки зрения программиста

Вот старинная задача под названием «Волк, коза и капуста».

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

Давайте подумаем, кого перевозить первым. Ясно, что нельзя брать волка – коза останется с капустой и съест её. По той же причине нельзя брать и капусту. Но вполне возможно забрать козу (волки обычно не любят капусту). После этого крестьянин может только вернуться в пустой лодке – везти козу назад бессмысленно.

Итак, первые два шага в решении задачи такие:

перевези козу
переправься

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

После этого у крестьянина есть две возможности:

перевези волка;
перевезти капусту.

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

Открыть задачу на полный экран

Нередко при решении этой задачи появляются такие предложения:

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

Конечно, в условии ничего не сказано про то, что рядом есть мост. Но ведь там не говорится ни слова и о том, что моста нет!

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

перевези волка
перевези капусту
перевези козу
переправься

Допустимы только действия, перечисленные в списке; все прочие строго запрещены (или, иначе, все другие действия не имеют отношения к задаче).

Рассказанная история подводит к одному из важнейших понятий книги – Исполнителю. Исполнитель – это человек или механическое устройство (или, скажем, компьютер) со строго определённым набором возможных операций. Эти операции называются командами. Исполнитель может выполнять команды из набора, и ничего более. В задаче Крестьянин был Исполнителем, а его набор команд состоял из четырёх операций.

2. Задача напоминает игру

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

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

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

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

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

В этой книге вы встретитесь с несколькими Исполнителями и некоторыми играми.