Составить программу на машине Поста

Что такое остаток от деления a на b? Это число, определяемое формулой r = a – d * b, 0 <= r < b. То есть, чтобы получить r, надо из а последовательно вычитать b, пока не получим значение меньше b.

Возникает вопрос, как узнать, что результат вычитания меньше b. Для этого будем вычитать по 1, заодно отмечая, сколько единиц вычли. Если вычли b единиц, то вычитание прошло успешно, начинаем новое. Если же в какой-то момент уменьшаемое стало 0, значит, вычли меньше b единиц, а количество вычтенных единиц и даёт остаток.

Пусть на ленте записаны делимое и через пробел делитель, каретка стоит над самым левым символом делимого. Отмечать, сколько единиц вычли, будем с помощью указателя в делителе. Раз делитель задаётся массивом меток, то указатель в нём будет отсутствием метки, «дыркой».

А1. Перейти на пробел между делимым и делителем.
А2. Сдвинуться вправо до конца делителя.
А3. Передвинуть указатель влево.
А4. Перейти на пробел между делимым и делителем.
А5. Если слева нет делимого (уменьшаемое равно 0), перейти на А11.
А6. Сдвинуться влево до конца делимого.
А7. Стереть крайнюю метку делимого (то есть уменьшить делимое на 1).
А8. Перейти на пробел между делимым и делителем.
А9. Сдвинуться вправо до указателя.
А10. Перейти на А3.
А11. На этом шаге делимое 0, а в делителе справа от указателя столько меток, сколька раз мы вычли единицу, то есть искомый остаток. Осталось только стереть делитель слева от указателя и поставить каретку на левый символ остатка.

Переведём этот алгоритм в условню запись машины Поста.

Ш1. Вправо, пока метка.
Ш2. Вправо, пока метка.
Ш3.1. Влево.
Ш3.2. Если пусто (делитель закончился), перейти к Ш2.
Ш3.3. Стереть метку.
Ш4. Влево, пока метка.
Ш5.1. Влево.
Ш5.2. Если пусто, перейти к Ш11.1.
Ш6. Влево, пока метка.
Ш7.1. Вправо.
Ш7.2. Стереть метку.
Ш8. Вправо, пока метка.
Ш9.1. Вправо, пока метка.
Ш9.2. Поставить метку.
Ш10. Перейти к Ш3.1.
Ш11.1. Вправо (на начало делителя).
Ш11.2. Стирать вправо, по не пусто (очищаем делитель слева от указателя).
Ш11.3. Вправо (пропускаем указатель).
Ш11.4. Стоп.

Ну и сама программа.

1. ВПРАВО
2. ? 3,1
3. ВПРАВО
4. ? 5,3
5. ВЛЕВО
6. ? 3,7
7. СТЕРЕТЬ
8. ВЛЕВО
9. ? 10,8
10. ВЛЕВО
11. ? 21,12
12. ВЛЕВО
13. ? 14,12
14. ВПРАВО
15. СТЕРЕТЬ
16. ВПРАВО
17. ? 18,16
18. ВПРАВО
19. ? 20,18
20. ПОСТАВИТЬ 5
21. ВПРАВО
22. ВПРАВО
23. ? 25,24
24. СТЕРЕТЬ 22
25. ВПРАВО
26. СТОП

1. Устанавливаем курсор на самую левую метку.
2. Повторяем 5 раз: Если текущая клетка пуста - СТОП. Иначе сдвигаемся вправо.
3. Повторяем 5 раз: Сдвигаемся влево.
4. Повторяем 5 раз: Стираем метку и сдвигаемся вправо.
5. Переходим к пункту 2.

Но расписывать это всё в виде команд МП - слишком нудно и тупо.

Хорошего дня тебе

Для того, чтобы составить программу на машине Поста, нужно описать последовательность действий, которые выполняются на ленте.

Первым шагом мы запишем на ленту два числа: делимое и делитель. Например, 7 и 5. Для этого мы будем использовать разделительные символы, чтобы отделить числа друг от друга.

Далее мы будем использовать следующую последовательность команд:

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

Перемещаем указатель на ленте к следующему разделительному символу.

Записываем на ленту оставшееся число.

Выводим на экран значение остатка от деления.

Ниже приведена программа на машине Поста, которая выполняет деление с остатком:

 0:    7 5 # 

1:    : 7 5 # 

2:    [ 3 5 # 

3:    - 2 5 # 

4:    : 2 5 # 

5:    [ 0 5 # 

6:    ! 2 # 

 

Где:

: - разделительный символ
# - символ конца строки
[ - команда "пока"
- - команда "вычитание"
] - закрытие команды "пока"
! - команда "вывод"
Программа начинается со строки 0, на которой записаны числа 7 и 5 с разделительным символом между ними. Затем программа переходит к строке 1, где указатель устанавливается на разделительный символ, и начинается цикл команды "пока".

На строках 2-5 выполняется вычитание второго числа из первого до тех пор, пока первое число не станет меньше или равно второму. После этого программа переходит к строке 6, где происходит вывод остатка от деления.