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

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

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

На рис. 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. Насколько это важно, мы увидим ниже.