Вычислительное мышление: Метод решения сложных задач | страница 47
Теперь внимательно посмотрите на чистый вариант графа. Мы перечертили его, не меняя ребер и вершин, и он выглядит в точности как схема метро. Единственная разница — в обозначениях вершин. Цифры вместо названий.
Теперь видно, что эти задачи можно и что они не просто похожи, но в точности одинаковы. Если у вас есть решение для одной задачи (алгоритм, позволяющий найти ответ), значит, есть и для другой! Все, что нужно сделать, — поменять обозначения. версия алгоритма подойдет для обеих головоломок, и ничего не придется делать заново.
На рис. 36 показано, как поменять обозначения на графе одной из наших задач, чтобы он подошел для другой. Еще на нем видно, как перевести решение одной задачи в решение другой. Обозначение каждого шага в алгоритме для одной из задач нужно заменить на соответствующее в другой.
Итак, если мы нашли следующее решение для задачи экскурсовода:
1. Отель.
2. Научный музей.
3. Магазин игрушек
4. Колесо обозрения.
5. Парк.
6. Зоопарк.
7. Аквариум.
8. Художественный музей.
9. Музей восковых фигур.
10. Военный корабль.
11. Замок.
12. Собор.
13. Отель,
то, используя таблицу, сразу же найдем решение для «Хода конем»:
1. Поле 1.
2. Поле 9.
3. Поле 3.
4. Поле 11.
5. Поле 5.
6. Поле 7.
7. Поле 12.
8. Поле 4.
9. Поле 10.
10. Поле 2.
11. Поле 8.
12. Поле 6.
13. Поле 1.
Эта таблица — еще один вид информации или в виде С ее помощью вы легко найдете эквивалент поля из «Хода конем» в списке достопримечательностей из задачи для экскурсовода. Но стоит заметить, что искать поле, соответствующее достопримечательности, не очень удобно. Было бы гораздо лучше, если бы достопримечательности стояли в алфавитном порядке.
Схема на рис. 37 — еще одно представление той же информации, полученное методом наложения. Также она показывает единое решение (для обеих задач). Конечно, поскольку решений может быть много, вы можете прийти к какому-то другому, но и тогда оно подойдет для обеих задач.
Итак — вероятно, это удивит вас, — две разные вроде бы задачи оказались одинаковыми и с одним решением (после ). Решив одну, вы сразу решили и другую! Это открытие происходит после выбора подходящих и подходящего двух задач ( в виде графа).
Мосты Кенигсберга
Вот еще одна головоломка, над которой стоит поразмыслить. На рис. 38 показана карта города с рекой, протекающей через него, двумя островами и семью мостами через реку.
