45
Программирование на микрокалькуляторе: ветвление и цикл
В. В. РОЖДЕСТВЕНСКИЙ,
С. Г. ХЛЕБУТИН
Эта заметка предназначется в первую очередь для девятиклассиков, изучающих курс «Основы информационных и вычислительных технологий» и имеющих доступ к программируемому микрокалькулятору.
В предыдущеем номере «Кванта» рассказываюсь о том, как простейшие программы, написанные на учебном алгоритмическом языке, можно «трансслировать в коды программируемого микрокалькулятора», то есть автоматически превращать такие программы в списком команд для микрокалькулятора (см. статью Л. Ф. Штернберга «Programmiрование на микрокалькуляторе: простейшие программы»). Здесь мы продолжаем этот рассказ. Речь躬дет о трансляции двух основных конструкций алгоритмического языка: ветвления и цикла. Изложение ведется применительно к микрокалькулятору «Электронка МК-54», но незначительными изменениями может быть присооблено к другим моделям отечественных программируемых калькуляторов.
Прежде всего, посмотрим как работает калькулятор в автоматическом режиме, то есть когда программа выполняется без вмешательства человека. Для управления выбором команды из памяти служит некоторая специализная ячейка, называемая счетчиком адресом.
Эта ячейка может содержать любой адрес программной памяти.
Если в авторном режиме нажать клавишу C/П, то тем самым отдается приказ калькулятору наать автоматический работу. Это значит, что калькулятор анализирует содержимое ячейки программиной памяти, на которую указывает счетчик адреса, выполняет ту или иную операцию и изменяет содержимое счетчика адреса. Такие действия называются тактом работы программы. Последовательно выполняя такты, программа считает, пока не встретиет команды СТОП.
Если в программе нет операций переходов, то в процессе выполнения одного такта значение счетчика адреса увеличивается на единицу. Операции перехода предназначены именно для того, чтобы менять содержимое счетчика адреса по нашему устройству. Как же работает команды перехода?
Рассмотрим команды БП и Fx∨0, где ∨ обозначает один из знаков операции сравнения: <, =, ≥, ≠. Для работы этих команд необходимо использовать две ячейки памяти: одну для хранения кода команды и следующего для хранения некоторого адреса.
Работа команды БП осуществляется так: калькулятор помещает в счетчик адреса тот адрес, который у нас записан в следующей последке кода БП ячейке.
Команда Fx∨0 делает следующее: если условие x∨0 выполено, то старое содержимое счетчика адреса увеличивается на два, если условие не выполено, то в счетчик адреса помещается адрес из следующего за кодом команды Fx∨0 ячейки.
Пример 1. Проследим за изменением счетчика адреса в процессе потокового выполнения следующего программы (см. таблицы ниже).
46
Итак, мы видим, что наличие операций перехода позволяет нарушать естественный (по порядку следования адресов) последовательность команды, а это как раз и необходимо при программировании конструкций «цикл» и «ветвление».
Конструкция «цикл»
На алгоритмическом языке такая конструкция выглідит следующим образом:
пока условие
нц
серия
кц
Для облегчения перехода конструкции «цикл» на язык калькулятора мы будем записьать ее в несколько ином виде, а именно:
пока
v ∨ 0
серия
кц
Здесь v — аргументческое выражение, ∨ — один из знаков сравнения, описанных выше.
Предлагаем следующую схему перехода оператора цикла с алгоритмического языка на язык калькулятора (здесь X обозначает вершину стека):
Заметим, что команда K НОП (нет операции) хотя и не влечет никакого действия, но удобна для установления соответствия между ключевыми словами (пока, кц). алгоритмческого языка и командами калькулятора, а также облегчает прослеживание логики программы. Выравнивание записей по вертикали удобно для поиска адресов перехода и для чтения программы.
Пример 2. Разработаем программу вычисления m=n!
На учебном алгоритмическом языке программа выглідит так:
алг факторial (цел m, n)
арг n
рез m
нач цел
ввод n
m:=1
i:=1
пока i<n
нц
i:=i+1
m:=m*i
кц
вывод m
кон
Обратите внимание на то, что в тело программы мы вставили две дополнительные команды (ввод и вывод) — они облегчают трансляцию.
Теперь можно транслировать программу. Сначала опишем место хранения переменных в виде таблицы.
Переменные n m i
Память RgO Rg1 Rg2
Оттраслированная программа выглідит так:
Адреса Команды Коды
00 C/П 50
01 X→ПО 40
02 1 01
03 X→П1 41
04 1 01
05 X→П2 42
06 K НОП 54
07 П→X2 62
08 П→X0 60
09 - 11
10 F x<0 5C
11 22 22
12 П→X2 62
13 1 01
14 + 10
15 X→П2 42
16 П→X1 61
17 П→X2 62
18 X 12
19 X→П1 41
20 БП 51
21 06 06
22 K НОП 54
23 П→X1 61
24 C/П 50
47
Конструкция «ветвление»
На алгоритмическом языке эта конструкция записьется так:
если условие
то серия 1
инначе серия 2
все
Для удобства перевод на языке калькулятора мы будем записьать ее так:
если
v ∨ 0
серия 1
инначе
серия 2
все
Предлагаем следующую схему перевода:
Для «укороченного» оператора ветвления (если… то… все) схема перевода может быть такой:
Пример 3. Разработаем программу нахождения большого из двух чисел a и b.
На алгоритмическом языке эту программу можно записьать следующим образом (как и выше, для удобства трансляции мы ввели дополнительные команды ввод и вывод):
алг бид (вещ a, b, y)
apr a, b
рез y
нач
ввод a, b
если a ≥ b
то y := a
инначе y := b
все
вывод y
кон
Выпишем в виде таблицы адреса переменных:
Переменные a b y
Память Rg a Rg b Rg 0
Программа транслирует следующим образом:
Адреса Команды Коды Алгоритмический язык
00 C/П 50
01 X→Па 4-
02 C/П 50
03 X→Пb 4L
04 КНОП 54
05 П→Ха 6-
06 П→Хb 6L
07 — 11
08 F x ≥ 0 59
09 14 14
10 П→Ха 6-
11 X→П0 40
12 БП 51
13 17 17
14 КНОП 54
15 П→Хb 6L
16 X→П0 40
17 КНОП 54
18 П→Х0 60
19 C/П 50
В заключение заметим, что схемы перевода могут быть лучшие или хуже, но само их наличие позволяет осуществлять перевод автоматически и почти без ошибок. Таким образом, если программа на алгоритмическом языке составлена грамотно, то довести ее до калькулятора совсем несложно.
Поправка
В первом номере «Кванта» за этот год допущена операция в условиям задачи 2 варианта I на стр. 52. Неравенство в условиям следует читать так: log > 0.