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

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

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

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

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

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

Как мы уже знаем, алгоритмические фокусы и компьютерные программы — по сути, одно и то же. В некоторых фокусах применяются точно такие же алгоритмы, как и в программах, — например, поисковый. Значит, мы вправе применить обобщениеи повторно использовать некоторые решения. В описанном фокусе надо было найти 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).

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