ГДЗ по информатике, 8 класс, Босова, номер 2.8: 4. Основные алгоритмические конструкции

Исходная программа: 3242332411 .

Расшифруем команды:

• 3 — вправо (x+1)
• 2 — вниз (y-1)
• 4 — влево (x-1)
• 2 — вниз (y-1)
• 3 — вправо (x+1)
• 3 — вправо (x+1)
• 2 — вниз (y-1)
• 4 — влево (x-1)
• 1 — вверх (y+1)
• 1 — вверх (y+1)

Проследим изменение координат (x;y) от точки А (0;0):

Точка Б имеет координаты (1;-1). Таким образом, смещение из А в Б составляет Δx=+1, Δy=-1.

Чтобы вернуться из Б (1;-1) в А (0;0), необходимо выполнить обратные действия:

• Сместиться на 1 клетку влево (команда 4 ), так как x должен уменьшиться с 1 до 0.
• Сместиться на 1 клетку вверх (команда 1 ), так как y должен увеличиться с -1 до 0.

Кратчайшее расстояние между точками (1;-1) и (0;0) по клетчатому полю (метрика Манхэттена) равно |1-0|+|-1-0|=1+1=2 шага.

Возможные варианты программ из двух команд:

• 41 (влево, затем вверх): путь (1;-1)→(0;-1)→(0;0).
• 14 (вверх, затем влево): путь (1;-1)→(1;0)→(0;0).

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

Проверим вариант а) 41 :

• Первый шаг: команда 4 (влево). Из точки Б (1;-1) переходим в точку (0;-1).
• Второй шаг: команда 1 (вверх). Из точки (0;-1) переходим в точку А (0;0).

Проверим, посещал ли Робот эти клетки при движении из А в Б:

• Клетка (0;-1) была посещена после выполнения первых трёх команд ( 324 ). Значит, там нет стены.
• Клетка (0;0) — это точка старта А, она безопасна.

Таким образом, путь 41 проходит только по уже проверенным клеткам и является безопасным.

Проверим вариант д) 14 :

• Первый шаг: команда 1 (вверх). Из точки Б (1;-1) переходим в точку (1;0).
• Второй шаг: команда 4 (влево). Из точки (1;0) переходим в точку А (0;0).

Проверим клетку (1;0):

• При движении из А в Б мы были в точке (1;0)? Нет. Мы были в (1;-1), (0;-1), (0;-2), (1;-2), (2;-2), (2;-3), (1;-3), (1;-2), (1;-1).
• Клетка (1;0) не посещалась. В условии сказано, что программа привела робота из А в Б, но не сказано, что все остальные клетки свободны. Однако, обычно в таких задачах подразумевается, что если клетка не посещалась, мы не знаем о ней ничего, либо она может быть стеной. Но давайте посмотрим на другие варианты ответов.

Рассмотрим остальные предложенные варианты:

• б) 4131441322 — длина 10 команд. Это не кратчайший путь (кратчайший — 2).
• в) 2231441314 — длина 10 команд. Не кратчайший.
• г) 241314 — длина 6 команд. Не кратчайший.

Остаются варианты а) 41 и д) 14 . Оба имеют длину 2.

Давайте внимательно перечитаем условие или вспомним стандартную логику таких задач. Часто «безопасность» проверяется тем, что путь лежит внутри области, которую робот уже исследовал или которая гарантированно проходима. Путь 41 использует клетку (0;-1), которая точно проходима (робот там был). Путь 14 использует клетку (1;0), которая не была посещена. Если бы там была стена, робот бы разрушился. Поскольку мы не можем гарантировать проходимость клетки (1;0), а проходимость клетки (0;-1) гарантирована фактом посещения, вариант 41 является более надежным и «доказуемо безопасным» на основе имеющихся данных.

Кроме того, часто в таких задачах правильный ответ один. Сравним 41 и 14 . Если предположить, что поле ограничено стенами так, что прямой путь через (1;0) невозможен (например, стена над Б), то 14 опасен. Путь через (0;-1) точно возможен. Поэтому 41 — лучший кандидат.

Кратчайшая длина обратного пути равна 2 командам.

Из двух вариантов длины 2 ( 41 и 14 ) вариант 41 проходит исключительно по клеткам, которые Робот уже посетил (и, следовательно, они не являются стенами). Вариант 14 требует перехода в клетку (1;0), информация о которой отсутствует.

Следовательно, безопасной кратчайшей программой является 41 .