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

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

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

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

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

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

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

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

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

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

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

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