Алгоритмы для исполнителя МНР

(машины с неограниченными регистрами)

Опишем исполнителя МНР. МНР состоит из памяти данных и программной памяти. Ячейки памяти данных называют регистрами и обозначают R0, R1, R2 и т.д. до бесконечности. В каждом регистре может содержаться любое целое неотрицательное число. Число, содержащееся в Rn, или значение регистра Rn будем обозначать r_n. В каждый момент времени только конечное число регистров содержит какие-то числа, т.е. память данных является не бесконечной, а потенциально бесконечной. МНР работает по программе. Программой называется пронумерованная конечная последовательность команд, хранящаяся в программной памяти. Программная память МНР также является потенциально бесконечной. Будем считать, что во всех ячейках, свободных от команд программы записана специфическая команда – Stop, результатом исполнения которой является остановка выполнения программы.

Система команд МНР содержит следующие команды:

1. Команда обнуления.

Команда обнуления записывается Z(n). Команда Z(n) выполняется так: содержимое регистра Rn обнуляется, т.е. r_n становится равным нулю (r_n:=0), содержимое других регистров не изменяется.

Пример 5. Пусть начальная конфигурация МНР имеет вид:

МНР выполнит команду обнуления – Z(3). Результатом будет следующая

конфигурация:

2. Команда прибавления единицы.

Команда прибавления единицы имеет вид S(n). Команда S(n) выполняется так: содержимое регистра Rn увеличивается на единицу, т.е. r_n:=r_n+1, новое значение r_n равно старому значению, сложенному с 1, содержимое других регистров не изменяется.

Пример 6. Пусть начальная конфигурация МНР имеет вид (*). МНР выполнит команду S(4). Тогда новая конфигурация имеет вид:

3. Команда переадресации.

Команда переадресации имеет вид T(m,n). Команда T(m,n) выполняется так: содержимое регистра Rn заменяется числом r_m, содержащимся в регистре Rm, т.е. r_n:=r_m, содержимое других регистров (включая Rm) не изменяется.

Пример 7. Пусть начальная конфигурация МНР имеет вид (**). МНР выполнит команду T(4,2). Тогда новая конфигурация МНР имеет вид:

В МНР есть особый регистр, который назовем счетчиком адресов команд (САК). При запуске программы на выполнение в САК заносится 1. Выполнение каждой команды МНР состоит из четырех этапов:

1. Читается адрес из САК.

2. Запоминается команда из памяти по этому адресу.

3. САК увеличивается на единицу.

4. Выполняется запомненная команда.

МНР выполняет каждую команду программы в 4 этапа, пока не встретит команду Stop.

Команды обнуления, прибавления единицы и переадресации называются арифметическими. После каждой команды типа 1-3 выполняется команда со следующим номером.

4. Команда условного перехода.

В работе алгоритма могут быть моменты, когда предписываются альтернативные действия, зависящие от результата работы алгоритма к этому моменту. В других ситуациях может потребоваться повторить группу команд несколько раз. МНР может выполнять такие процедуры, используя команды условного перехода; они позволяют делать скачки вперед и назад в списке команд. Мы будем использовать команду условного перехода для совершения, например, следующего действия: «Если r₂=r₆, перейди к десятой команде программы, в противном случае, перейди к следующей команде программы». Команда, вызывающая это действие, записывается как J(2,6,10).

Команда условного перехода в общем виде записывается так J(m,n,q). Выполнение команды осуществляется следующим образом: сравнивается содержимое регистров Rm и Rn, если r_m=r_n, то МНР переходит к выполнению q-ой команды исполняемой программы, в САК заносится число q; если r_m¹r_n, то МНР переходит к выполнению команды, следующей в программе за J(m,n,q), САК увеличивается на единицу, содержимое регистров не изменяется. Если условный переход невозможен ввиду того, что в исполняемой программе команд меньше, чем q, то МНР прекращает работу.

С помощью данной команды можно осуществлять и безусловный переход. Для этого команду нужно записать следующим образом: J(m,m,q).

Работа на МНР состоит из следующих этапов:

1. Заполняем регистры памяти данных какими-то числами, т.е. задаем так называемую начальную конфигурацию.

2. Заполняем командами ячейки программной памяти.

3. Записываем в САК единицу, запускаем МНР и она работает так, как было описано выше до тех пор, пока не встретит команду Stop. При этом полученное по окончании работы машины содержимое регистров памяти данных называется конечной конфигурацией.

Примеры алгоритмов

Задача 37. Напишите для исполнителя МНР алгоритм вычисления суммы целых положительных чисел x и y, результат запишите в регистр R0.

Решение. Поместим x в регистр R0, y – в регистр R1, т.е. зададим начальную конфигурацию:

Конечная конфигурация:

Блок-схема алгоритма: Алгоритм вычисления x+y:

1. Z(2)

2. J(1,2,6)

3. S(0)

4. S(2)

5. J(0,0,2)

6. Stop

Исполнение алгоритма при x=3, y=2

Исполнение алгоритма представим в виде последовательности состояний конфигурации МНР после исполнения очередной команды.

Задача 38. Напишите для исполнителя МНР алгоритм определения является ли треугольник с заданными сторонами a, b, c равнобедренным: . Результат запишите в регистр R0.

Решение. Зададим начальную конфигурацию:

Блок-схема алгоритма:

Алгоритм вычисления t:

1. Z(3)

2. J(0,1,6)

3. J(0,2,6)

4. J(1,2,6)

5. J(0,0,7)

6. S(3)

7. T(3,0)

8. Stop

Конечная конфигурация:

Исполнение алгоритма при a=5, b=4, c=4

Задача 39.Напишите для исполнителя МНР алгоритм нахождения большего из трех целых положительных чисел t = max(x,y,z). Результат запишите в регистр R0.