Игра в Робота (I)
| Постусловием цикла (P) называется отрицание его условия (C), то есть P = не C. Инвариантом цикла (I) — утверждение, верное до и после любого выполнения цикла. Нас интересуют I такие, что утверждение I и не P является тем, что мы хотим доказать. Таким образом, для доказательства правильности работы программы необходимо сформулировать, что делает каждый ее цикл, доказать, что он нормально завершается, при необходимости предъявить соответствующий инвариант и доказать его индукцией по проходам цикла. |
Задачи
1.
Дано: Робот в огороженном прямоугольнике.
Надо: Робот у северной стены.
2.
Дано: Робот в огороженном прямоугольнике.
Надо: Робот в верхнем левом углу.
3.
Дано: Робот в нижней (южной) клетке огороженного коридора шириной в одну клетку.
Надо: Все клетки коридора закрашены.
Примечание: Желательно найти два решения с различными инвариантами.
4.
Дано: Робот в в левом нижнем углу прямоугольника.
Надо: Прямоугольник закрашен.
5.
Дано: Робот в нижней клетке незакрашенного коридора шириной в одну клетку..
Надо: Клетки закрашены через одну, начиная с первой.
6.
Дано: Робот в левом нижнем углу огороженного незакрашенного прямоугольника.
Надо: Прямоугольник закрашен в шахматном порядке; левая нижняя клетка закрашена.
Примечание: Высота или ширина прямоугольника (или обе) могут быть равны 1.
7.
Дано: Робот у нижней стены огороженного прямоугольника, внутри которого только горизонтальные стены, все находящиеся на одной широте.
Надо: Робот у верхней границы..
8.
Дано: Робот у нижней стены огороженного прямоугольника, внутри которого только горизонтальные стены, не нарушающие связности.
Надо: Робот у верхней границы.
9.
Дано: В огороженном прямоугольнике есть вертикальные и горизонтальные стены, не примыкающие к границе прямоугольника и друг к другу.
Надо: Робот в верхнем левом углу прямоугольника.
10.
Дано: В огороженном прямоугольнике возможно есть внутренние стены, но ни одна горизонтальная внутренняя стена не примыкающие к вертикальной внутренней (к границе примыкать могут) и не нарушающие связности.
Надо: Робот в верхнем левом углу прямоугольника.
11.
Дано: В огороженном прямоугольнике есть не примыкающая к границе огороженная со всех сторон клетка; других стен нет, Робот в левом нижнем углу прямоугольника.
Надо: Робот в клетке, соседней с огороженной.
Тексты программ.