Читать «Вычислительное мышление: Метод решения сложных задач» онлайн - страница 40

Циклы

В информатике есть особое название для обхода графа, когда вы посещаете каждую вершину ровно один раз и возвращаетесь в начало. Это называется — по имени ирландского физика Уильяма Роуэна Гамильтона. Он изобрел головоломку, по условиям которой нужно было обойти все углы додекаэдра, проходя по его граням.

Одно решение на двоих

Возвращаемся к началу

Возможно, вы уже заметили, что головоломка «Ход конем» и задача экскурсовода очень похожи друг на друга. Если вы записали требования для «Хода конем», то, вероятно, увидели полное совпадение.

1. Тур начинается в заданной точке.

2. Необходимо посетить все точки.

3. Нельзя проходить уже посещенную точку.

4. Необходимо закончить в начальной точке.

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

Итак, задача экскурсовода оказалась легкой, потому что мы представили ее в виде графа. Так почему бы нам не сделать то же самое и с задачей «Ход конем»?

Для этого нужно в большей степени. Чтобы это сделать, необходимо осознать две вещи. Во-первых, не важно, как выглядит доска. Не важно, что поля — это квадраты. Их форма и размер могли бы быть абсолютно любыми. Давайте нарисуем каждое поле в виде кружочка — так же, как достопримечательности изображены на карте метро. Это просто вершины графа.

Во-вторых, какие поля на самом деле находятся рядом друг с другом — тоже не очень важно. Единственное, что имеет значение, — между какими полями конь перемещается. Поэтому давайте соединим линиями любые два кружка, между которыми можно сделать ход. Подобным образом карта метро показывает, между какими достопримечательностями можно переместиться на метро. Это ребра графа.

Создаем граф

Чтобы сделать граф для головоломки «Ход конем», переходите с поля на поле и по мере продвижения рисуйте кружки и линии (вершины и ребра). Если четко выстроить путь, вы ничего не пропустите. Начните с поля 1. Нарисуйте кружок и пометьте его цифрой «1». Теперь с поля 1 можно перейти на поле 9 — значит нужно нарисовать еще один кружок, обозначить его как «9» и соединить их линиями. С поля 9 перейдите на поле 3 и нарисуйте еще один кружок, который пометьте «3» и соедините его линией с кружком 9.

Продолжайте так делать, пока не вернетесь к уже нарисованному кружку. Теперь отойдите на ход назад и попробуйте из этой точки пойти другой дорогой. Если других вариантов, которые вы еще не обозначили, больше нет, вернитесь еще на один ход и попробуйте оттуда. Продолжайте делать так до тех пор, пока не проведете эту операцию (она называется ) до поля 1 и у вас не кончатся варианты. В итоге вы получите схему.