Книга: Насосы интуиции и другие инструменты мышления
Назад: XI. Что осталось за кадром
Дальше: Источники
Приложение
Решения задач о регистровых машинах
упражнение 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).
Назад: XI. Что осталось за кадром
Дальше: Источники
