Новый Робот в новых задачах О. Б. Богомолова, Д. Ю. Усенков. - презентация

1 Новый Робот в новых задачах О. Б. Богомолова, Д. Ю. Усенков

2 Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости: При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх, вниз, влево, вправо. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: Цикл ПОКА последовательность команд КОНЕЦ ПОКА выполняется, пока условие истинно. В конструкции ЕСЛИ ТО команда1 ИНАЧЕ команда2 КОНЕЦ ЕСЛИ выполняется команда1 (если условие истинно) или команда2 (если условие ложно) ввер х вни з влев о вправ о сверху свободно снизу свободно слева свободно справа свободно

3 Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится и программа прервётся. Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)? НАЧАЛО ПОКА вправо КОНЕЦ ПОКА ПОКА вниз КОНЕЦ ПОКА КОНЕЦ 1) 8 2) 12 3) 16 4) 20

4 Решение 1. Указанные записи циклов ПОКА аналогичны более коротким: ПОКА вправо КОНЕЦ ПОКА ПОКА вправо ПОКА вниз КОНЕЦ ПОКА ПОКА вниз

5 Решение 2. Внутренние циклы определяют перемещение РОБОТа в соответствующем направлении до препятствия в виде стенки. 3. Внешний цикл означает, что «Г-образное» движение РОБОТа, определяемое двумя внутренними циклами, может быть повторено, если после остановки РОБОТа из-за препятствия снизу выяснится, что справа препятствия нет. 4. Завершение движения РОБОТа – в клетке, которая имеет препятствия (стенки) и снизу, и справа. Причем проверка этого условия производится только после выполнения обоих вложенных циклов. 5. Любой из вложенных циклов ПОКА осуществляет движение РОБОТа до препятствия. Поэтому можно разбить весь лабиринт на полоски «равноправных» клеток: если какая-то из них является решением, то решением являются и все остальные клетки этой полоски, и наоборот.

6 Решение Определяем клетки лабиринта, имеющие стенки и справа, и снизу: Клетка F6 – искомая. Клетки F2 и D5 – «ловушки» для РОБОТа. Разбиваем лабиринт на диапазоны «равноправных» клеток: A1:F1, A2:F2, A3:F3, A4:F4, A5:D5, E5:F5, A6:F6

7 Решение Анализируем диапазон A1:F1: достаточно проанализировать клетку A1: Из всех клеток этого диапазона РОБОТ попадет в «ловушку» - клетку F2.

8 Решение Анализируем диапазон A2:F2: достаточно проанализировать клетку A2: Из всех клеток этого диапазона РОБОТ тоже попадет в «ловушку» – клетку F2.

9 Решение Анализируем диапазон A3:F3: достаточно проанализировать клетку A3: Из всех клеток этого диапазона РОБОТ попадет в нужную клетку F6: 6 решений.

10 Решение Анализируем диапазон A4:F4: достаточно проанализировать клетку A4: Из всех клеток этого диапазона РОБОТ попадет в нужную клетку F6: еще 6 решений.

11 Решение Анализируем диапазон A5:D5: достаточно проанализировать клетку A5: Из всех клеток этого диапазона РОБОТ попадет в «ловушку» – клетку D5.

12 Решение Анализируем диапазон E5:F5: достаточно проанализировать клетку E5: Из всех клеток этого диапазона РОБОТ попадет в нужную клетку F6: еще 2 решения.

13 Решение Анализируем диапазон A6:F6: достаточно проанализировать клетку A6: Из всех клеток этого диапазона РОБОТ попадет в нужную клетку F6: еще 6 решений.

14 Решение Итого (зеленый цвет – клетки, являющиеся решениями; оранжевый цвет – клетки, не являющиеся решениями): Решениями задачи являются: 6 клеток диапазона A3:F3, 6 клеток диапазона A4:F4, 2 клетки диапазона E5:F5 и 6 клеток диапазона A6:F6 (включая саму клетку F6), т. е. всего = 20 ячеек. Ответ: вариант 4.