Механизм предсказания будущего

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

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

Перейдем к тому, что видит аудитория. Вызовите добровольца. Распределите карты в одну линию на столе лицом вверх, чтобы зрители видели, что это обычная перетасованная колода. Объявите, что сначала вам нужно поделить колоду примерно пополам. Попросите добровольца выбрать любую карту примерно посередине и покажите руками, что вы имеете в виду. Вы обязательно должны сделать так, чтобы ваши руки оказались над 16-й и 32-й картами. Таким образом вы ненавязчиво ограничиваете выбор до какого-то варианта между ними. Сбросьте карты справа от той, которую укажет доброволец (нижнюю часть колоды), и попросите его подтвердить, что это был свободный выбор. Возьмите оставшиеся карты и, держа их рубашкой вниз, объясните, что ночью перед выступлением вам всегда снятся странные сны, в которых маги учат вас новым фокусам. Накануне во сне к вам явился австралийский маг и научил методу «шиворот-навыворот», позволяющему угадывать карту, о которой никак нельзя было знать заранее.

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

Теперь укажите вот на какую странную вещь: в вашем сне австралийский маг сказал, что нужно заранее положить в конверт одну конкретную карту. Попросите добровольца посмотреть под столом и достать из конверта карту, предсказанную австралийским магом в вашем сне. Это тоже восьмерка червей!

Поблагодарите добровольца и попросите аудиторию поаплодировать ему.

Хитрые алгоритмы

Какое отношение фокус имеет к информатике? Здесь мы имеем так называемый самовоспроизводящийся фокус — именно это в информатике называют алгоритмом. Под алгоритмом подразу­ме­вается серия инструкций, которая всегда приводит к конкретному желаемому эффекту, если следовать им в заданном порядке. В данном случае — магический эффект: у вас остается именно предсказанная карта. Компьютерные программы — всего лишь алгоритмы, написанные на языке, который скорее поймет компьютер, чем фокусник. С их помощью программист добивается, чтобы программа выполняла задуманные им действия.

Алгоритм, лежащий в основе «Сна об австралийском маге», показан на рис. 5.

Этот конкретный алгоритм содержит не только шаги, которые надо выполнять последовательно. В нем есть циклы, например «повторите 4 раза». Цикл показывает, что некоторые инструкции надо повторить. Он позволяет не писать одно и то же много раз. Именно такие инструкции программисты используют в компьютерных программах, чтобы компьютер повторил какие-то указания. Есть и второй цикл: «Повторите, пока не останется карт». Этот цикл воспроизводится 4 раза, как указано в первом цикле. Каждый раз вы проходите через всю колоду, оставляя и сбрасывая карты, пока не останется ни одной.

Придумываем фокусы

Чтобы придумать новый трюк, фокусник должен использовать тот же тип мышления, что и ученый-информатик, — а именно вычислительное мышление. Карточный фокус подразумевает вычисления, только они проводятся с помощью колоды карт вместо компьютера. Чтобы изобрести новый фокус, необходимо алгоритмическое мышление. Фокусник должен продумать серию шагов, которые можно повторить и обязательно получить магический эффект. Ему абсолютно необходимо, чтобы фокус получался всегда. Он не хочет глупо выглядеть на сцене, и поэтому нужно продумать все до мельчайших деталей. Необходимо удостовериться, что шаги должны делаться именно в указанной последовательности. Как и в программировании, нужно продумать каждый возможный вариант. Может ли доброволец как-то помешать выполнению фокуса? Если да, нужно знать, что делать в этом случае. Кроме того, следует достаточно точно записать все действия, чтобы в будущем сам фокусник или кто-то другой смог повторить их и успешно показать фокус (хотя маги, в отличие от ученых-информатиков, не склонны раскрывать свои секреты!). Все это — алгоритмическое мышление в действии.

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

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

Все электронные устройства, которые вы когда-либо видели в действии, слепо следуют алгоритму.

Делим на части

Чтобы придумать фокус, например можно составить его из частей, отдельно поработав над каждым шагом и его представлением. Здесь мы снова наблюдаем вычислительное мышление в действии, а именно — декомпозицию. Фокус «Сон об австралийском маге» состоит из четырех основных шагов. Во-первых, нужно подготовить колоду, поместив карты на известные позиции. Во-вторых, нужно сбросить нижнюю часть колоды, создав у добровольца ощущение, что он сам выбирает, как ее поделить, от чего зависит результат (хотя это не так). Следующий шаг — раскладывать карты так, чтобы в итоге осталась одна. И последний шаг — раскрыть предсказание. Если мы запишем фокус в виде алгоритма на этом уровне детализации, то получим что-то вроде изображенного на рис. 6а.

Обратите внимание, что здесь мы прибегли к абстрагированию, то есть прячем детали. В этом описании мы скрыли, как выполняются шаги. Эти детали можно записать в виде отдельного мини-алгоритма. Например, алгоритм для шага, когда мы сбрасываем каждую вторую карту, как показано на рис. 6b.

На самом деле мы уже занимались такого рода абстрагированием для каждого из шагов в начальной версии алгоритма. Зачем? Чтобы вы увидели общую идею и не увязли в подробностях.

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

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

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

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

Всегда ли получается фокус?

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

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

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

Это уменьшает объем необходимых тестов. Нам просто нужно проверить, получается ли фокус вне зависимости от того, как мы делим колоду. Останется ли у нас 16-я карта, независимо от того, куда укажет доброволец? Колоду можно разделить только в 52 местах, поэтому теперь мы знаем, что достаточно проверить 52 случая и посмотреть, всегда ли остается 16-я карта. Возможно, к этому моменту вы уже поняли, что это не всегда срабатывает! Необходимо ограничить промежуток, в рамках которого можно делить колоду…

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 …

Что останется, если мы сбросим каждую вторую карту, начиная с первой? Только четные позиции, а это означает, что 16-я карта останется на месте:

2 4 6 8 10 12 14 16 18 …

Мы снова сбрасываем каждую вторую карту, и остаются следующие позиции:

4 8 12 16 …

а потом

8 16

и, наконец,

16.

Эта модель показывает, что как при большем, так и при меньшем числе карт происходит одно и то же. Очевидно, что 16-я карта остается в любом случае, если убирать каждую вторую.

Однако у нас остается проблема, связанная с «…». Здесь мы наблюдаем важное свойство абстрагирования. Если отбросить важную деталь, то мы, вероятно, получим неправильный ответ. Логическое мышление тоже с легкостью заведет вас не туда, если не продумать в точности все возможные варианты. Если бы в начале фокуса мы разделили колоду в какой-то точке до 16-й карты, то, конечно, эта карта ушла бы при первом разделении. Тогда у нас осталась бы другая карта, например восьмая. Возможно, вы поняли это, как только обратились к абстрагированию. Однако есть еще одна похожая, но немного более тонкая проблема. Давайте снова проведем моделирование, но увеличим масштаб. Результат показан на рис. 7.

Ну и ну. Если взять 32 карты или больше, у нас останется не 16-я карта, а 32-я. Таким образом, даже если мы добьемся того, что 16-я карта не будет сброшена в начале, фокус не сработает, если не подготовиться заранее. Нам нужно добавить еще одно условие. Как показали логические рассуждения, колоду необходимо разделить в каком-то месте после 16-й и перед 32-й картой. Поэтому важно сказать добровольцу, что нужно отбросить «примерно половину». Однако на самом деле подразу­мевается не примерное разделение, а весьма точное — «между 16-й и 32-й картой». Вот почему нужно ограничить руками пространство над 16-й и 32-й картами, чтобы сориентировать добровольца при делении колоды. Это делается для того, чтобы условие, или, как выразился бы программист, входное условие, было выполнено без ведома добровольца.

Итак, мы использовали численное моделирование и логическое мышление и таким образом убедились, что фокус действительно работает, но при условии, что перед тем, как мы начинаем сбрасывать карты, их в колоде минимум 16 и максимум 31. Численное моделирование — это создание моделей вычислительных процессов с целью их изучения. Здесь мы прибегли к моделированию, чтобы посмотреть, всегда ли получается фокус, но подобным образом можно провести и обобщение. Наша модель показывает принцип, лежащий в основе фокуса. Главное в нем — не игральные карты. Мы абстрагировались от них, как и от многих других деталей. Выявив этот базовый принцип, мы можем придумать другие варианты фокуса, основанные на нем. Мы еще вернемся к этому позже.

Перфокарты

Магия успешного поиска

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

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

На рис. 8 приведен пример перфокарты для числа 22. Чтобы увидеть, как использовать перфокарты для поиска данных с помощью магического принципа «шиворот-навыворот», давайте сделаем их сами, а потом посмотрим, как они действуют.

Шаблоны для перфокарт можно скачать здесь: www.cs4fn.org/punchcards/.

Распечатайте их — в идеале прямо на тонком картоне — и слегка посыпьте тальком, чтобы они не склеивались (это важно).

Вместо отверстий и их отсутствия мы будем использовать в нашем коде отверстия и небольшие вырезы. Вам следует сделать вырезы в нужных местах, чтобы в сумме получилось число, крупно написанное на карте. Например, на карте 22 есть вырезы напротив 16, 4 и 2, а 16 + 4 + 2 = 22. Чтобы понять происходящее, нужно знать кое-что из простой математики, а именно двоичную систему счисления.

Две системы

Двоичный код — это способ записывать числа, при котором в нашем распоряжении 0 и 1 вместо 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9, которыми мы обычно пользуемся. Наша обычная система называется десятичной. В двоичной системе всего два символа, и на перфокартах мы будем использовать круглые отверстия для 0 и щели для 1. Двоичная и десятичная системы — просто две разные системы представления чисел. Выбрать правильное представление информации — еще один важный элемент вычислительного мышления.

Давайте сначала рассмотрим десятичную систему и сравним ее с двоичной. В десятичной системе, чтобы досчитать до 9, мы используем цифры, но они заканчиваются, и в этот момент мы переходим в новый столбик. Мы возвращаемся к 0, но переносим 1 в следующий столбик, и 1 теперь обозначает 10, как показано на рис. 9.

Любая цифра во втором столбике обозначает на 10 больше, чем та же цифра в первом столбике. В десятичной системе 16 — это один десяток (1 в столбике десятков) и шесть единиц (6 в столбике единиц). Мы добавляем 10 к 6, чтобы получить число 16. Подобным образом, 987 обозначает 9 раз по 100, 8 раз по 10 и 7 раз по одному, сложенные вместе.

Двоичная система работает точно так же, только у нас раньше заканчиваются цифры. Дойдя до 1, мы уже переходим в новый столбик, до 9 нам не добраться (рис. 10). Это значит, что столбцы теперь предназначены для единиц, двоек, четверок, восьмерок и так далее — вместо единиц, десятков и сотен. То есть в двоичной системе (используя только 1 и 0) мы записываем, например, число 5 как 101. Это 1 в разряде четверок плюс 0 в разряде двоек и плюс 1 в разряде единиц.

Если распределить это на пять колонок (как мы сделаем это на перфокартах), то 5 в двоичной системе будет выглядеть как 00101.

Подобным образом, 16 в двоичной системе — это 10000.

Отметим, что, помимо колонки единиц, все остальные колонки обозначают степени двойки, то есть четные числа. Поэтому единственный способ представить нечетное число в двоичной системе — поставить 1 в колонку единиц. У всех нечетных чисел в ней будет 1, а у четных — 0. Насколько это важно, мы увидим ниже.

Двоичные перфокарты

Какое отношения это имеет к нашим перфокартам? На них мы можем записывать числа в двоичной системе, используя отверстия для 0 и вырезы для 1. Чтобы записать на перфокарту число 5, начиная слева, нам нужно отверстие (0), еще отверстие (0), потом вырез (1), снова отверстие (0) и, наконец, вырез (1). Для числа 16 (10000) нам нужен один вырез и 4 отверстия. Если у нас есть место для пяти отверстий, мы можем записать на карту любое число до 31. Имея достаточно места (то есть достаточно степеней двойки и, соответственно, разрядов), мы можем записать любое число. Описанные примеры перфокарт приведены на рис. 11а и 11b.

Как только мы записали на карту число в двоичном коде в виде отверстий и вырезов, можно с легкостью найти любую карту. И здесь наступает черед метода «шиворот-навыворот».

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

Например, мы ищем карту с номером 16. В двоичной системе это 10000. При движении слева направо выходит:

 

ВЫРЕЗ 1: 0 — СБРОСЬТЕ упавшие карты.

ВЫРЕЗ 2: 0 — СБРОСЬТЕ упавшие карты.

ВЫРЕЗ 4: 0 — СБРОСЬТЕ упавшие карты.

ВЫРЕЗ 8: 0 — СБРОСЬТЕ упавшие карты.

ВЫРЕЗ 16: 1 — ОСТАВЬТЕ упавшие карты.

 

Многократно сбрасывайте нижнюю стопку, пока, в пятом раунде, ее не нужно будет оставить. У вас останется карта с номером 16. Таким образом, прорабатывая двоичный код, можно найти любую карту. Попробуйте найти карту 5. В двоичной системе это 00101. При движении справа налево получаем:

 

ВЫРЕЗ 1: 1 — ОСТАВЬТЕ упавшие карты.

ВЫРЕЗ 2: 0 — СБРОСЬТЕ упавшие карты.

ВЫРЕЗ 4: 1 — ОСТАВЬТЕ упавшие карты.

ВЫРЕЗ 8: 0 — СБРОСЬТЕ упавшие карты.

ВЫРЕЗ 16: 0 — СБРОСЬТЕ упавшие карты.

 

У вас останется карта 5.

Как же это работает?

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

Возьмите первый раунд, когда вы сбрасываете карты и одновременно ищете номер 16. Стряхнув первые перфокарты и затем избавившись от них, вы отметаете все карты с вырезом (1) в первой позиции двоичного числа. Это столбик единиц. У чисел 1, 3, 5, 7 будет вырез (1) в этой позиции — все это нечетные числа. Происходит то же самое, что и в первом раунде «шиворот-навыворот», когда мы сбрасываем каждую вторую карту. Как вы видели выше, мы переводим число из двоичной системы в десятичную, складывая числа в соответствующих разрядах (например, 5 = 4 + 0 + 1). Этот последний разряд единиц полностью определяет нечетные числа, в то время как все остальные — четные (2, 4, 8, 16, …).

Вот еще один способ понять, почему двоичное представление ведет к тому, что нечетные числа отбрасываются, — он поможет нам понять, как работает остальная часть фокуса. Подумайте, как мы считаем в двоичной системе: 0, 1, 2, 3, 4, … — это 000, 001, 010, 011, 100, … В колонке единиц во время счета значение меняется через раз, то есть в этой последней позиции по очереди оказываются 0, 1, 0, 1 — и так далее. Это значит, что если мы отбросим все единицы, то избавимся от каждой второй карты.

То есть мы показали, что в первом раунде происходит то же самое, что и в фокусе. Отбросив все карты с нечетными цифрами, мы переходим к следующему отверстию на перфокарте и, таким образом, к следующей позиции в двоичном числе. Эта операция убирает все числа, в составе которых есть разряд двоек. Например, это 6 (110 в двоичной системе), поскольку 6 = 4 + 2 + 0. На этот раз уходят 2 (10 в двоичной системе), 3 (11), 6 (110), 7 (111), 10 (1010), 11 (1011) и так далее. Однако нечетные числа уже были удалены, значит, на этот раз мы стряхнем 2, 6, 10,... То есть остается каждая вторая карта. Это та же последовательность карт, которую мы удаляем во втором раунде «шиворот-навыворот».

Причина становится очевидной, если посмотреть на второй столбик в числах, записанных двоичным кодом. Там мы видим 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1...

Получается, что в двоичной записи второй символ меняется только в том случае, если в первой позиции уже были и 0, и 1. Но если убрать каждую вторую карту в этой последовательности, у нас остается не 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1..., а 0, 1, 0, 1, 0, 1,... И мы получаем:

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

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

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

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

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

И снова изобретаем фокусы

Новое из старого

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

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

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