Текст книги "Вычислительное мышление: Метод решения сложных задач"

Другие головоломки

Еще один простой «Улей»

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

Головоломка посложнее

На рис. 29 показана еще одна головоломка, значительно больше и сложнее. Решая ее, выводите новые правила – те, что пригодятся при решении этой головоломки, и те, что могут пригодиться в будущем.

СОВЕТ. Когда будете искать новое правило, обратите внимание на то, что происходит, когда области из трех шестиугольников граничат друг с другом.

Логическое мышление и опыт

Важность логики

Какую роль логическое мышление играет в информатике? Центральную. Работа компьютеров основана на логике, а значит, чтобы программировать их, давать им указания, нужно мыслить логически. В противном случае вы с большой вероятностью ошибетесь.

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

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

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

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

Специалисты за работой

Чем больше у нас опыта в разгадывании головоломок, тем больше правил накапливается в уме и тем быстрее и легче мы решаем новые задачи. Именно так гроссмейстеры играют в шахматы. Они видят в текущих позициях ситуации, похожие на те, что им уже встречались, и делают ход, подсказанный опытом. Это позволяет не перебирать огромное количество ходов наперед, что у человека происходит медленно и порой с ошибками. Компьютеры играют именно так – перебирают массу вариантов и смотрят, какие будут последствия. Люди-шахматисты играют гениально, потому что используют как логическое мышление, так и сопоставление с образцом; кроме того, у них накопилась масса неформальных правил.

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

Если вы хотите стать специалистом в любой области, развивайте навыки сопоставления с образцом и обобщения. Есть универсальный принцип, который позволяет овладеть любым навыком до уровня гения и стать невероятно успешным, – нужно потратить 10 000 часов на тренировки. Столько времени тратят на занятия скрипачи-виртуозы. Подобным образом самые успешные программисты (те, кто стал миллиардерами) примерно столько учились писать программы. Даже тибетские монахи, известные безмятежностью и способностью сострадать, практиковали медитацию примерно столько же времени, чтобы достичь внутреннего покоя.

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

Ответы

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

Глава 5
Головоломные маршруты

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

Две задачи

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

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

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

Решите это!

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

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

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

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

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

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

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

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

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

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

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

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

1. Экскурсия начинается в отеле.

2. Туристы посещают все достопримечательности.

3. Они не проходят одно и то же место дважды.

4. Экскурсия завершается в отеле.

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

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

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

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

Это не важно!

Нас интересует, какие у нас есть достопримечательности (наши вершины) и какие из них соединены друг с другом линиями метро (наши ребра). Другие особенности этих мест нас не интересуют, поэтому мы их игнорируем. Мы опускаем их точное расположение, расстояние друг от друга, соединения автодорог и многие другие вещи, которые не относятся к нашей задаче – понять, как объехать все это на метро. Граф – это абстракция реального города. Мы спрятали все лишние детали, не нужные для построения графа. Здесь отражена только важная информация. Поэтому нам легко увидеть действительно необходимое для решения. Это хорошее представление текущей задачи.

Упрощаем

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

Циклы

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

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

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

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

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

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

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

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

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

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

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

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

Создаем граф

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

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

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

Идем вглубь

Способ исследования всех возможных ходов с целью нарисовать граф называется поиском в глубину: мы исследуем пути до самого конца, например продвигаясь через 1 – 9 – 3 – 11… до конца, потом сохраняем этот путь и пробуем другие. Альтернативный вариант (под названием поиск в ширину) подразумевает рисование всех ребер, исходящих из вершины, и всех вершин, к которым они ведут, перед перемещением к новой вершине. Используя этот метод, мы могли бы нарисовать все ребра из вершины 9, потом все ребра из вершины 6 – и так далее. Это два разных алгоритма для исчерпывающего исследования графа – два разных алгоритма обхода графа. Как только вы осознаете, что задачу можно представить в виде графа, то используйте любой из этих алгоритмов в качестве упорядоченного способа исследования графа и, соответственно, задачи.

Чистота и порядок

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

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

Одна задача, одно решение

Теперь внимательно посмотрите на чистый вариант графа. Мы перечертили его, не меняя ребер и вершин, и он выглядит в точности как схема метро. Единственная разница – в обозначениях вершин. Цифры вместо названий.

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

Сопоставление схем

На рис. 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 показана карта города с рекой, протекающей через него, двумя островами и семью мостами через реку.

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

Похожую задачу о мостах города Кенигсберга в XVIII веке решил математик Леонард Эйлер. В своем решении он впервые ввел идею графов. В итоге они стали одним из ключевых вычислительных инструментов как в математике, так и в информатике. Ученые Викторианской эпохи Чарльз Беббидж и Ада Лавлейс, написавшие первые компьютерные программы, попытались решить ее в XIX веке. Нарисуйте граф для задачи и посмотрите, сможете ли решить ее, прежде чем читать дальше.

Мыслим логически

Вычислительное мышление подразумевает умение мыслить логически. Хорошее представление информации помогает в этом, потому что позволяет убрать ненужное и сосредоточиться на главном. Именно это и обнаружил Леонард Эйлер, когда решал задачу «Мосты Кенигсберга» и пришел к мысли нарисовать граф (рис. 39). Граф помог ему увидеть задачу предельно ясно.

Глядя на граф, Эйлер осознал, что найти ответ невозможно. Почему? Подходящий маршрут должен затронуть все вершины и обойти все ребра, но только один раз (поскольку ребра – это мосты, а нам сказали, что по каждому мосту можно пройти один раз). Давайте предположим, что такой маршрут существует, и, чтобы его показать, нарисуем пунктирные линии со стрелками вдоль ребер. Все ребра должны входить в маршрут, а значит, все они должны совпасть с пунктирными стрелками. Возьмем вершину на этом маршруте, как показано на рис. 40. На каждую пунктирную стрелку, направленную от нее, должна приходиться пунктирная стрелка, направленная к ней. В противном случае маршрут зайдет в тупик – когда пойдет по лишнему ребру, над которым не будет пунктирной стрелки. Из этого тупика не получится выйти без возвращения на уже пересеченный мост. То же относится и к любой вершине. Поэтому, чтобы искомый маршрут был возможен, у всех вершин должно быть четное число связанных с ними ребер.

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