Из сборника Введение в информатику. Лабораторные работы. Ч. II / Авт.-сост. А.П. Шестаков; Перм. ун-т. — Пермь, 1999. — 71 с.
Подпрограммы (вспомогательные алгоритмы) целесообразно использовать в тех случаях, когда исходная задача является достаточно сложной, а ее решение — громоздким. Тогда разумно выделить в ней отдельные подзадачи, решение каждой из которых оформить в виде подпрограммы. Еще более естественным является использование подпрограмм в тех случаях, когда некоторый фрагмент программы повторяется.
При обращении к подпрограммам в E97 используется стек — структура данных, организованная по принципу "последний пришел — первый ушел". Стек позволяет по окончанию работы подпрограммы обеспечить возврат в ту точку основной программы, которая следует сразу же за вызовом подпрограммы. При обращении к вспомогательному алгоритму адрес в указателе стека (SP) уменьшается на 2, по вновь полученному адресу записывается адрес, следующий за вызовом подпрограммы. Подпрограмма исполняется, и когда встречается команда возврата (0D00), в счетчик команд помещается адрес, на который указывает SP, значение SP увеличивается на 2. Таким образом исполнение основной программы продолжается.
Из сказанного выше следует, что в SP нужно поместить адрес, свободный от данных и программы; несколько предшествующих адресов также должны быть свободны, поскольку стек стоится в сторону уменьшения адресов.
Пример. На отрезке [m; n] вычислить сумму тех четных чисел, в десятичной записи которых три четных цифры.
В задаче можно выделить такие подзадачи:
Каждую из этих подзадач решим с помощью подпрограммы.
1) Определить, является ли число четным.
Число a будет четным, если остаток от деления на 2 этого числа равен нулю, и нечетным в противном случае.
План решения
1. b := a div 2 3. a := a - b 2. b := b * 2 4. Возврат из п/п
Распределение памяти
| R0 | R1 | R2 | R3 |
| — | — | адрес a | адрес b |
Подпрограмма
Адрес Команда Действие Замечания 0070 0167 (R3) := (R2) b := a 0072 06D7 (R3) := (R3) \ 2 b := a div 2 0074 0002 0076 05D7 (R3) := (R3) * 2 b := b * 2 0078 0002 007A 0376 (R6) := (R6) - (R7) a := a - b 007C 0D00 возврат из п/п
2) Подсчет количества четных цифр в десятичной записи числа.
Отделяем очередную цифру числа z (остаток от деления на 10) и проверяем ее на четность. Если четная, учитываем это. Число z делим на 10 и повторяем процедуру. Действия продолжим до тех пор, пока последнее частное не станет равным нулю.
План решения
1. s := 0 6. m := z - k 2. Сравнить z с 0 7. Если m четное, то s := s + 1 3. Если z=0, то к п. 10 8. z := z div 10 4. k:=z div 10 9. Переход к п. 2. 5. k:=k*10 10. Возврат из п/п.
Распределение памяти
| R0 | R1 | R2 | R3 |
| — | адрес s, k | адрес a=m | адрес b, z |
Подпрограмма
Адрес Команда Действие Замечания 0080 01D5 0 => (R1) s := 0 0082 0000 0084 02D1 R1 := R1 + 2 адрес k 0086 0002 0088 04D7 сравнить (R3) с 0 сравнить z с 0 008A 0000 008C 5D32 если =0, к возврату из п/п 008E 0175 (R3) => (R1) k := z 0090 06D5 (R1) := (R1) \ 10 k := k \ 10 0092 000A 0094 05D5 (R1) := (R1) * 10 k := k * 10 0096 000A 0098 0176 (R3) => (R2) m := z 009A 0356 (R2) := (R2) - (R1) m := m - k 009C 03D3 R3 := R3 - 2 адрес b 009E 0002 00A0 9C0D переход на п/п определения четности 00A2 0070 00A4 04D6 сравнить (R2) с 0 00A6 0000 00A8 4D0C если <>0, переход на C байт 00AA 03D1 R1 := R1 - 2 адрес s 00AC 0002 00AE 02D5 (R1) := (R1) + 1 s := s + 1 00B0 0001 00B2 02D1 R1 := R1 + 2 адрес k 00B4 0002 00B6 02D3 R3 := R3 + 2 адрес z 00B8 0002 00BA 06D7 (R3) := (R3) \ 10 z := z \ 10 00BC 000A 00BE 1DC8 переход на сравнение z с 0 00C0 03D1 R1 := R1 - 2 адрес s 00C2 0002 00C4 03D3 R3 := R3 - 2 адрес, предшествующий z 00C6 0002 00C8 0D00 возврат из п/п
Приступим к составлению основной программы. Для решения задачи достаточно просмотреть все числа от m до n включительно. Проверяем очередное число — будет ли оно четным, если да, то вычисляем количество четных цифр в его записи; если их будет 3 — добавляем число к сумме.
План решения
1. i := m 2. Sum := 0 3. Сравнить i с n 4. Если i>n, переход к п. 11. 5. Проверить четность числа i, если нечетное, перейти к п. 9. 6. Вычислить R - количество четных цифр в записи числа i. 7. Сравнить R с 3. Если R<>3, перейти к п. 9. 8. Sum := Sum + i. 9. i := i + 1. 10. Перейти к п. 3. 11. Стоп
Распределение памяти
| R0 | R1 | R2 | R3 |
| адрес m, Sum, n | адрес i, R, в п/п | в п/п | в п/п |
Адрес 0050 0052 0054 0056 0058 005A 005C 005E 0060 Переменная m Sum n i R, s k a, m z b
Тесты
Программа
Адрес Команда Действие Замечания 0000 0145 (R0) => (R1) i := m 0002 02D0 R0 := R0 + 2 адрес Sum 0004 0002 0006 01D4 0 => (R0) Sum := 0 0008 0000 000A 02D0 R0 := R0 + 2 адрес n 000C 0002 000E 0454 сравнить (R1) с (R0) (i с n) (R0) - (R1) 0010 3D38 если >0, переход на 38 байт на стоп 0012 0156 (R1) => (R2) a := i 0014 9C0D переход на п/п& 0016 0070 определения четности 0018 04D6 сравнить (R2) с 0 сравнить a с 0 001A 4D28 если <>0, переход на 28 байт на изменение i 001C 02D3 R3 := R3 + 2 адрес z 001E 0002 0020 0157 (R1) => (R3) z := i 0022 02D1 R1 := R1 + 2 адрес R 0024 0002 0026 9C0D переход на п/п сколько четных цифр в числе 0028 0080 002A 04D5 сравнить (R1) с 3 (R с 3) (R1) - 3 002C 0003 002E 4D10 если <>0, переход на 10 байт на увеличение i 0030 03D0 R0 := R0 - 2 адрес Sum 0032 0002 0034 03D1 R1 := R1 - 2 адрес i 0036 0002 0038 0254 (R0) := (R0) + (R1) Sum := Sum + i 003A 02D0 R0 := R0 + 2 адрес n 003C 0002 003E 1D04 переход на 4 байта адрес i уже вычислен 0040 03D1 R1 := R1 - 2 адрес i 0042 0002 0044 02D5 (R1) := (R1) + 1 i := i + 1 0046 0001 0048 1DC4 переход к сравнению i с n 004A 0F00 стоп
Примечание. Расчет переходов предлагаем читателю проделать самостоятельно.
На примере данной задачи рассмотрим более подробно механизм обращения к подпрограмме. По схеме можно проследить, как осуществляются переход к вспомогательному алгоритму и возврат в вызывающую программную единицу.
Рассмотрим, как изменяется содержание регистра — указателя стека SP и памяти по тем адресам, на которые указывает SP, во время исполнения программы. Начальный адрес в SP — 00FE(16).
До вызова После вызова После вызова После возврата После возврата
первой п/п первой п/п второй п/п из второй п/п из первой п/п
SP: 00FE SP: 00FC SP: 00FA SP: 00FC SP: 00FE
00FC: 002A 00FA: 00A4 00FC: 002A
00FC: 002A
Следует заметить, что регистр SP может быть использован не только при работе с подпрограммами, но и для промежуточного хранения величин.
Заметим также, что подпрограммы могут обращаться и сами к себе — прямо или косвенно (через другие подпрограммы). Подпрограмма, вызывающая себя, называется рекурсивной.
Пример. Продемонстрируем это на классическом примере рекурсивного алгоритма — вычислении факториала
натурального числа. С одной стороны, n! определяется как произведение
последовательных натуральных чисел от 1 до n включительно.
С другой стороны 
Это и есть рекурсивное определение факториала, которым мы воспользуемся.
План решения
1. Сравнить n с 0. 2. Если n=0, переход к п. 7. 3. Запомнить n в стеке; n:=n-1. 4. Вызов п/п вычисления факториала. 5. F:=F*n. 6. Переход к п. 1. 7. F:=1. 8. Возврат из п/п.
Распределение памяти
| R0 | R1 | R2 | R3 |
| n | F | — | — |
Подпрограмма
Адрес Команда Действие Замечания 0070 2400 сравнить R0 c 0 n-0 0072 5D0E если равно 0, переход переход на F:=1 0074 0E20 n => стек 0076 2310 R0 := R0 - 1 n := n - 1 0078 9C0D переход к п/п 007A 0010 вычисления факториала 007C 0E30 стек => R0 n => R0 001E 0501 R1 := R1 * R0 F := F * n 0020 1D02 переход к возврату из п/п 0022 2111 1 => R1 F :=1 0024 0D00 возврат из п/п
Основная программа
Распределение памяти
| R0 | R1 | R2 | R3 |
| n | F | — | — |
Адрес Команда Действие Замечания 0000 0E6D Установка указателя 0002 00FE стека SP на адрес 00FE 0004 9C0D вызов п/п 0006 0010 вычисления факториала 0008 0F00 стоп
Тест. n=7; F=5040(10)=13B0(16). \vskip2mm
При решении задачи были использованы операции с короткой константой, а также запись в стек, чтение из стека, изменение указателя стека. Все это рассматривается в следующей работе, поэтому не будем здесь на этом останавливаться.