Номер 11, страница 37, часть 2 - гдз по математике 2 класс учебное пособие - тетрадь Петерсон

Урок 12. Плоские поверхности предметов. Плоскость. Часть 2 - номер 11, страница 37.

Условие 2023.

11* Игра «Путь садовника»

На рисунке дан план небольшого яблоневого сада (точки – яблони).

Садовник обработал все яблони подряд. Начал он с клетки, отмеченной звёздочкой, и обошёл одну за другой все клетки – как занятые яблонями, так и свободные. При этом он ни разу не возвратился на пройденную клетку. По диагонали он не ходил и на закрашенных клетках не был, так как там помещались различные строения. Закончив обход, садовник оказался на той же клетке, с которой начал свой путь. Начерти путь садовника.

Решение 2 (2023).

Задача заключается в поиске так называемого Гамильтонова цикла на графе, вершинами которого являются клетки сада, а рёбрами — возможные переходы между ними. Садовник должен посетить каждую из 60 доступных клеток ровно один раз и вернуться в исходную точку. Закрашенные клетки (строения) и диагональные ходы запрещены.

Проблема относится к классу NP-полных задач, поэтому для её решения обычно используются методы перебора с возвратом (бэктрекинг). Однако для данной конфигурации поля существует единственное решение. Путь садовника представляет собой сложную траекторию, которая обходит все препятствия и покрывает всё поле целиком.

Ниже представлен план сада с начерченным маршрутом садовника, который удовлетворяет всем условиям задачи.

Путь садовника

Ответ: Маршрут садовника показан на рисунке красной пунктирной линией. Он начинается в клетке со звёздочкой, обходит все 60 разрешённых клеток по одному разу и возвращается в начальную клетку.

Условие 2020-2022.

11* Игра «Путь садовника»

На рисунке дан план небольшого яблоневого сада (точки — яблони).

Садовник обработал все яблони подряд. Начал он с клетки, отмеченной звёздочкой, и обошёл одну за другой все клетки — как занятые яблонями, так и свободные. При этом он ни разу не возвратился на пройденную клетку. По диагонали он не ходил и на закрашенных клетках не был, так как там помещались различные строения. Закончив обход, садовник оказался на той же клетке, с которой начал свой путь. Начерти путь садовника.

Решение 2020-2022.