Напишите процедуру, которая переставляет три переданные ей числа в порядке возрастания.
Пример:
Введите три натуральных числа:
10 15 5
5 10 15
Напишите процедуру, которая сокращает дробь вида M/N. Числитель и знаменатель дроби передаются как изменяемые параметры.
Пример:
Введите числитель и знаменатель дроби:
25 15
После сокращения: 5/3
Напишите процедуру, которая вычисляет наибольший общий делитель и наименьшее общее кратное двух натуральных чисел и возвращает их через изменяемые параметры.
Пример:
Введите два натуральных числа:
10 15
НОД(10,15)=5
НОК(10,15)=30
Функции
Напишите функцию, которая определяет сумму цифр переданного ей числа.
Пример:
Введите натуральное число:
123
Сумма цифр числа 123 равна 6.
Напишите функцию, которая находит наибольший общий делитель двух натуральных чисел.
Пример:
Введите два натуральных числа:
7006652 112307574
НОД(7006652,112307574) = 1234.
Напишите функцию, которая «переворачивает» число, то есть возвращает число, в котором цифры стоят в обратном порядке.
Пример:
Введите натуральное число:
1234
После переворота: 4321.
Логические функции
Напишите логическую функцию, которая определяет, является ли переданное ей число совершенным, то есть, равно ли оно сумме своих делителей, меньших его самого.
Пример:
Введите натуральное число:
28
Число 28 совершенное.
Пример:
Введите натуральное число:
29
Число 29 не совершенное.
Напишите логическую функцию, которая определяет, являются ли два переданные ей числа взаимно простыми, то есть, не имеющими общих делителей, кроме 1.
Пример:
Введите два натуральных числа:
28 15
Числа 28 и 15 взаимно простые.
Пример:
Введите два натуральных числа:
28 16
Числа 28 и 16 не взаимно простые.
Простое число называется гиперпростым, если любое число, получающееся из него откидыванием нескольких цифр, тоже является простым. Например, число 733 – гиперпростое, так как и оно само, и числа 73 и 7 – простые. Напишите логическую функцию, которая определяет, верно ли, что переданное ей число – гиперпростое. Используйте уже готовую функцию isPrime, которая приведена в учебнике.
Пример:
Введите натуральное число:
733
Число 733 гиперпростое.
Пример:
Введите натуральное число:
19
Число 19 не гиперпростое.
Рекурсия
Напишите рекурсивную функцию, которая вычисляет НОД двух натуральных чисел, используя модифицированный алгоритм Евклида.
Пример:
Введите два натуральных числа:
7006652 112307574
НОД(7006652,112307574) = 1234.
Напишите рекурсивную функцию, которая раскладывает число на простые сомножители.
Пример:
Введите натуральное число:
378
378 = 2*3*3*3*7
Дано натуральное число N. Требуется получить и вывести на экран все возможные различные способы представления этого числа в виде суммы натуральных чисел (то есть, 1 + 2 и 2 + 1 – это один и тот же способ разложения числа 3). Решите задачу с помощью рекурсивной процедуры.
Пример:
Введите натуральное число:
4
1 + 1 + 1 + 1
1 + 1 + 2
1 + 3
2 + 2
Стек
Из учебника (§ 61) вы уже знаете, что при вызове процедур важнейшую роль играет стек – область оперативной памяти, в которой хранятся адрес возврата из процедуры и локальные переменные. В этой практической работе мы познакомимся с работой стека на примере учебного компьютера «ЛамПанель», с которым вы уже встречались при изучении глав 4 и 5.
Возможности программы «ЛамПанель»
Программа «ЛамПанель» – это модель процессора, который управляет ламповой панелью, то есть, может с помощью специальных команд зажигать и гасить определенные лампочки.
Стек в программе «ЛамПанель» размещается в оперативной памяти, вместе с программой и данными. Оперативная память имеет размер 256 байт, адреса ячеек (байтов) изменяются от 0 до 255 = FF16. Программа начинается с адреса 0 (в начале области памяти), данные обычно расположены сразу за ней. Стек находится в самом конце оперативной памяти и «растет вверх». Это значит, что первое записанное в стек 16-битное слово имеет адрес FE16 (последние два байта памяти), следующее записанное слово – адрес FC16 и т.д. Как же компьютер разбирается, где начинается стек и сколько чисел туда записано?
В процессоре есть специальный регистр SP (от англ. StackPointer – указатель стека), в котором хранится адрес вершины стека, то есть последнего записанного в стек 16-битного значения. При запуске программы в регистр SP записывается значение 10016 (область 1 на рисунке). Этот адрес находится за границами оперативной памяти и говорит о том, что стек пуст.
Для того, чтобы записать значение из регистра общего назначения в стек, используется команда PUSH (от англ. push – втолкнуть). Например, при выполнении этих команд в стек будет записано значение регистра R0:
MOV 1234,R0
PUSH R0
Обратите внимание на значение регистра SP – оно стало равно FE16 и теперь указывает на последнее слово памяти (область 2 на рисунке), в котором записано число 123416 – значение регистра R0 (сначала младший байт, потом старший).
Добавим к программе еще одну команду, которая «снимает» 16-битное значение с вершины стека и записывает его в регистр R2:
POP R2
После этого наблюдаем следующее (см. рисунок ниже):
в регистре R2 находится то же значение 123416, которое было в R0 (область 1)
регистр SP содержит значение 10016, которое говорит о том, что стек пуст (область 2)
в последних двух байтах памяти осталось значение 123416, которое было записано в стек (область 3), но теперь оно уже не является часть стека, поскольку регистр SP изменен.
Вызов подпрограмм
Как вы знаете, подпрограммы – это вспомогательные алгоритмы. Напишем подпрограмму, которая возводит в квадрат значение регистра R0. Эта подпрограмма содержит всего одну команду умножения (умножить R0 на R0, записать результат в R0):
MUL R0, R0
В начале подпрограммы нужно поставить метку (имя подпрограммы), а в конце – команду возврата RET (от англ. return – возврат), по которой процессор возвращается в точку вызова. Таким образом, вся подпрограмма, которую мы назовём SQR, выглядит так:
SQR:
MUL R0, R0
RET
«Паспорт» этой подпрограммы такой:
Вход: число в регистре R0
Выход (результат): квадрат числа в регистре R0
Подпрограмма располагается ниже основной программы. Чтобы вызвать подпрограмму, используют команду CALL (от англ. call – вызвать), после которой записывают имя подпрограммы – метку, с которой она начинается, адрес точки входа. Вот вся программа вместе с подпрограммой:
MOV 12,R0 ; записать начальное значение в R0
CALL SQR ; вызвать подпрограмму SQR
STOP ; конец основной программы
SQR: ; точка входа подпрограммы
MUL R0, R0 ; тело подпрограммы – возведение R0 в квадрат
RET ; возврат из подпрограммы
Остается один вопрос: как процессор определяет адрес возврата из подпрограммы, когда выполняется команда RET? Заметим, что в самой команде RET адрес не указан. Дело в том, что адрес перехода заранее определить нельзя (нельзя поставить команду безусловного перехода JMP), потому что подпрограмма может вызываться из разных мест программы, в том числе из других подпрограмм. Эту проблему оказалось просто решить с помощью стека:
команда CALL записывает в стек адрес возврата из подпрограммы, то есть адрес команды, следующей за командой CALL; поскольку регистр PC (программный счётчик) всегда содержит адрес следующей команды, процессору достаточно просто скопировать содержимое регистра PC в стек;
после этого в регистр записывается адрес указанной подпрограммы и ей передается управление;
команда RET снимает с вершины стека адрес возврата и записывает его в регистр PC, таким образом управление передается следующей команде вызывающей программы.
Сохранение регистров
Теперь напишем более сложную подпрограмму, которая возводит R0 в куб. Теперь для вычисления придется задействовать ещё один регистр, например, R1:
MOV R0,R1 ; скопировать R0 в R1
MUL R0,R0 ; возвести R0 в квадрат
MUL R1,R0 ; умножить R1 на R0
Все хорошо, но… мы стерли значение регистра R1, которое было до вызова подпрограммы. Чтобы при вызове подпрограммы регистры не стирались, их нужно сохранять при входе в подпрограмму и восстанавливать перед самым выходом. Где сохранять? Самый простой выход – использовать стек, сохранять командой PUSH, и восстанавливать командой POP. Таким образом полный текст подпрограммы CUBE выглядит так:
CUBE:
PUSH R1 ; сохраняем R1
MOV R0,R1 ; скопировать R0 в R1
MUL R0,R0 ; возвести R0 в квадрат
MUL R1,R0 ; умножить R1 на R0
POP R1 ; восстанавливаем R1
RET
Передача параметров в подпрограмму
В предыдущих примерах вы уже увидели, что параметры (дополнительные данные) могут передаваться в подпрограмму через регистры общего назначения R0-R3. Но этих регистров всего четыре, поэтому таким способом можно передать только четыре 16-битных числа. А что, если нужно передать, например, массив из 100 элементов? В этом случае на помощь приходит стек.
Перед вызовом подпрограммы в стек записываются все передаваемые параметры. рассмотрим сначала «игрушечную» задачу – написать подпрограмму, которая возводит число в квадрат, причем это число передается через стек. Результат должен быть помещен в регистр R0.
Перед вызовом подпрограммы запишем в стек значение R0:
0000 MOV 12,R0 ; это число нужно возвести в квадрат
0004 PUSH R0 ; запишем его в стек
0006 CALL SQR ; вызов подпрограммы
000A STOP
000C SQR:
... ; здесь будет подпрограмма
Если посмотреть на стек (в нижней части оперативной памяти), то после выполнения команды PUSH R0 он выглядит так:
SP-> 00FE 0012
Указатель стека SP содержит адрес 00FE и указывает на последнее 16-битное слово памяти. В стеке находится число 1216 – значение, передаваемое в подпрограмму.
Когда выполнится команда CALL, в стек запишется адрес возврата из подпрограммы, то есть адрес 000A16, по которому расположена команда STOP. На этот адрес и будет указывать регистр SP:
SP-> 00FC 000A
00FE 0012
Теперь займемся подпрограммой: как «достать» переданное значение? Сначала нужно скопировать содержимое указателя стека в какой-то регистр общего назначения, например, в R0:
MOV SP,R0
Теперь в R0 находится адрес вершины стека, но там лежит адрес возврата. Чтобы получить адрес переданного параметра, нужно увеличить R0 на 2:
ADD 2,R0
Теперь можно взять значение по этому адресу и записать его в тот же регистр R0:
MOV (R0),R0
Запись (R0) означает «значение, находящееся в памяти по адресу, записанному в R0», это так называемый косвенный способ адресации, когда в регистре находится адрес данных, а не значение. Теперь в R0 уже получено переданное число, и можно возвести его в квадрат. Вот полная подпрограмма:
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. Нужно при входе в процедуру сохранить его (в стеке), а перед выходом – восстановить. Это вы уже можете сделать самостоятельно.
Задание на практическую работу
Запустите тренажёр «ЛамПанель». Напишите и отладьте программу, которая меняет местами значение регистров R2 и R3 с помощью стека (не используя других регистров общего назначения).
Программа:
Опишите, как работает стек при выполнении этой программы:
Введите текст программы
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
|
|
|
|
Напишите и отладьте программу с подпрограммой, которая вычисляет куб числа, записанного в регистр R0.
Программа:
Напишите и отладьте программу с подпрограммой, которая и строит RGB-код цвета, 4-битные составляющие которого (R, G и B), записаны соответственно в регистры R0, R1 и R2. Результат должен быть получен в регистре R0.
Программа:
Выполните предыдущее задание при условии, что параметры передаются через стек, а значения регистров R1 и R2 не должны измениться.
Программа:
Отладьте программу с рекурсивной подпрограммой, которая вычисляет факториал числа, записанного в регистр R0. При выполнении в пошаговом режиме (клавиша F7) наблюдайте, как изменяется регистр SP и содержимое стека.
Программа:
Решите задачу предыдущего пункта, используя подпрограмму без рекурсии.
Программа:
|
Скачать 379 Kb.