Арифметические исполнители

Арифметические исполнители представляют собой методически эффективный раздел обширной темы «Исполнители» в курсе раннего обучения информатике. Арифметические операции выполняются командами, которые, с одной стороны, строго формализованы и не требуют дополнительных комментирующих обсуждений, а с другой стороны, хорошо знакомы учащимся начальной школы по урокам математики. Чтобы опереться на априорные знания младших школьников, в качестве множества значений операндов в арифметических операциях программных исполнителей используются только целые положительные числа. С этим ограничением связаны аварийные сообщения «Не могу» у тех исполнителей, которые допускают операции вычитания и деления (хотя, разумеется, ориентируя такого рода исполнителей на старших школьников, программисту, реализующему такой исполнитель, не составило бы труда предусмотреть отрицательные и дробные результаты арифметических операций).

Простейшим из программных исполнителей, представляющим этот класс программ в Роботландии, можно назвать Автомат. Он использует всего только две арифметические операции, более того, два очень частных случая сложения и умножения: сложение (счетчика) только с единицей и умножение (счетчика) только на 2. Задачи этого исполнителя формулируются так: для любого заданного целого числа построить последовательность команд из СКИ Автомата, которая исходное нулевое состояние счетчика преобразует в заданное число. На таком множестве задач естественно выбрать задачу на оптимизацию: получить результат с помощью минимального количества команд. В последовательности команд только самая первая команда очевидна: она должны быть сложением, поскольку умножение не меняет нулевое состояние счетчика. Порядок следования остальных команд может быть, вообще говоря, любым. Однако получение заданного результата 13 путем тринадцати прибавлений единицы — это, несомненно, не лучшее решение. Желание поскорее добраться до результата подсказывает детям идею из последовательности умножений (удвоений). Но почти всегда (кроме случаев, когда заданое число представляет собою степень двойки) такой алгоритм не приводит к решению. Возникает задача об оптимальном чередовании команд, приводящих к заданному результату. Решая ее, учитель сначала записывает результат, например, 13 и спрашивает: «Какой из двух команд исполнителя Автомат можно получить это число?» Ответ:

ПРИБАВИТЬ

(поскольку в противном случае результат был бы четным). Следовательно, к началу зафиксированной команды в счетчике должно было находиться число 12. Записав это число рядом с командой

12 ПРИБАВИТЬ

учитель задает тот же вопрос. Теперь ответ на него звучит иначе: « I 2 получается командой УМНОЖИТЬ, так как в противном случае число было бы нечетным». Этот ответ отмечается записью, располагаемой выше предыдущей:

6 УМНОЖИТЬ

Проводя подобные рассуждения до тех пор, пока не будет достигнут нуль (исходное состояние счетчика), получают последовательность команд:

0 ПРИБАВИТЬ

1 УМНОЖИТЬ

2 ПРИБАВИТЬ

3 УМНОЖИТЬ

6 УМНОЖИТЬ

12 ПРИБАВИТЬ

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

0	ПРИБАВИТЬ
1	УМНОЖИТЬ
2	ПРИБАВИТЬ
3	УМНОЖИТЬ
6	УМНОЖИТЬ
12	ПРИБАВИТЬ

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

Центральным понятием уроков, посвященных Плюсику, остается, конечно, стек. В исполнителе Машинист он существовал как некоторый вспомогательный объект. Сейчас на нем фокусируется внимание. Как всегда, организуя «предмашинную» часть урока, учитель показывает, как стековый механизм памяти реализуется в стопке книг, на детской пирамидке, в мензурке, наполненной покрашенными шариками для настольного тенниса. Во всех этих примерах-демонстрациях дети знакомятся с новыми понятиями — верхушка стека, глубина стека. В компьютере стек очень удобен тем, что адрес операнда всякой операции определяется однозначно — это верхушка стека. Чтобы выполнить, например, команду СЛОЖИ, надо сначала взять из верхушки стека один из операндов. Конечно, в операции сложения безразлично, какой из операндов второй, а который — первый. Но формальный исполнитель Плюсик даже в этом случае поступает по реализованному в нем алгоритму: в верхушке стека располагается «второй» операнд операции. Когда слагаемое из верхушки стека взято, то, тем самым, место в верхушке освобождается, и его сразу же занимает следующий элемент стека, который является первым слагаемым операции. Взятое из верхушки стека число попадает на один из двух входов устройства, непосредственно выполняющего операцию. Это и есть арифметическое устройство процессора. Затем из стека (вновь из верхушки) извлекается следующее число, которое в нашей операции является первым операндом. Это число попадает на другой вход арифметического устройства. Устройство выполняет сложение введенных таким образом чисел, а получившийся на выходе результат отправляется обратно в стек и занимает место опять в верхушке стека. В результате выполнения арифметической операции глубина стека уменьшается на единицу: вместо двух взятых чисел-операндов в верхушке стало одно число-результат.

В начале работы исполнителя стек пуст. Чтобы его заполнить, нужна команда, имеющая формат ЗАПОМНИТЬ <число>. В результате ее выполнения число, задаваемое в команде, попадает в верхушку стека, а глубина стека увеличивается на единицу. Можно поэкспериментировать с этой командой, вводя в стек несколько чисел подряд. Цель эксперимента — определить, в какой ситуации команда ЗАПОМНИ порождает сообщение «Не могу». Далее, демонстрируется выполнение коммутативных операций сложения и умножения. Ставя вычислительные опыты с исполнителем Плюсик, дети могут поставить вопрос о сообщении «Не могу» для команд СЛОЖИ и УМНОЖЬ и, главное, самостоятельно ответить на них. Больше внимания требуют команды ВЫЧТИ и ДЕЛИ. В этих командах первый операнд — уменьшаемое и делимое — должен быть больше второго операнда — вычитаемого и делителя (коль скоро принято соглашение о множестве целых положительных чисел как области определения операндов Плюсика). Но поскольку Плюсик всегда направляет первый операнд на правый вход арифметического устройства, а второй — на левый, то порядок выполнения некоммутативных операций должен быть предусмотрен при заполнении стека. Следовательно, из двух операндов команды ВЫЧТИ первым в стек должно попасть большее — уменьшаемое, а вторым — меньшее вычитаемое, так как на левом входе арифметического устройства оказывается последнее попавшее в стек число. Упражнения с некоммутативными арифметическими операциями занимают столько времени на уроках Плюсика, сколько необходимо для усвоения этого непростого механизма, устанавливающего соответствие между последовательностью команд формирования стека и выполнением некоммутативных операций. Только после этого можно переходить к вычислению арифметических выражений, где участвуют три операнда. Если в число операций такого выражения входит, по крайней мере, одна некоммутативная операция, то порядок заполнения стека становится важным.

В вычислении выражения 2 + 7 — 3 возможны два варианта. Первый из них — с возможно опускаемыми скобками: (2 + 7) - 3, второй — со скобками обязательными 2 + (7 - 3).

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

ЗАПОМНИ 2

ЗАПОМНИ 7

СЛОЖИ

ЗАПОМНИ 3

ВЫЧТИ

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

ЗАПОМНИ 2

ЗАПОМНИ 3

ЗАПОМНИ 7

ВЫЧТИ

СЛОЖИ

Отсюда видно, что если есть разные варианты группирования операндов в скобки, то предпочтение следует отдавать тем из них, при которых в скобки попадают некоммутативные операции. Ясно, однако, что это возможно не всегда. Вот пример: 7 + 2 - 3. В нем (7 + 2) - 3 — это разрешимая задача для Плюсика, а при вычислении 7 + (2 - 3) Плюсик, работающий только с положительными числами, выдаст сообщение «Не могу». Таким образом, расстановка скобок — это сложный момент темы. Тем более, что в программе для Плюсика они формально отсутствуют, их всегда надо держать в воображении (или переносить это воображение на лист бумаги в виде дополнительных скобок). Например, для вычисления

(15 - 3) : (1 + 2)

надо отчетливо осознавать, что сначала в стек должны попасть числа, участвующие в вычислении делимого (левой скобки), затем следует выполнить операцию над этими числами, чтобы скобка сменилась одним числом, затем сверху в стек добавить числа, необходимые для вычисления делителя (правой скобки), только после этого вычислить делитель и выполнить последнюю команду ДЕЛИ:

ЗАПОМНИ 15

ЗАПОМНИ 3

ВЫЧТИ

ЗАПОМНИ 2

ЗАПОМНИ 1

СЛОЖИ

ДЕЛИ

На примере Плюсика полезно закрепить механизм постепенного сокращения синтаксических конструкций: на первом занятии с этим исполнителем команды предлагаются в развернутой форме, а далее используются их сокращенные формы С (СЛОЖИ), У (УМНОЖЬ) и т. д. В частности, операции со скобками целесообразно выполнять после того, как хорошо освоены сокращенные формы команд Плюсика. Для преобразования обычного арифметического выражения в программу для Плюсика можно просматривать выражение последовательно слева направо, записывая команды ЗАПОМНИ число. Если после очередной записи команды ЗАПОМНИ выяснится, что над последними двумя числами в стеке можно выполнить арифметическую операцию, записывается соответствующая команда. Если строго следовать этому алгоритму, ошибки не будет!

Пример.

Выражение: 28*(36-700/5)+15

(*) Составление программы для Плюсика: Просматриваем запись (*) слева направо и записываем команды запоминания:

ЗАПОМНИ 28 (нельзя выполнить операцию)

ЗАПОМНИ 36 (нельзя выполнить операцию)

ЗАПОМНИ 700 нельзя выполнить операцию)

ЗАПОМНИ 5 (можно выполнить деление)

ДЕЛИ (700/5, можно выполнить вычитание)

ВЫЧТИ 36-700/5, можно выполнить умножение)

УМНОЖЬ (28*(36-700/5), нельзя выполнить операцию)

ЗАПОМНИ 15 (можно выполнить сложение)

СЛОЖИ (28*(36-700/5)+15)

Возможности Плюсика полностью покрывают вычислительные потребности начальной школы. Поэтому в качестве завершения темы «Арифметические исполнители» можно порекомендовать проведение урока математики в школьном кабинете информатики. Последнее обстоятельство настолько важно, что при возможности следует (даже ценою разового перепланирования расписания кабинета информатики) пригласить детей в кабинет на урок, который в расписании назван «математика». Столь же важно, чтобы такой урок провел основной учитель класса, ведущий, в частности, математику, даже если курс раннего обучения информатике ведет в классе другой учитель (что должно быть, как об этом говорилось в предшествующих лекциях, скорее исключением, нежели правилом). На таком уроке сосредоточены вычислительные упражнения — задачи и примеры, решения которых записываются не в тетрадях, а на компьютерных экранах, в среде Плюсика. А сами задачи и примеры учитель не придумывает, а предлагает из школьного учебника (задачника) математики, с которым дети постоянно работают в школе. У такого урока, наряду с его учебными целями, большой важности воспитательная задача: здесь конструктивно и эффективно демонстрируются межпредметные связи информатики; дети воочию убеждаются, что компьютер — не только объект изучения на уроке информатики, но и дидактический инструмент других уроков. Позднее такие уроки можно сделать регулярными (компьютерные диктанты и грамматические упражнения на уроке русского языка, оформление дневника наблюдений на уроке естествознания и т. п.). Плюсик позволяет показать детям нетрадиционную запись арифметического выражения, называемую обратной польской записью. Эта запись оказывается очень удобным средством в компьютерных программах, переводящих обычные арифметические выражения на язык компьютеров, память которых организована в виде стека.

Вот как может выглядеть обычная запись выражения:

а + b * (с + d/e)/f

Обратная польская запись того же выражения имеет вид:

abcde/+*f/+

Сравните: Обычная запись выражения:

2 + 5 * (10 + 134/12)/7

Программа для Плюсика:

ЗАПОМНИ 2

ЗАПОМНИ 5

ЗАПОМНИ

10 ЗАПОМНИ

134 ЗАПОМНИ

12 ДЕЛИ

СЛОЖИ

УМНОЖЬ

ЗАПОМНИ 7

ДЕЛИ

СЛОЖИ

Конечно, при работе с Плюсиком не надо вводить термин «обратная польская запись», но нужно добиться, чтобы перевод выражения из обычной формы в обратную польскую (программу для Плюсика) не представлял для детей особого труда.