Задача 1. На ленте машины Поста расположен массив из N меток. Составить программу, действуя по которой машина выяснит, делится ли число на 3. Если да, то после массива через одну пустую секцию поставить метку V . В начальном состоянии каретка обозревает крайнюю левую метку массива.

Алгоритм

1. Известно, что вначале каретка обозревает первую слева метку.

2. Проверяем вторую справа ячейку, если она пустая, то число N на 3 не делится. Переходим на пункт 7.

3. Проверяем третью справа ячейку, если она пустая, то число N на 3 не делится. Переходим на пункт 7.

4. Проверяем четвертую срава ячейку. Если ячейка пустая, значит на ленте расположены подряд три метки. Следовательно, число N на 3 делится. Переходим на пункт 5. Если ячейка с меткой, значит на ленте расположено более трех меток, возвращаемся на пункт 2, считая текущую ячейку первой.

5. Делаем шаг вправо, пропуская одну ячейку.

6. Ставим метку.

7. Конец работы.

Задача 2. На ленте машины Поста расположен массив в N отмеченных секций. Необходимо справа от данного массива через одну пустую секцию разместить массив вдвое больший (он состоять из 2* N меток). При этом исходный массив может быть стерт.

Алгоритм. Последовательно удалять одну метку исходного массива и ставить две метки нового массива.

1. Переходим к первой слева метке.

2. Удаляем эту метку.

3. Находим первую пустую ячейку справа от числа.

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

5. Если можно поставить метку, то ставим две метки подряд. Если метка уже есть, то ставим метки в первой справа пустой ячейке.

6. Возвращаемся на пустую ячейку между массивами.

7. Находим удаленную метку.

8. Делаем шаг вправо. Если в ячейке есть метка, то переходим на пункт 2 и начинаем цикл заново. Если в ячейке нет метки, то исходный массив скопирован полностью. Переходим на пункт 9.

9. Находим крайнюю справа метку второго массива. Ставим за ней еще одну метку.

10. Конец работы.

Задача 1. Число k представлено на ленте машины Поста k +1 идущими подряд метками. Найти остаток от деления целого неотрицательного числа k на 3, если известно, что каретка находится справа от заданного числа. Примечание. Если на число делится на три, то должна остаться одна метка, которая обозначает 0.

Алгоритм. В основе алгоритма лежит идея вычитать из числа последовательно по три метки. Как только останется меньше трех меток, то это и будет остаток от деления.

1. Находим первую пустую ячейку справа от числа.

2. Делаем три шага вправо.

3. Проверяем наличие метки. Если метка есть, значит число больше трех. Переходим на пункт 4. Если метки нет, значит число закончилось. Переходим на пункт 5.

4. Возвращаемся назад и удаляем подряд три метки. Переходим на пункт 2.

5. Конец работы.

Задача 1. Число k представляется на ленте машины Поста k +1 идущими подряд метками. Одна метка соответствует нулю. Составить программу копирования исходного числа и прибавления к нему единицы. Каретка расположена над одной из меток, принадлежащих заданному числу k . При этом исходное число должно остаться на ленте.

Алгоритм. Последовательно удалять одну метку исходного массива и ставить одну метку нового массива. В конце поставить в новом массиве еще одну метку.

1. Переходим к первой слева метке.

2. Удаляем эту метку.

3. Находим первую пустую ячейку справа от числа.

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

5. Если можно поставить метку, то ставим. Если метка уже есть, то ставим метку в первой справа пустой ячейке.

6. Возвращаемся на пустую ячейку между массивами.

7. Находим удаленную метку. Ставим ее обратно.

8. Делаем шаг вправо. Если в ячейке есть метка, то переходим на пункт 2 и начинаем цикл заново. Если в ячейке нет метки, то исходный массив скопирован полностью. Переходим на пункт 9.

9. Находим крайнюю справа метку второго массива. Ставим за ней еще одну метку.

10. Конец работы.

Задача 1. На ленте машины Поста расположен массив из N меток. Составить программу, действуя по которой машина выяснит, делится ли число на 3. Если да, то в исходном массиве удаляются метки через одну.

Алгоритм

1. Известно, что вначале каретка обозревает первую слева метку.

2. Проверяем вторую справа ячейку, если она пустая, то число N на 3 не делится. Переходим на пункт 7.

3. Проверяем третью справа ячейку, если она пустая, то число N на 3 не делится. Переходим на пункт 7.

4. Проверяем четвертую срава ячейку. Если ячейка пустая, значит на ленте расположены подряд три метки. Следовательно, число N на 3 делится. Переходим на пункт 5. Если ячейка с меткой, значит на ленте расположено более трех меток, возвращаемся на пункт 2, считая текущую ячейку первой.

5. Находим любую крайнюю метку (левую или правую). 

6. В цикле удаляем каждую вторую метку: делаем шаг, удаляем метку, делаем два шага, если метка есть снова удаляем, опять делаем два шага и так далее, пока удалять станет нечего.

7. Конец работы.

Задача 2. Составить программу нахождения разности двух неотрицательных целых чисел a и b, находящихся на ленте машины Поста. Каретка находится над левой меткой левого числа. Неизвестно, какое число больше: a или b .

Алгоритм основан на поочередном удалении по одной метке у каждого массива до тех пор, пока не закончатся метки одного из них.