Из сборника Введение в информатику. Лабораторные работы. Ч. II / Авт.-сост. А.П.
Шестаков; Перм. ун-т. — Пермь, 1999. — 71 с.
Развилка и цикл
В предыдущей лабораторной работе мы рассмотрели примеры
программ, которые имеют линейную структуру, т.е. команды
выполняются последовательно, одна за другой, без изменения порядка
следования. Реально такие задачи встречаются достаточно редко.
Гораздо чаще приходится сталкиваться с ситуацией, когда действие
необходимо совершить при истинности некоторого условия — развилка.
Другая ситуация — повторение одной и той же последовательности
действий несколько раз — цикл.
Для реализации таких действий микропроцессор должен
содержать команды перехода. E97 не является исключением.
В его системе команд есть две команды перехода — абсолютного и
относительного.
Наиболее простой является команда абсолютного перехода. В этом случае
просто необходимо указать адрес, на который нужно попасть.
Структура команды следующая
Код команды абсолютного перехода — C.
Команда относительного перехода имеет следующий формат
Смещение указывает, на сколько необходимо изменить текущее
значение счетчика команд при организации перехода.
Значение модификатора в команде в большинстве случаев зависит
от управляющих битов Z и N регистра состояния PS.
Следующая таблица показывает возможные значения
модификатора.
МОД Условие перехода
0 возврат из подпрограммы
1 безусловный переход
2 результат неотрицателен (N=0)
3 результат отрицателен (N=1)
4 результат ненулевой (Z=0)
5 результат нулевой (Z=1)
6 результат неположительный (N=1 или Z=1)
7 результат положительный (N=0 и Z=0)
9 вызов подпрограммы
Код команды относительного перехода — D.
Если переход осуществляется в сторону увеличения адресов, то смещение
будет положительным, в сторону уменьшения адресов — отрицательным.
Смещение записывается в дополнительном коде.
Развилка может быть полной или неполной.
Полная развилка имеет структуру
если <условие> то <серия 1> иначе <серия 2>
Здесь <условие> — это отношение между двумя величинами.
Например, x< y; z>10. <серия 1>, <серия 2> —
действия, которые необходимо осуществить соответственно в случае
истинности или ложности условия.
Например если a < b то min := a иначе min := b.
В примере выбирается наименьшее из двух целых чисел a, b.
Неполная развилка имеет структуру если <условие> то <серия 1>.
В этом случае действия выполняются только в случае истинности
условия, в противном случае никаких действий выполнять не нужно.
Например если a < 0 то a := -a.
В примере данное число a заменяется модулем.
При реализации развилки (как полной, так и неполной) с помощью системы
команд E97 обычно используется несколько различных команд (в их числе
в большинстве случаев должна быть команда сравнения для установки
управляющих битов Z, N регистра состояния PS; очень часто присутствуют
команды условного и безусловного перехода).
Пример 1. Найти произведение наибольшего и наименьшего
из трех чисел a, b, c.
Согласно условию задачи прежде всего необходимо определить
наименьшее и наибольшее из трех чисел, после чего вычислить их произведение.
План решения
Сравнить числа a, b. Если a < b, то min:=a, иначе min:=b.
Сравнить числа min, c. Если c < min, то min:=c.
Сравнить числа a, b. Если a > b, то max:=a, иначе max:=b.
Сравнить числа max, c. Если c > max, то max:=c.
Вычислить p:=min*max.
Стоп.
Распределение памяти
R0
R1
R2
R3
адреса величин a, b, c
min
max
p
Адрес
0060
0062
0064
Величина
a
b
c
Тесты
a=-8 (FFF8); b=-1 (FFFF); c=4. Ответ: -32
a=5; b=10 (A); c=2. Ответ: 20 (14).
Программа
Адрес Команда Действие Замечания
0000 0141 (R0) => R1 min := a
0002 02D0 R0 := R0 + 2 адрес b
0004 0002
0006 0441 сравнить (R0) с R1 R1 - (R0)
0008 6D02 если <=0, переход на 1 слово (2 байта)
000A 0141 (R0) => R1 min := b
000C 02D0 R0 := R0 + 2 адрес c
000E 0002
0010 0441 сравнить (R0) с R1 R1 - (R0)
0012 6D02 если <=0, переход на 1 слово (2 байта)
0014 0141 (R0) => R1 min := c
0016 03D0 R0 := R0 - 4 адрес a
0018 0004
001A 0142 (R0) => R2 max := a
001C 02D0 R0 := R0 + 2 адрес b
001E 0002
0020 0442 сравнить (R0) с R2 R2 - (R0)
0022 2D02 если >=0, переход на 1 слово (2 байта)
0024 0142 (R0) => R2 max := b
0026 02D0 R0 := R0 + 2 адрес c
0028 0002
002A 0442 сравнить (R0) с R2 R2 - (R0)
002C 2D02 если >=0, переход на 1 слово (2 байта)
002E 0142 (R0) => R2 max := c
0030 0113 R1 => R3 p := min
0032 0523 R3 := R3 * R2 p := p * max
0034 0F00 стоп
В том случае, когда некоторая последовательность действий
повторяется несколько раз, используется цикл.
Действия в цикле выполняются до тех пор, пока
истинно некоторое условие (логическое выражение).
Как только значение истинности меняется на противоположное,
исполнение цикла прекращается.
В E97 цикл можно организовать, используя команды сравнения,
условного и безусловного перехода.
Пример 2. Найти сумму первых n нечетных натуральных чисел, которые
кратны 3.
Идея решения.
Указанные в условии задачи числа образуют последовательность
3, 9, 15, ..., 6n-3. Для получения суммы можно использовать цикл; очередное слагаемое
будет на 6 больше предыдущего.
План решения
1. i := 1. 6. S := S + k.
2. S := 0. 7. k := k + 6.
3. k := 3. 8. i := i + 1.
4. Сравнить i с n. 9. Перейти к п. 4.
5. Если i>n, перейти к п. 10. 10. Стоп.
Распределение памяти
R0
R1
R2
R3
n
i
k
S
Тест.n=10, S=300.
Программа
Адрес Команда Действие Замечания
0000 01D1 1 => R1 i := 1
0002 0001
0004 01D3 0 => R3 S := 0
0006 0000
0008 01D2 3 => R2 k := 3
000A 0003
000C 0410 сравнить R1 с R0 R0 - R1
000E 3D0C если i>n, переход на стоп
0010 0223 R3 := R3 + R2 S := S + k
0012 02D2 R2 := R2 + 6 k := k + 6
0014 0006
0016 02D1 R1 := R1 + 1 i := i + 1
0018 0001
001A 1DF0 переход на сравнение i с n
001C 0F00 стоп
Расчет переходов.
Переход в случае i>n на конец программы. При выполнении
этой команды счетчик адреса команд (согласно алгоритму работы процессора)
имеет значение 0010. Попасть необходимо на команду с адресом 001C.
Поэтому смещение будет таким: 001C - 0010=0C.
Безусловный переход (возврат) на сравнение i с n.
Адрес должен смениться с 001C на 000C.
Имеем 000C-001C=-10.
Это смещение необходимо записать в дополнительном коде.
Имеем: прямой код 10(16)=00010000(2);
дополнительный код 11101111(2)+1(2)=11110000(2)=F0(16).
Рассмотренная задача может быть решена и без использования цикла.
В самом деле, полученная последовательность является арифметической
прогрессией с разностью d=6. По формуле суммы первых n членов
имеем:
Последней формулой и можно воспользоваться для расчетов.
Вернемся к примеру 2 из предыдущей лабораторной работы.
Как видно из представленного решения, задача более рационально
должна быть решена с использованием цикла.
Пример 3. В последовательных ячейках памяти расположены пять целых
чисел. Получить произведение этих чисел. Содержимое памяти не изменять.
Распределение памяти
R0
R1
R2
R3
Адрес очередного числа
i
—
P
Заданные числа будем хранить с адреса 0050.
Тест
Адрес
0050
0052
0054
0056
0058
Величина
0002
FFFE
000A
FFFF
0003
Ответ: 120(10)=78(16)
Замечание. Целые числа записываются в память в дополнительном коде.
Программа
Адрес Команда Действие Замечания
0000 01D3 1 => R3 P := 1
0002 0001
0004 01D1 1 => R1 i := 1
0006 0001
0008 04D1 сравнить i c 5 R1 - 5
000A 0005
000C 7D0C если i>5, переход на стоп
000E 0543 R3 := R3 * (R0) P:=P * ai
0010 02D1 R1 := R1 + 1 i:=i+1
0012 0001
0014 02D0 R0 := R0 + 2 адрес следующего числа
0016 0002
0018 1DEE переход на сравнение i с 5
001A 0F00 стоп
Расчет переходов
1A - 0E = 0C
08 - 1A =-12 (EE)
Задания для самостоятельного выполнения
Числовая последовательность задана рекуррентной формулой
an=an-1+an-2. Найти k-ый член последовательности,
если a0=1 и a1=2.
Используя операцию вычитания, написать программу нахождения
частного и остатка от деления одного целого числа на другое.
На отрезке [1; 10] найти такое целочисленное значение
первого члена арифметической прогрессии, при котором один из
ее членов равен c. Разность d (d ≠ 1) задать самостоятельно.
Сколько членов последовательности предшествуют члену со значением c?
Даны два натуральных числа. Определить, сколько натуральных чисел
расположено между ними, и поместить эти числа в последовательно
расположенные ячейки памяти.
Вычислить 2n.
Большее из трех натуральных чисел умножить на 10, среднее по величине — на 50,
меньшее — на 100.
Найдите сумму всех целых чисел, принадлежащих отрезку [a, b].
В памяти хранятся числа a, b, причем a < b. Определить,
сколько раз можно к числу a прибавить 4, чтобы результат не
превышал b. Из полученной суммы вычесть b, результат записать в память.
Вычислить
В двух регистрах процессора находятся числа a, b, причем a < b.
К ним начинают прибавлять соответственно 3 и 1. Через
сколько повторений число в первом регистре будет больше, чем во втором?
В памяти по некоторому адресу хранится натуральное число.
Написать программу, которая позволяет переменной a присвоить
значение 0, если число четное, и 1, если — нечетное.
Заданы числа a, b, c (a < b < c; b - a >= 2). Сколько
раз нужно вычесть 5 из c, чтобы результат попал на отрезок
[a, b]? Предусмотреть случай, когда попадание на отрезок невозможно.
Число a умножить n раз на число b.
Какой член числовой последовательности
an=3an-1-1 превысит b, если a0=1?
Найти сумму четных чисел от 2 до n.
Результаты вычислений по формулам
y=8A-4B и z=|A+4B| записать в память. Большее из них поместить в R0.
Найти min {max (A,B), max (C,D)}.
Даны три числа. Занести их в память в порядке возрастания.
Проверить, попадает ли точка C(x, y) в квадрат
{a < x < b; c < y < d}. Если попадает, то ее абсциссу
занести в регистр R0, иначе — в память по адресу 90.
Из трех чисел найти наибольшее и вычесть из него все остальные.
Записать число a в память по адресу 72, а b —
по адресу 74. Вычислить c=|a-7b| и сравнить с d.
Если c > d, то очистить память с адресом 72, иначе — 74.
Даны два натуральных числа. Найти первое нечетное число,
следующее за большим из данных чисел.
Функция задана формулой:
(n — натуральное число). Составить программу
вычисления значений этой функции.
Заданы длины трех отрезков. Определить, могут ли эти
отрезки служить сторонами треугольника. Если могут, то
по адресу 76 занести 1, иначе — 2.
В регистрах R1, R2, R3 находятся числа. Записать номер регистра,
в котором находится наибольшее значение, в память по адресу 84.
Проверить, удовлетворяют ли заданные числа M и N
соотношениям |M|<10 и |N|>5.
В случае, если оба соотношения справедливы, то очистить память с адресом
76, в противном случае записать туда 1.
В памяти по адресам с 60 по 76 хранятся числа.
Переписать содержимое памяти с адресом 60+2N+M, где
M и N — произвольные целые числа, в регистр R3.
Предусмотреть контроль правильности полученного адреса.
Даны два угла треугольника. Проверить, будет ли он
прямоугольным. Если да, то по адресу 76 занести 1, иначе — 0.
В памяти находятся пять чисел. Найти наименьшее из них.
Для целых x, y, z вычислить max(x + y + z, xyz).
Для целых x, y, z вычислить min2(x + y + z / 2, xyz) + 1.
Написать программу, которая по заданным трем числам определяет, является ли сумма каких-либо двух из них положительной.
Составить программу, реализующую эпизод применения компьютера в книжном магазине. Исходные данные: стоимость книг, сумма денег, внесенную покупателем;
если сдачи не требуется, ответами являются числа 0 и 0; если денег внесено больше, то 1 и сумма сдачи; если денег недостаточно, то -1 и размер недостающей суммы.
Даны действительные числа a, b, c. Удвоить эти числа, если a ≥ b ≥ c, и заменить их абсолютными значениями, если это не так.
Заданы размеры A, B прямоугольного отверстия и размеры x, y, z кирпича. Определить, пройдет ли кирпич через отверстие (1 - пройдет; 0 - не пройдет).
Рис расфасован в два пакета. Масса первого — m кг, второго — n кг. Составьте программу, определяющую: а) какой пакет тяжелее — первый или второй? б) массу более тяжелого пакета.
Написать программу, которая анализирует мужчину по возрасту и относит к одной из четырех групп: дошкольник (0), ученик (1), работник (2), пенсионер (3).
Дано натуральное число n. Найти сумму первой и последней цифры этого числа.
Дано натуральное число n. Переставить местами первую и последнюю цифры этого числа.
Даны два натуральных числа m и n (m ≤ 9999, n ≤ 9999). Проверить, есть ли в записи числа m цифры, одинаковые с цифрами в записи числа n.
Дано натуральное число n. Проверить, есть ли в записи числа три одинаковые цифры (n ≤ 9999).
Дано натуральное число n ≤ 99. Дописать к нему цифру k в конец и в начало.
Даны натуральные числа n, k. Проверить, есть ли в записи числа nk цифра m.
Среди всех n-значных чисел указать те, сумма цифр которых равна данному числу k.
Заданы три натуральных числа A, B, C, которые обозначают число, месяц и год. Найти порядковый номер даты, начиная отсчет с начала года.
Найти наибольшую и наименьшую цифры в записи данного натурального числа.
Произведение n первых нечетных чисел равно p. Сколько сомножителей взято? Если введенное число n не является указанным произведением, сообщить об этом.
Найти на отрезке [n; m] натуральное число, имеющее наибольшее количество делителей.
Контрольные вопросы
Рассказать о форматах команд микропроцессора.
Что такое безусловный переход? В каких случаях он применяется?
Каково назначение битов N и Z регистра словосостояния?
Каково назначение других битов этого регистра?
Как организовать условный переход?
Как вычислить смещение при организации перехода?
Чем отличается абсолютный переход от относительного?
(n — натуральное число). Составить программу
вычисления значений этой функции.