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