Читать «Вычислительное мышление: Метод решения сложных задач» онлайн - страница 26

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

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