LINEBURG


страница 1
(всего 7)

ОГЛАВЛЕНИЕ

След. стр. >>

Н а у ч н о - р е д а к ц и о н н ы й с о в е т с е р и и:
В. В. Прасолов, А. Б. Сосинский (гл. ред.),
А. В. Спивак, В. М. Тихомиров, И. В. Ященко.



Серия основана в 1999 году.
Библиотека
<Математическое просвещение>
Выпуск 29




С. Б. Гашков



СИСТЕМЫ СЧИСЛЕНИЯ
И ИХ ПРИМЕНЕНИЕ




Издательство Московского центра
непрерывного математического образования
Москва • 2004
УДК 511.1
ББК 22.130
Г12

Аннотация
Различные системы счисления используются всегда, когда
появляется потребность в числовых расчётах, начиная с вычи-
слений младшеклассника, выполняемых карандашом на бумаге,
кончая вычислениями, выполняемыми на суперкомпьютерах.
В книжке кратко изложены и занимательно описаны не-
которые из наиболее популярных систем счисления, история их
возникновения, а также их применения, как старые, так и но-
вые, как забавные, так и серьёзные.
?
Большая её часть доступна школьникам 7—8 классов,
но и опытный читатель может найти в ней кое-что новое для себя.
Текст книжки написан на основе лекций, прочитанных
автором в школе им. А. Н. Колмогорова при МГУ и на Малом
мехмате МГУ.
Книжка рассчитана на широкий круг читателей, интересу-
ющихся математикой: школьников, учителей.


Издание осуществлено при поддержке
Московской городской Думы
и Департамента образования г. Москвы.


ISBN 5-94057-146-8 © Гашков С. Б., 2004.
© МЦНМО, 2004.


Сергей Борисович Гашков.
Системы счисления и их применение.
(Серия: <Библиотека ,,Математическое просвещение“>).
М.: МЦНМО, 2004. — 52 с.: ил.
Редакторы Е. В. Корицкая, Ю. Г. Кудряшов.
Художник Т. И. Котова.
Техн. редактор М. Ю. Панов. Корректор Т. Л. Коробкова.

Лицензия ИД № 01335 от 24/III 2000 года. Подписано к печати 25/II 2004 года.
Формат бумаги 60?88 116 . Офсетная бумага № 1. Офсетная печать. Физ. печ. л. 3,25.
/
Усл. печ. л. 3,18. Уч.-изд. л. 3,62. Тираж 5000 экз. Заказ 6709.

Книга соответствует гигиеническим требованиям к учебным изданиям для обще-
го и начального профессионального образования (заключение государственной са-
нитарно-эпидемиологической службы Российской Федерации № 77.99.02.953.Д.
002797.04.03 от 18/IV 2003 года).

Издательство Московского центра непрерывного математического образования.
119002, Москва, Г-2, Бол. Власьевский пер., 11. Тел. 241 72 85, 241 05 00.

Отпечатано с готовых диапозитивов
в ФГУП <Производственно-издательский комбинат ВИНИТИ>.
140010, г. Люберцы Московской обл., Октябрьский пр-т, 403. Тел. 554 21 86.
§ 1. ДЕНЬГИ В КОНВЕРТАХ И ЗЁРНА НА ШАХМАТНОЙ ДОСКЕ
Представьте себе, дорогой читатель, что вы банкир, занимаю-
щийся отмыванием грязных денег, и завтра ждёте важного клиен-
та, которому вы должны выдать круглую или не очень круглую,
но заранее вам неизвестную сумму от 1 до 1 000 000 000 у. е. Что-
бы не пачкать руки о грязные деньги, вы заранее дали указание
своим кассирам заготовить некоторое количество конвертов с день-
гами, на которых написаны содержащиеся в них суммы, и собира-
етесь просто отдать клиенту один или несколько конвертов, в ко-
торых и будет содержаться требуемая им сумма. Какое наимень-
шее количество конвертов необходимо иметь?
Конечно, можно просто заготовить конверты со всеми суммами
от 1 до 1 000 000 000. Но где взять столько денег на конверты?
1. А какова будет в этом случае полная сумма во всех конвер-
тах? Попробуйте оценить также массу бумаги, предполагая, что
использованы не более чем сотенные купюры*).
Есть более рациональный подход к нашему делу. Надо положить
в первый конверт 1 у. е., а в каждый следующий класть вдвое боль-
шую сумму, чем в предыдущий. Тогда, например, в 5-м конверте
будет 16 у. е., в 10-м — 512 у. е., в 11-м — 1024 у. е., в 21-м —
10242 =1 048 576 у. е., в 31-м — 10243 =1 073 741 824 у. е., но он
нам, очевидно, уже не понадобится, а вот 30-й с 1 073 741 824/2=
=536 870 912 у. е. может и пригодиться. В общем случае сумма
в (n+1)-м конверте будет равна произведению n двоек, это чи-
сло принято обозначать 2n и называть n-й степенью двойки. Усло-
вимся считать, что 20 =1. Проведённые выше вычисления основы-
вались на следующих свойствах операции возведения в степень:
2n 2m =2n+m , 2n /2m =2n?m , (2n )m =2nm .
Экспериментально легко проверить, что любое число можно пред-
ставить единственным образом в виде суммы различных меньших
степеней двойки, и поэтому наша задача почти решена. Например,
30 000=214 +213 +212 +210 +28 +25 +24 .
Но для реального применения нужен алгоритм построения тако-
го разложения. Далее будут приведены несколько разных алгорит-
мов, но вначале мы рассмотрим самый простой. В сущности, это
алгоритм выдачи сдачи клиенту, записанный некогда даже в ин-
струкции для работников торговли, но очень редко ими выполняю-
щийся. А он очень прост — сдачу надо выдавать, начиная с самых
больших купюр. В нашем случае нужно найти конверт с наиболь-
шей суммой денег, не превосходящей требуемую, т. е. наибольшую
степень двойки, не превосходящую требуемого количества денег.
*) Двумя чертами слева выделены тексты задач для самостоятельного решения.
3
Если требуемая сумма равна этой степени, то алгоритм заканчивает
работу. В противном случае опять выбирается конверт с наиболь-
шей суммой денег, не превосходящей оставшуюся, и т. д. Алго-
ритм закончит работу, когда останется сумма, в точности равная
степени двойки, и она будет выдана последним конвертом.
Ниже мы докажем, что, имея набор конвертов с суммами
в 1 у. е., 2 у. е., 4 у. е., ..., 2n у. е., любую сумму денег от 1 у. е.
до 2n+1 ?1 у. е. можно выдать единственным способом. Также
будет доказано, что, действуя по описанному алгоритму, мы всегда
получим этот способ выдачи требуемой суммы.
Вначале рассмотрим пример работы алгоритма с числом 2n ?1.
Ясно, что на первом шаге будет выбрано число 2n?1 , останется
число 2n ?1?2n?1 =2n?1 ?1, потом будет выбрано число 2n?2 ,
и т. д., и в результате получится разложение
2n ?1=2n?1 +2n?2 +...+22 +21 +20 .
Но оно не показалось бы очевидным, если, не зная заранее ответа,
пришлось бы вычислять сумму
1+2+4+8+...+2n?2 +2n?1 ,
называемую суммой геометрической прогрессии со знаменателем 2.
Ведь для этого пришлось бы выдумать какой-нибудь трюк наподо-
бие следующего:
1+2+4+8+...+2n?2 +2n?1 =2?1+2+4+8+...+2n?2 +2n?1 =
=4?1+4+8+...+2n?2 +2n?1 =8?1+8+16+...+2n?2 +2n?1 =...
...=2n?2 ?1+2n?2 +2n?1 =2n?1 ?1+2n?1 =2n ?1.
2. Используя подобный трюк, вычислите произведение
n
(2+1)(22 +1)·...·(22 +1).
Докажем теперь существование и единственность представле-
ния числа N в виде суммы меньших степеней двойки. Доказатель-
ство будем проводить индукцией по N.
Для N=1 утверждение очевидно.
Пусть оно верно для всех N<N0. Пусть 2n — максимальная
степень двойки, не превосходящая N, т. е. 2n ?N0 <2n+1 . Тогда
по предположению индукции число N0 ?2n ?2n представимо в ви-
де суммы степеней двойки, меньших N0 ?2n <2n . Следовательно,
число N0 тоже представимо в виде суммы меньших степеней двой-
ки (достаточно к представлению числа N0 ?2n добавить 2n ). Кроме
того, так как 1+2+...+2n?1 =2n ?1<2n , то не существует пред-
ставления числа N0 , не исползующего 2n . Таким образом, доказа-
на единственность такого представления.
Заметим, что для быстрого применения этого алгоритма удобно
заранее вычислить все степени двойки, не превосходящие данного
числа.
4
Заметим ещё, что, в отличие от первого варианта решения,
полная сумма во всех конвертах менее чем в два раза превосходит
верхнюю границу подлежащей выплате суммы.
Для краткой записи результата работы алгоритма над данным
числом a можно вместо разложения
a=2n1 +...+2nk ,
которое и записать-то в общем виде без использования трёхэтаж-
ных обозначений затруднительно, использовать последовательность
показателей степеней (n1 , ..., nk ), или, что ещё удобнее (но не все-
гда короче), написать последовательность (am , ..., a1 ) чисел 0 и 1,
в которой ai =1, если число 2i?1 входит в указанное выше разло-
жение, и ai =0 в противном случае. Тогда это разложение можно
будет переписать в виде
а=a1 +2a2 +4a3 +...+2m?1 am .
Ясно, что приведённый выше алгоритм позволяет строить такое
представление, причём оно определяется однозначно, если предпо-
лагать, что старший его разряд am ненулевой. Это представление
и называется двоичной записью числа a.
Читатель увидит, что понятие двоичной записи очень похоже
на понятие десятичной записи и в каком-то смысле даже проще.
Остался вопрос о минимальности найденной системы конвер-
тов. В общем виде указанный выше приём предлагает для уплаты
любой суммы от 1 до n использовать m конвертов с суммами 1,
2, 4, 8, ..., 2m?1 , где 2m?1 ?n<2m . Меньшего количества кон-
вертов может не хватить, потому что с помощью k<m конвер-
тов можно уплатить не более чем 2k ?1<2m?1 ?n разных сумм,
так как каждая сумма однозначно определяется ненулевым набо-
ром (a1 , ..., ak ), в котором каждое число ai равно 1, если i-й кон-
верт входит в эту сумму, и равно 0 в противном случае, а всего
наборов длины k из нулей и единиц можно составить ровно 2k .
3. Докажите последнее утверждение.
4. Докажите, что если n=2m ?1, то минимальная система
конвертов определяется однозначно, в противном случае — нет.
После упоминания десятичной системы сразу возникает идея
на первый взгляд даже более простого решения задачи о конвер-
тах. Надо просто заготовить конверты с суммами 1, 2, ..., 9, 10,
20, 30, ..., 90, 100, 200, 300, ..., 100 000 000, 200 000 000, ...
..., 900 000 000. Тогда для выплаты любой требуемой суммы
не нужно искать её двоичную запись, так как для выплаты, напри-
мер, 123 456 789 у. е. нужно просто взять конверт с суммой 9, кон-
верт с суммой 80, конверт с суммой 700 и т. д. Это действительно
проще, но исключительно потому, что мы привыкли пользоваться
десятичной системой и все расчёты ведутся с её помощью. Если бы
мы использовали в повседневной жизни только двоичную систему,
5
то этот способ был бы сложнее, так как приходилось бы перево-
дить данную сумму из двоичной системы в десятичную*). Поэтому
простота десятичного способа решения задачи скорее мнимая.
На самом деле указанный выше двоичный метод имеет пре-
имущество перед десятичным (и любым другим). Оно заключается
в меньшем числе используемых конвертов, что было показано выше.
Хотя длина двоичной записи числа в три с лишним раза больше
длины его десятичной записи, на каждую цифру десятичной запи-
си приходится девять конвертов, т. е. число конвертов в двоичном
методе почти в три раза меньше, чем в десятичном.
Идея, лежащая в основе изложенной задачи, видимо, очень древ-
няя, и происходит, вероятно, из Индии. Об этом свидетельствует ле-
генда об изобретателе шахмат, который скромно попросил (после
настояний магараджи, которому очень понравилась игра) себе в на-
граду положить одно зерно на угловую клетку шахматной доски
и удваивать количество зёрен на каждой следующей клетке. Магарад-
жа, подивившись скудоумию казавшегося таким мудрым человека,
распорядился отсыпать ему запрошенные несколько мешков зерна.
5. Оцените приблизительно, во сколько миллионов тонн зерна
обойдётся магарадже его щедрость.
Из сказанного выше видно, что если бы на каждое поле шах-
матной доски не всегда класть столько зерна, сколько просил му-
дрец, а иногда вообще не класть зёрен, то можно получить таким
образом любое число от 0 до 264 ?1. Поэтому, вероятно, таким
образом можно представить любое число, которое может встретить-
ся в каких либо конкретных прикладных вычислениях.
Индийская легенда обращает наше внимание на одну особен-
ность двоичной (и любой позиционной) системы — возможность
представить колоссальные числа в виде короткой записи. Разуме-
ется, в качестве такой записи не надо использовать совокупность
количеств зёрен, лежащих на клетках доски в точности так как
указано выше — ведь эти числа могут быть очень велики, и реаль-
но такое количество зёрен на большей части клеток доски поме-
стится не может. Вместо этого, как и принято в двоичной системе,
на каждую клетку или не кладётся зёрен вообще, или кладётся од-
но зерно, которое символизирует соответствующую степень двой-
ки. Тогда шахматная доска превращается по существу в то, что
на Востоке называют абак, а в России — счёты.
Конечно, реально используемые счёты всегда были десятичны-
ми, но проведённые выше рассуждения показывают, что, хотя дво-
ичная запись в три раза длиннее десятичной (и вообще, из всех
позиционных систем в этом смысле двоичная — самая плохая),

*) Иногда это приходится делать и в реальной жизни. Различные алгоритмы
такого перевода будет изложены далее.
6
но изготовление счёт с применением двоичной системы могло бы
дать определённую (правда, лишь теоретическую) экономию (см.
приложение, с. 49).
6. Пусть на каждой из n спиц счётов находится по b костяшек
(т. е. счёты представляют числа в системе счисления с основани-
ем b+1) и поэтому они позволяют записать в этой системе любое
число от 0 до N=(b+1)n ?1 (число N характеризует <вмести-
мость> счётов). Каким нужно выбрать b, чтобы суммарное коли-
чество костяшек на счётах (<сложность> счётов) было минималь-
ным при условии возможности указанного представления на счё-
тах любого числа от 1 до N (т. е. при заданной вместимости)?
Для прочитавших этот параграф, ответ, конечно очевиден. Для
знающих логарифмы продолжение этой задачи: сравните слож-
ности десятичных и двоичных счёт одинаковой вместимости.
Приведённый выше алгоритм перевода из десятичной системы
в двоичную вычислял цифры двоичной записи, начиная со стар-
ших цифр. Опишем теперь кратко, возможно более удобный, ал-
горитм, в котором цифры двоичной записи вычисляются, начиная
с младших*).
Очевидно, самая младшая цифра равна нулю, если число чёт-
ное, и единице, если оно нечётное. Для нахождения остальных
двоичных цифр надо от исходного числа отнять найденную млад-
шую цифру, поделить разность пополам и к полученному числу
применить описанный выше шаг алгоритма.
Например, у числа 300 последние две цифры нули, а для нахож-
дения остальных цифр надо иметь дело с числом 300/4=75, поэто-
му следующая цифра 1, и получаем промежуточный результат 37.
Следующая далее цифра опять 1, и промежуточный результат 18,
поэтому следующая цифра 0, а промежуточный результат 9, сле-
дующая цифра 1, а потом три нуля подряд, а старший разряд, как
всегда 1. В результате получается двоичная запись 1000101100.
Преимущество этого алгоритма в том, что не требуется предва-
рительного вычисления степеней двойки, но зато приходится не-
однократно выполнять операцию деления пополам.
§ 2. ВЗВЕШИВАНИЕ С ПОМОЩЬЮ ГИРЬ И ВОЗВЕДЕНИЕ В СТЕПЕНЬ
Предлагаем читателю самому убедиться в том, что точно так же,
как и предыдущем разделе, можно доказать, что для отвешивания
любого числа граммов песка от 1 г до n г за одно взвешивание,
достаточно иметь гири 1 г, 2 г, 4 г, ..., 2m г, где 2m ?n<2m+1,
и меньшего числа гирь недостаточно, если песок лежит на одной чаш-
ке весов, а гири разрешается ставить на вторую чашку. На самом
*) Кстати, кассиры в магазинах и на рынках предпочитают выдавать сдачу
начиная с мелких купюр, вопреки инструкции. Причина понятная — надеются,
что покупатель, получив мелочь, уйдёт, забыв взять крупные.
7
деле с математической точки зрения эта задача, известная со сред-
невековых времён, ничем не отличается от рассмотренной выше
задачи о конвертах с деньгами.
Часто новые и интересные задачи получаются, если в старой
задаче наложить какие-нибудь естественные ограничения. Напри-
мер, можно задать следующий вопрос: за какое наименьшее коли-
чество взвешиваний на чашечных весах можно отвесить килограмм
сахарного песка, если имеется лишь одна однограммовая гирька?
На первый взгляд кажется, что единственный способ решения
этой задачи — отвесить один грамм, положить в эту же чашку
гирьку, отвесить в другой чашке два грамма, переложить гирьку
в неё и т. д., добавляя по одному грамму, после тысячного взве-
шивания отмерить наконец-то килограмм.
Но есть и более быстрый способ. Нужно лишь заметить, что если
мы научились отвешивать за n взвешиваний m г песка, то, сделав
ещё одно взвешивание, можно даже не используя гирьку отвесить
ещё m г, и, ссыпав обе порции вместе, получить 2m г за n+1 взве-
шивание. А если при этом взвешивании положить на одну из чашек
гирьку, то за n+1 взвешивание можно отмерить 2m±1 г песка.
Теперь воспользуемся двоичной записью числа 1000. Применяя
любой из указанных выше алгоритмов, получаем равенство
1000=29 +28 +27 +26 +25 +23 .
Так как
29 +28 +27 +26 +25 +23 =(((((2+1)2+1)2+1)2+1)22 +1)23 ,
то, последовательно отвешивая 1, 2+1=3, 2·3+1=7, 2·7+1=
=15, 2·15+1=31, 2·31=62, 2·62+1=125, 2·125=250, 2·250=
=500, получаем на десятом взвешивании 2·500=1000 г. Девяти
взвешиваний не хватит, потому что за два взвешивания можно
отмерить массу не более 3=22 ?1, за три — не более 7=2·3+
+1=23 ?1, за четыре — не более 15=2·7+1=24 ?1, и за девять
взвешиваний — не более 511=29 ?1.
Если нужно отмерить n г песка, то надо записать n в двоичном
виде am ...a1 , где 2m?1 ?n<2m, am =1, и воспользоваться формулой
n=am 2m?1 +...+a22+a1 =(...((2am +am?1 )2+am?2 )...)2+a1,
последовательно отвешивая по b1 =am , b2 =2b1 +am?1 , b3 =2b2 +
+am?2 , ..., bm =bm?1 2+a1 =n г.
В используемой формуле знающие читатели увидят так назы-
ваемую схему Горнера. К ней мы ещё вернёмся в дальнейшем.
Идея, лежащая в основе этого метода взвешивания, стара как сама
математика. Её применяли и древние египтяне, и древние индусы,
но, конечно, не для взвешивания, а для умножения. Ведь алгоритм
умножения столбиком был придуман не сразу, а до этого умножение
сводилось к сложению. Например, чтобы умножить какое-нибудь
8
число a на 1000, можно, используя только операции сложения после-
довательно вычислить a+a+a=3a, 3a+3a+a=7a, 7a+7a+a=
=15a, 15a+15a+a=31a, 31a+31a=62a, 62a+62a+a=125a,
125a+125a=250a, 250a+250a=500a, 500a+500a=1000a. Та-
кой метод умножения дожил почти до нашего времени, он удобен
при вычислениях на счётах. Сейчас он никому не нужен, так как
все используют калькуляторы. Но как возвести на калькуляторе
число a, например, в тысячную степень, если у него нет специ-
альной операции возведения в произвольную степень? Умножать
999 раз не нужно, а можно применить тот же приём, последо-
вательно вычисляя a3 =a2 a, a7 =(a3 )2 a, a15 =(a7 )2 a, a31 =(a15 )2 a,
a62 =(a31 )2 , a125 =(a62 )2 a, a250 =(a125 )2 , a500 =(a250 )2 , a1000 =(a500)2 .
Если вспомнить, что 1000 имеет двоичную запись 1111101000,
то можно заметить, что если отбросить старший бит (всегда равный
единице), то каждому следующему биту соответствует операция воз-
ведения в квадрат, если он нулевой, или, если он ненулевой, возве-
дение в квадрат с последующим умножением на число a — основа-
ние степени (т. е. делается две операции). Кстати, число a не нуж-
но каждый раз заново набирать на клавиатуре. Нужно в самом на-
чале вычислений занести его в память калькулятора, и когда нуж-
но, после нажатия кнопки для умножения, просто вызывать его
из памяти и потом нажимать кнопку <равно>. Таким образом, воз-
ведение в квадрат требует двукратного нажатия кнопок, а возведе-
ние в квадрат и последующее умножение на основание степени —
пятикратного. Для того чтобы не запутаться в операциях, можно
перед началом вычислений составить мнемоническое правило. Воз-
ведение в квадрат обозначим символом К, а возведение в квадрат
и последующее умножение — символом КУ. Тогда, заменяя в дво-
ичной записи единицы (кроме старшей) на КУ, а нули — на К,
получим правило КУКУКУКУККУККК, или короче КУ4 ККУК3 .
Посчитаем общее число операций умножения в рассмотрен-
ном вычислении. Число возведений в квадрат на единицу меньше
длины двоичной записи показателя степени, а число умножений
общего вида на единицу меньше суммы цифр двоичной записи.
Для любого n обозначим ?(n) уменьшенную на единицу дли-
ну двоичной записи числа n, a ?(n) — её сумму цифр (другими
словами, число единиц в ней). Тогда в общем случае число опера-
ций умножения, использованных в этом методе возведения в сте-
пень n, будет равно ?(n)+?(n)?1. Далее будет показано, что мень-
шим числом операций обойтись нельзя, если только не обновлять
содержимое ячейки памяти.
Очевидно, что ?(n)+?(n)?1?2?(n). Те, кто знают логарифмы,
сообразят, что ?(n)= log2 n , где знак x означает целую часть
числа x. Но можно вычислить обе введённые функции даже
не упоминая о двоичной записи. Для этого надо воспользоваться
9
следующими правилами:
?(1)=1, ?(2n)=?(n), ?(2n+1)=?(n)+1,

страница 1
(всего 7)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign