Вычислительное мышление. Метод решения сложных задач - Питер Макоуэн

Задача «Ход конем»

В головоломке «Ход конем» один шахматный конь может передвигаться по небольшой доске в форме креста. Конь ходит на два поля в любом направлении, а потом на одно поле перпендикулярно этому направлению или наоборот. Он переходит на новое поле, не останавливаясь на полях между начальным и конечным, и всегда должен оставаться в пределах доски. Возможные первые ходы в головоломке показаны на рис. 32.

Вам нужно найти последовательность ходов, начиная с поля 1, чтобы конь побывал на всех полях ровно один раз и вернулся в исходную точку.

Решите это!

Попробуйте решить задачу «Ход конем», замерив, сколько времени у вас уйдет. При этом недостаточно, чтобы конь прошел заданный путь. Необходимо найти алгоритмическое решение, а не просто двигать фигуру по доске. Для этого нужно записать серию перемещений, которые приведут к ответу. То есть придется применить алгоритмическое мышление и вывести алгоритм для решения головоломки. Этот алгоритм можно записать в виде списка номеров, присвоенных полям, на которые ходит конь, в порядке прохождения. Или же записать алгоритм как серию команд вроде «перейти с поля 1 на поле 9». Решать вам.

Как только у вас появится работающий алгоритм, оцените его: проверьте, действительно ли работает это решение, опробовав его на практике. Следуйте собственным инструкциям, отмечая клетки по мере того, как их обходит конь. Таким образом вы сможете гарантировать, что он не нарушает правила и посещает каждую клетку ровно один раз. Если головоломка решена, прекрасно! Если нет, не беспокойтесь — ниже мы посмотрим, как облегчить эту задачу. Но сначала давайте попробуем решить задачу полегче.

Задача экскурсовода

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

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

Как и в случае с «Ходом конем», задача — найти алгоритмическое решение. Убедитесь, что ваше решение действительно работает. Сколько времени у вас ушло? Оказалась ли эта задача легче, чем предыдущая (то есть вы решили ее быстрее)?

Что необходимо?

Почему важно проверить, верно ли ваше решение? Ну конечно, вам не хотелось бы отправиться на экскурсию и в конце дня обнаружить, что вы пропустили важную достопримечательность. Кому хочется разбираться с недовольными туристами!

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

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

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

Для задачи экскурсовода нужно проверить, удовлетворяет ли итог следующим требованиям.