SQR:
MOV SP, R0
ADD 2,R0
MOV (R0),R0
MUL R0,R0
RET
Остается один вопрос – кто же будет освобождать стек, удаляя из него параметры подпрограммы? Тут есть два варианта. Этим может заниматься вызывающая программа – после вызова подпрограмму нужно использовать команду POP. Кроме того, это может делать и процедура – для этого нужно применить команду RET с параметром, который обозначает количество байт, которые нужно «сбросить» со стека. Например, в нашем случае можно применить команду
RET 2
которая освободит 2 байта (удалит один параметр). Отметим, что параметр команды RET – четное число, записанное в шестнадцатеричной системе счисления.
Таким образом, если параметров мало, их удобно передавать через регистры R0-R3. Кроме того, параметры можно передавать через стек. Если подпрограмма обрабатывает большой массив, лучше передать ей адрес этого массива, вместо того, чтобы записывать его в стек.
Рекурсия
Для процессора рекурсивная подпрограмма ничем не отличается от «обычной». Только внутри рекурсивной подпрограммы есть вызов CALL по адресу той же самой подпрограммы.
Напишем рекурсивную подпрограмму для вычисления факториала числа, находящегося в регистре R0. Результат должен быть помещен в тот же регистр R0.
Факториал числа 
вычисляется как произведение всех натуральных чисел от 1 до : 
. Основная идея подпрограммы может быть записана на псевдокоде так:
R1:=R0
R0:=R0-1
вычисляем факториал R0 (вызов процедуры)
R0:=R0*R1
Перевод на язык ассемблера дает:
FACT:
MOV R0,R1
SUB 1,R0
CALL FACT
MUL R1,R0
FINISH:
RET
Однако, выполнение этой подпрограммы никогда не закончится, потому что вызовы никогда не остановятся. Нужно добавить условие выхода: если R0=1, нужно выйти из подпрограммы, то есть перейти на последнюю команду RET (перед ней должна быть метка):
FACT:
CMP 1,R0
JZ FINISH
MOV R0,R1
SUB 1,R0
CALL FACT
MUL R1,R0
FINISH:
RET
Остается еще один недостаток – подпрограмма изменяет значение регистра R1. Нужно при входе в процедуру сохранить его (в стеке), а перед выходом – восстановить. Это вы уже можете сделать самостоятельно.
Задание на практическую работу
1. Запустите тренажёр «ЛамПанель». Напишите и отладьте программу, которая меняет местами значение регистров R2 и R3 с помощью стека (не используя других регистров общего назначения).
Программа:
Опишите, как работает стек при выполнении этой программы:
2. Введите текст программы
MOV 12,R0
CALL SQR
STOP
SQR:
MUL R0,R0
RET
Заполните таблицу, выполнив программу пошагово с помощью клавиши F7 (пошаговое выполнение со входом в подпрограммы):
Адрес | Команда | Регистры после ее выполнения | ||
R0 | PC | SP | ||
? | 0000 | 0100 | ||
MOV 12,R0 | ||||
CALL SQR | ||||
STOP | ||||
MUL R0,R0 | ||||
RET |
3. Напишите и отладьте программу с подпрограммой, которая вычисляет куб числа, записанного в регистр R0.
Программа:
4. Напишите и отладьте программу с подпрограммой, которая и строит RGB-код цвета, 4-битные составляющие которого (R, G и B), записаны соответственно в регистры R0, R1 и R2. Результат должен быть получен в регистре R0.
Программа:
5. Выполните предыдущее задание при условии, что параметры передаются через стек, а значения регистров R1 и R2 не должны измениться.
Программа:
6. Отладьте программу с рекурсивной подпрограммой, которая вычисляет факториал числа, записанного в регистр R0. При выполнении в пошаговом режиме (клавиша F7) наблюдайте, как изменяется регистр SP и содержимое стека.
Программа:
7. Решите задачу предыдущего пункта, используя подпрограмму без рекурсии.
Программа:
Практическая работа № 40.
Перебор элементов массива
Уровень A. Заполните массив случайными числами в интервале [0,100] и найдите среднее арифметическое его значений.
Пример:
Массив:
1 2 3 4 5
Среднее арифметическое 3.000
Уровень B. Заполните массив случайными числами в интервале [0,100] и подсчитайте отдельно среднее значение всех элементов, которые <50, и среднее значение всех элементов, которые ≥50.
Пример:
Массив:
3 2 52 4 60
Среднее арифметическое элементов [0,50): 3.000
Среднее арифметическое элементов [50,100): 56.000
Уровень C. Заполните массив из N элементов случайными числами в интервале [1,N] так, чтобы в массив обязательно вошли все числа от 1 до N (постройте случайную перестановку).
Пример:
Массив:
3 2 1 4 5
Практическая работа № 41.
Линейный поиск
Уровень A. Заполните массив случайными числами в интервале [0,5]. Введите число X и найдите все значения, равные X.
Пример:
Массив:
1 2 3 1 2
Что ищем:
2
Нашли: A[2]=2, A[5]=2
Пример:
Массив:
1 2 3 1 2
Что ищем:
6
Ничего не нашли.
Уровень B. Заполните массив случайными числами в интервале [0,5]. Определить, есть ли в нем элементы с одинаковыми значениями, стоящие рядом.
Пример:
Массив:
1 2 3 3 2 1
Есть: 3
Пример:
Массив:
1 2 3 4 2 1
Нет
Уровень C. Заполните массив случайными числами. Определить, есть ли в нем элементы с одинаковыми значениями, не обязательно стоящие рядом.
Пример:
Массив:
3 2 1 3 2 5
Есть: 3, 2
Пример:
Массив:
3 2 1 4 0 5
Нет
Практическая работа № 42.
Поиск максимального элемента массива
Уровень A. Заполните массив случайными числами и найти минимальный и максимальный элементы массива и их номера.
Пример:
Массив:
1 2 3 4 5
Минимальный элемент: A[1]=1
Максимальный элемент: A[5]=5
Уровень B. Заполните массив случайными числами и найти два максимальных элемента массива и их номера.
Пример:
Массив:
5 5 3 4 1
Максимальный элемент: A[1]=5
Второй максимум: A[2]=5
Уровень C. Введите массив с клавиатуры и найдите (за один проход) количество элементов, имеющих максимальное значение.
Пример:
Массив:
3 4 5 5 3 4 5
Максимальное значение 5
Количество элементов 3
Практическая работа № 43.
Алгоритмы обработки массивов
Уровень A. В. Заполнить массив случайными числами и выполнить циклический сдвиг элементов массива вправо на 1 элемент.
Пример:
Массив:
1 2 3 4 5 6
Результат:
6 1 2 3 4 5
Уровень B. Массив имеет четное число элементов. Заполнить массив случайными числами и выполнить реверс отдельно в первой половине и второй половине.
Пример:
Массив:
1 2 3 4 5 6
Результат:
3 2 1 6 5 4
Уровень C. Заполнить массив случайными числами в интервале [-100,100] и переставить элементы так, чтобы все положительные элементы стояли в начала массива, а все отрицательные и нули – в конце. Вычислите количество положительных элементов.
Пример:
Массив:
20 -90 15 -34 10 0
Результат:
20 15 10 -90 -34 0
Количество положительных элементов: 3
Практическая работа № 44.
Отбор элементов массива по условию
Уровень A. Заполнить массив случайными числами в интервале [-10,10] и отобрать в другой массив все чётные отрицательные числа.
Пример:
Массив А:
-5 6 7 -4 -6 8 -8
Массив B:
-4 -6 -8
Уровень B. Заполнить массив случайными числами в интервале [0,100] и отобрать в другой массив все простые числа. Используйте логическую функцию, которая определяет, является ли переданное ей число простым.
Пример:
Массив А:
12 13 85 96 47
Массив B:
13 47
Уровень C. Заполнить массив случайными числами и отобрать в другой массив все числа Фибоначчи. Используйте логическую функцию, которая определяет, является ли переданное ей число числом Фибоначчи.
Пример:
Массив А:
12 13 85 34 47
Массив B:
13 34
Практическая работа № 45.
Сортировка. Метод пузырька
Уровень A. Напишите программу, в которой сортировка выполняется «методом камня» – самый «тяжёлый» элемент опускается в конец массива.
Уровень B. Напишите вариант метода пузырька, который заканчивает работу, если на очередном шаге внешнего цикла не было перестановок.
Уровень C. Напишите программу, которая сортирует массив по убыванию суммы цифр числа. Используйте функцию, которая определяет сумму цифр числа.
Практическая работа № 46.
Сортировка. Метод выбора
Уровень A. Массив содержит четное количество элементов. Напишите программу, которая сортирует первую половину массива по возрастанию, а вторую – по убыванию. Каждый элемент должен остаться в «своей» половине.
Пример:
Массив:
5 3 4 2 1 6 3 2
После сортировки:
2 3 4 5 6 3 2 1
Уровень B. Напишите программу, которая сортирует массив и находит количество различных чисел в нем.
Пример:
Массив:
5 3 4 2 1 6 3 2 4
После сортировки:
1 2 2 3 3 4 4 5 6
Различных чисел: 6
Уровень C. Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком» и методом выбора. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.
Практическая работа № 47.
Быстрая сортировка
Уровень A. Массив содержит четное количество элементов. Напишите программу, которая сортирует по возрастанию отдельно элементы первой и второй половин массива. Каждый элемент должен остаться в «своей» половине. Используйте алгоритм быстрой сортировки.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
