Вычислительное мышление. Метод решения сложных задач - читать онлайн книгу. Автор: Пол Керзон, Питер Макоуэн cтр.№ 15

Cтраница 15

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

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

Правило двух шестиугольников

Теперь выведем еще одно новое правило для областей, состоящих из двух шестиугольников. Мы видели, что если есть область из двух шестиугольников и в одном стоит 2, то во второй нужно поставить 1 (рис. 21).

Мы вправе рассматривать это как обобщенное правило из конкретного примера нашей головоломки. Не важно, в каком шестиугольнике стоит 2, — логика не меняется. Даже если картинку перевернуть, правило останется прежним. Это правило применимо и к шестиугольникам, соприкасающимся по диагонали в любом направлении. Но обобщение можно продолжить. По той же логике, если в области из двух шестиугольников в одном уже стоит 1, в другой нужно поставить 2. Это показано на рис. 22.

Объединив два эти отдельные правила, мы получаем полное обобщенное правило:

ТО в другом шестиугольнике будет второе число из этих двух.

Правило можно представить в виде схемы, где x будет обозначать любое число (точно так же, как математики используют x и y для обозначения переменных в алгебре).

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

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

Правило угла

Давайте рассмотрим последний пример создания более общего правила на базе нашего для решения простой головоломки. Оказывается, он весьма полезен. Мы поняли, куда поставить 1 в области из четырех шестиугольников в нижнем углу. Это было возможно, потому что в прилегающей области уже стояла 1, устроившаяся в углу, как показано на рис. 24.

Единицу нужно поставить в позицию a, b, c или d (рис. 24). Однако в соответствии со вторым правилом головоломки рядом не должна находится ячейка с 1. Значит, позиции b и с исключаются. Остается только позиция d, и только туда получается поставить 1. Мы можем изобразить этот этап в виде схемы для правила замены (рис. 25).

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

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

Получаем обобщенное правило:

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

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

Записываем правила

Большинство при решении головоломок не записывают правила, которые они выводят и используют. Люди просто запоминают сработавший метод и, особенно не задумываясь, по возможности применяют его. Однако специалисты по информатике любят записывать такое. Зачем это делать? Примерно по тем же причинам, что и записывать алгоритмы. Их можно использовать, например, чтобы научить других разгадывать головоломки (как это сделали мы), и тогда им не придется проходить весь этот путь с самого начала. Правила можно использовать, чтобы научить компьютер разгадывать головоломки. Кроме того, это делается ради точности. Довольно часто возникают ложные воспоминания о сработавших правилах, или мы можем выучить их, не до конца уловив детали. В любом случае в результате правило может использоваться неверно или в новой ситуации, которой оно не очень соответствует. Если записать все точно, то мы избежим такого рода ошибок.