программирование / программирование / ЛАБОРАТОРНЫЕ_РАБОТЫ / ЛР№1_Машина_Поста

Лабораторная работа

Машина Поста

Цель работы: разработка и написание программ для машины Поста.

Оборудование и ПО: компьютер, ОС Windows XP/7, интерпретатор машины Поста (файл …\Algo2000\Algo.exe).

Указание. Каждый студент должен выполнить 2 задания с номерами N₁ = N и N₂ = 25-N+1, где N – номер варианта. Вариант студента определяется по номеру студента в списке группы.

Практические задания

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3