Робот 1

Игра в Робота (I)


Постусловием цикла (P) называется отрицание его условия (C), то есть P = не C. Инвариантом цикла (I) — утверждение, верное до и после любого выполнения цикла. Нас интересуют I такие, что утверждение I и не P является тем, что мы хотим доказать. Таким образом, для доказательства правильности работы программы необходимо сформулировать, что делает каждый ее цикл, доказать, что он нормально завершается, при необходимости предъявить соответствующий инвариант и доказать его индукцией по проходам цикла.


Задачи

1.

Дано: Робот в огороженном прямоугольнике.
Надо: Робот у северной стены.

2.

Дано: Робот в огороженном прямоугольнике.
Надо: Робот в верхнем левом углу.

3.

Дано: Робот в нижней (южной) клетке огороженного коридора шириной в одну клетку.
Надо: Все клетки коридора закрашены.
Примечание: Желательно найти два решения с различными инвариантами.

4.

Дано: Робот в в левом нижнем углу прямоугольника.
Надо: Прямоугольник закрашен.

5.

Дано: Робот в нижней клетке незакрашенного коридора шириной в одну клетку..
Надо: Клетки закрашены через одну, начиная с первой.

6.

Дано: Робот в левом нижнем углу огороженного незакрашенного прямоугольника.
Надо: Прямоугольник закрашен в шахматном порядке; левая нижняя клетка закрашена.
Примечание: Высота или ширина прямоугольника (или обе) могут быть равны 1.

7.

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

8.

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

9.

Дано: В огороженном прямоугольнике есть вертикальные и горизонтальные стены, не примыкающие к границе прямоугольника и друг к другу.
Надо: Робот в верхнем левом углу прямоугольника.

10.

Дано: В огороженном прямоугольнике возможно есть внутренние стены, но ни одна горизонтальная внутренняя стена не примыкающие к вертикальной внутренней (к границе примыкать могут) и не нарушающие связности.
Надо: Робот в верхнем левом углу прямоугольника.

11.

Дано: В огороженном прямоугольнике есть не примыкающая к границе огороженная со всех сторон клетка; других стен нет, Робот в левом нижнем углу прямоугольника.
Надо: Робот в клетке, соседней с огороженной.

Тексты программ.