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

Как мы уже знаем, алгоритмические фокусы и компьютерные программы — по сути, одно и то же. В некоторых фокусах применяются точно такие же алгоритмы, как и в программах, — например, поисковый. Значит, мы вправе применить обобщение и повторно использовать некоторые решения. В описанном фокусе надо было найти 16-ю карту, но на примере перфокарт мы видим, что, если перевести числа в двоичный код и таким образом определить, какую стопку оставить, можно выделить любую карту. А значит, эту идею легко вернуть в мир магии. Например, подготовить фокус, в котором перед показом карту можно положить куда угодно. И это необязательно должна быть 16-я карта! Конечно же, при этом необходимо точно знать, где она находится. Еще надо уметь переводить числа в двоичный код в уме. Проводить математические операции в уме — полезный навык и для фокусника, и для ученого-информатика!

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

Выберите стопку

Давайте посмотрим, как этот принцип работает в «Сне об австралийском маге». Как мы увидели на примере перфокарт, он работает, потому что на каждом этапе мы сбрасываем и оставляем некий набор чисел в зависимости от их представления в двоичной системе. На первом этапе уходят перфокарты с нечетными числами, то есть с 1 в первой позиции двоичного кода (в первом колонке) — это 1, 3, 5, 7, … (0001, 0011, 0101, 0111, …). В следующем раунде мы отбрасываем числа 2, 6, … Это карты с 1 во второй позиции двоичного кода (во втором колонке), то есть 0010, 0110, … Это не все карты, у которых есть 1 в этой позиции, потому что некоторые мы уже отбросили. Давайте перечислим все такие карты. У нас получится более длинный список: 2, 3, 6, 7, 10, … (0010, 0011, 0110, 1111, 1010, …). В следующий раз избавляемся от карт с 1 в третьей позиции двоичного кода (колонке четверок). В полный список войдут 4, 5, 6, 7, 12, … (0100, 0101, 0110, 0111, 1100, ...). Теперь стоит отметить, что мы наблюдаем здесь еще одну модель. Первое число в каждом списке карт указывает на колонку в двоичном коде, которой соответствует весь список.

На этом основан еще один фокус. Сделайте стопку карт, на которых написаны числа 1, 3, 5, 7, 9, 11, 13, 15. Сделайте еще одну стопку карт, с числами 2, 3, 6, 7, 10, 11, 14, 15. Сделайте третью стопку, с 4, 5, 6, 7, 12, 13, 14, 15. И наконец, четвертую, с 8, 9, 10, 11, 12, 13, 14, 15. Перетасуйте карты в каждой стопке. Сами стопки могут идти в любом порядке.

Теперь попросите добровольца задумать число от 1 до 15 и запомнить его, но не говорить вам. Возьмите одну из стопок и сдавайте карты по одной. Объясните, что вы читаете мысли человека, который смотрит на карты, даже не глядя на него. Вам достаточно смотреть на карты. Когда вы закончите сдавать карты, попросите добровольца сказать, было ли задуманное число в этой стопке, что является «дополнительной проверкой на детекторе лжи», которая поможет вам настроиться на его мысли. Если доброволец скажет, что число было в стопке, отложите карты в сторону. Если нет, оставьте их на месте. Повторите эту процедуру с каждой стопкой.

После четвертой стопки назовите число, которое задумал доброволец! Как же вы это сделали?

Достаточно запомнить самое маленькое число в каждой отложенной стопке. Сложите их, и получится число, которое задумал человек. Почему? Эти самые маленькие числа отражают разряд в двоичном коде, который есть во всех картах из этой стопки. Так, если стопка отброшена, то загадочное число имеет 1 в этом разряде. Сложите эти малые значения, и вы переведете число из двоичного кода в десятичный. Например, если сброшены стопки 1 и 4, это значит, что искомое число — 0101 в двоичном коде или 5 в десятичном (0 × 8 + 1 × 4 + 0 × 2 + 1 × 1 = 4 + 1 = 5).

Таким образом, у вас появился новый фокус на основе той же математической модели, что и предыдущий.

Примечание фокусника

Считается, что принцип 16-й карты стал известен в 1958 г., когда программист и известный фокусник Алекс Элмсли опубликовал фокус «7–16» в журнале фокусников Ibidem. Он известен в среде фокусников благодаря манипуляции с картами, названной в его честь «счет Элмсли».

От фокусов к программам и наоборот

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

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

Логические головоломки

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

Говоря о логическом мышлении, в определенном отношении мы подразумеваем способность мыслить ясно и учитывать даже небольшие детали. Однако есть и более глубокий смысл — умение работать с математической логикой, и если вы им обладаете, то будете успешно выдвигать неопровержимые аргументы. Логически обоснованные аргументы неоспоримы, и еще древнегреческие философы осознали их важность. Умение найти неоспоримые аргументы полезно людям любых профессий, а не только программистам. Это нужно и для решения головоломок, только здесь оно сведено к чистой логике. Как и любой другой навык, логическое мышление можно освоить и улучшить. Для этого необходима практика (надо много тренироваться, как и в любом другом случае), разгадывание головоломок — приятный способ ее получить. Чем больше вы решаете головоломок, тем больше полезных хитростей подскажет вам вычислительное мышление.

Соты в улье

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