Работа 2.2 Упр.11 ГДЗ Семакин 10 класс (Информатика)

Задача

На информационной ленте машины Поста помечена 2п — 1 клетка. Составить программу отыскания средней помеченной клетки и стирания метки в ней.

Подробный ответ

На ленте отмечено $$2p-1$$ клеток, значит число помеченных клеток нечётное. Средняя помеченная клетка находится ровно посередине между первой и последней.

Чтобы найти её, удобно:

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

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

1. →
2. ?
3. 1
4. →
5. 0
6. →
7. ?
8. 1
9. ←
10. ?
11. 0
12. ←
13. ?
14. →
15. 0
16. →
17. ?
18. →
19. ?
20. ←
21. 0
22. ←
23. ?
24. !

Смысл программы: она последовательно «сжимает» набор помеченных клеток, удаляя крайние попарно, пока не останется одна средняя клетка, после чего в ней стирается метка.