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

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

Ответы

На рис. 30 и 31 показаны решения для двух последних головоломок «Улей».

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

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

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

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

Решите это!

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

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

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

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

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

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

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

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

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

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

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

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

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

Почему это легко?

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

Почему задача экскурсовода легкая? Карта метро дает важную информацию, незначительные детали опущены. Это хороший пример абстракции — решение легко увидеть. Без карты было бы сложнее, даже если бы мы знали, где что находится. Карта метро — особый способ предоставления информации. Это особый вид схемы под названием граф. В информатике под графом подразумевают несколько кружков (мы называем их вершинами графа) и линий, которые их объединяют (ребра графа). Вершины и ребра представляют те аспекты данных, которые нас интересуют. Ребра показывают, какие вершины объединены таким образом, что это важно для решения нашей задачи. Туристические достопримечательности, вероятно, соединены автомобильными дорогами, но по-другому. В этом случае граф пути был бы другим — и он понадобился бы нам, если бы мы организовывали автобусный тур!