Приложение Решения задач о регистровых машинах

упражнение 1

программа 1:

а. Сколько шагов потребуется регистровой машине, чтобы сложить 2 + 5 и получить 7, выполняя программу 1 (считая Кон отдельным шагом)?

Ответ: шесть шагов. Три декремента, два инкремента, одно окончание программы (последний декремент – переход на ноль).

б. Сколько шагов потребуется машине, чтобы сложить 5 + 2?

Ответ: двенадцать шагов. Шесть декрементов, пять инкрементов и одно окончание программы.

1(Какой из этого можно сделать вывод?)

Ответ: порядок содержимого может иметь большое значение, так что вам может показаться необходимым ввести правило всегда помещать меньшее число в регистр 1, но, если для этого вам сначала придется сравнивать два числа, чтобы выяснить, какое из них меньше, в итоге вам потребуется больше шагов, чем для сложения!

упражнение 2

а. Напишите РПА-программу для этого графа потока. (Обратите внимание: поскольку программа разветвляется, вы можете пронумеровать шаги несколькими способами. Неважно, какой из них вы выберете: главное, чтобы на верные следующие шаги указывали команды безусловного перехода.)

б. Что происходит, когда программа пытается вычесть 3 из 3 или 4 из 4?

Программа останавливается с нулем в регистре 4.

в. Какая возможная ошибка предотвращается обнулением регистра 3 перед попыткой вычитания на шаге 3 вместо шага 4?

Если на старте и в регистре 1, и в регистре 2 были нули, в конце программа могла выдать абсурдный ответ (либо – 0, либо число, отличное от 0 и 1, в регистре знака).

упражнение 3

а. Нарисуйте граф потока (и напишите РПА-программу) для умножения содержимого регистра 1 на содержимое регистра 3, поместив ответ в регистр 5.

б. (По желанию) Используя копирование и перемещение, улучшите программу умножения, созданную в задаче а: когда она закончит работу, изначальное содержимое регистра 1 и регистра 3 восстановится, так что вы сможете легко проверить исходные данные и ответы на правильность по завершении программы.

в. (По желанию) Нарисуйте граф потока и напишите РПА-программу, которая изучает содержимое регистра 1 и регистра 3 (не разрушая их!) и записывает адрес (1 или 3) регистра с большим содержимым в регистр 2 или помещает 2 в регистр 2, если содержимое регистров 1 и 3 равно. (После выполнения этой программы содержимое регистра 1 и регистра 3 должно остаться неизменным, а регистр 2 должен показывать, равно ли их содержимое, а если нет, то в каком из регистров содержимое больше.)

упражнение 4 (по желанию)

Нарисуйте граф потока и напишите РПА-программу, которая превращает регистровую машину в простой карманный калькулятор, следующим образом:

а. Используйте регистр 2 для операции:

0 = ADD

1 = SUBTRACT

2 = MULTIPLY

3 = DIVIDE

б. Поместите числа, с которыми будут производиться манипуляции, в регистры 1 и 3.

(Таким образом, 3 0 6 будет означать 3 + 6; 5 1 3 будет означать 5–3; 4 2 5 будет означать 4 * 5; а 9 3 3 будет означать 9 ? 3.) Затем поместите результаты операции в регистры 4–7, используя регистр 4 для знака (где 0 означает +, а 1 означает –), регистр 5 для численного ответа, регистр 6 для возможного остатка в случае деления, а регистр 7 для сообщения об ошибке ввода (либо требовании делить на ноль, либо неопределенной операции в регистре 2).