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

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

На рис. 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 стоит в середине каждого второго числа в приведенной последовательности.

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

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

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

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

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

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

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

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

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