Приложение Е

Задачи для самостоятельного решения по теме «Машина Поста»

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

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

3. На информационной ленте машины Поста расположено N массивов меток, отделенных друг от друга свободной ячейкой. Каретка находится над крайней левой меткой первого массива. Определите число массивов.

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

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

6. Составьте программу сложения двух целых неотрицательных чисел а и Ь, расположенных на ленте машины Поста. Каретка расположена над одной из меток, принадлежащих числу а. Число b находится правее числа а через несколько пустых секций.

7. Составьте программу сложения произвольного количества целых неотрицательных чисел, записанных на ленте машины Поста на расстоянии одной пустой секции друг от друга. Каретка находится над крайней левой меткой левого числа.

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

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

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

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

12. На ленте машины Поста расположен массив из 27V—1 меток. Составьте программу отыскания средней метки массива и стирания ее.

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

14. На информационной ленте машины Поста находятся два массива в М и N меток. Составьте программу выяснения, одинаковы ли массивы по длине.

15. Задача В. А. Успенского. На информационной ленте либо вправо, либо влево от секции, над которой расположена каретка, находится массив меток. Расстояние до массива выражается произвольным числом. Необходимо составить программу, работая по которой машина Поста найдет этот массив и установит каретку на начало этого массива.

16. Составьте программу умножения двух чисел а и Ь.

17. На ленте машины Поста находится п массивов меток, после последнего массива на расстоянии более трех пустых секций находится одна метка. Массивы разделены тремя пустыми ячейками. Количество меток в массивах не может быть меньше двух. Произвести обработку массивов следующим образом: если количество меток в массиве кратно трем, то стереть метки в данном массиве через одну, иначе – массив стереть полностью. Каретка находится над крайней левой меткой первого массива.

18. На ленте изображено п массивов меток, отделенных друг от друга одной свободной ячейкой. Каретка находится над первой меткой первого массива. Определите количество массивов.

19. На ленту машины Поста нанесены два массива меток на некотором расстоянии друг от друга. Соедините эти два массива в один. Каретка находится над крайней левой меткой левого массива.

20. На ленте машины Поста отмечен массив и меток. Найдите число 2п + 1 и проверьте, делится ли оно на 3. Если да, то после числа через одну пустую секцию, поставьте две метки, если нет – поставьте три метки. Каретка находится над крайней левой отмеченной секцией.

21. Дан массив меток. Каретка обозревает первую пустую секцию перед началом массива. Раздвиньте массив так, чтобы после каждой метки была пустая секция.

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

23. Найти НОД двух чисел, находящихся на ленте машины Поста. Между этими числами находится произвольное количество пустых секций. Каретка находится над левой меткой левого числа.

24. На ленте машины Поста находятся п массивов меток. Каретка находится где-то над первым массивом. Удалите все массивы с четными номерами (соседние массивы разделены тремя пустыми секциями).

25. На информационной ленте машины Поста находится массив меток. Каретка находится где-то над массивом (но не над крайней меткой). Сотрите все метки, кроме крайних, таким образом, чтобы положение каретки при этом не изменилось.