Системы счисления

3

Поступать таким же образом со всеми встречшимися на практике числами было бы неудобно. Далее если бы наши потребности ограничивались счетом в пределах тысяч, надо было бы запомнить тысячу специальных знаков. Естественно, что уже давно люди стали выбирать тот или иной ряд «ключевых» чисел и только их обозначать специальными знаками. Такова, например, римская система числения (нумерации), основанная на ключевых числах
1, 5, 10, 50, 100, 500 и 1000.
Эти числа в римской системе числения обозначают буквы I («и»), V («ве»), X («икс»), L («эль»), C («це»), D («де») и M («эм»).

Такие обозначения частно производили от рисунков, изображенных неокогда соответствующие числительные (I — палец, V — пятерия с расставлением пальцами, X — две пятери), а частно являются сокращениями латинских слов (centum — сто, demimille — пятьсот, mille — тысяча).

Так как римская система нумерации нужна нам только для примера, мы рассмотрим ее в более древнем, упрощенном варианте, когда число «четыре» писалось в виде IIII, а не в виде IV. Число 3477 в этой старом римской системе записывается так: МММССССCLXXVII=3·1000+4·100+50+2·10+5+2.

Аналогично поступает кассир, имеющий денежные купоры достоинством в 100 рублей, 50 рублей, 25 рублей, 10 рублей, 5 рублей, 3 рублей и 1 рублей. Для кассира ключевыми являются числа

100, 50, 25, 10, 5, 3 и 1.
Желая выплать, скажем, 499 рублей, он выдает сначала столько сотных бумажек, сколько возможно,

что бы выдать лишнего:
499 = 4·100 + 99.

Затем он выдает столько купор по 50 рублей, сколько возможно, чтобы выдать не более оставшихся к выплате 99 рублей:
499 = 4·100 + 1·50 + 49,
и т. д. Иногода у него может получить остаток меньше, чем следующее ключевое число. Так будет на нашем примере после выдачи двух десятирubleков:
499 = 4·100 + 1·50 + 1·25 + 2·10 + 4.

Следующее ключевое число равно 5, однако, так как 4 < 5, то пятирubleков выдавать не придется. Но для полотны картины можно считать, что было выдано 0 пятирubleков, и включить в сумму слагаемое 0·5. Вся процедура выдачи 499 рублей запишется так:
499 = 4·100 + 1·50 + 1·25 + 2·10 + 0·5 + 1·3 + 1·1.

Попробуем теперь обобщить сказанное, взяв в качестве последовательности ключевых чисел («базиса») любую последовательность возрастания чисел:
$q_0 = 1 < q_1 < q_2 < \dots < q_n < \dots$ (1)
Опишем, как получить запись произвольного числа $N$ в системе чисел с базисом (1).

В последовательности (1) ключевых чисел находится самое большое число $q_n$, не превысаящее $N$. Дelim $N$ на $q_n$ и получаем (неполное) частное $a_n$ и остаток $r_{n-1}$:
$N = a_nq_n + r_{n-1}$, где $0 \leqslant r_{n-1} < q_n$.

Первый остаток $r_{n-1}$ делим на следующее ключевое число $q_{n-1}$. Положаем
$r_{n-1} = a_{n-1}q_{n-1} + r_{n-2}$,
где $0 \leqslant r_{n-2} < q_{n-1}$, или
$N = a_nq_n + a_{n-1}q_{n-1} + r_{n-2}$.

(Заметьте, что мы не исключаем здесь и тот случай, когда $r_{n-1} = 0$, — в этом случае все последующее частные

4

и остатки будут равны нулю!) Терьерь новый остаток $r_{n-2}$ делим на $q_{n-2}$; мы получаем

$$r_{n-2} = a_{n-2}q_{n-2} + r_{n-3},$$

где

$$0 \leqslant r_{n-3} < q_{n-2},$$

или

$$N = a_nq_n + a_{n-1}q_{n-1} + a_{n-2}q_{n-2} + r_{n-3}$$

и т. д.

В конце концов, разделив предпоследний остаток $r_1$ на $q_1$, получаем

$$N = a_nq_n + a_{n-1}q_{n-1} + \dots + a_2q_2 + a_1q_1 + r_0,$$

где $0 \leqslant r_0 < q_1$.

(Tак как $q_0 = 1$, то делить на него «последний остаток» $r_0$ излише: ясно, что $r_0 = a_0q_0 = a_0$.) Практические подобное многоократное деление обычно записьают слитно. Как это делается, мы показем на уже разобранном примере запись суммы в 499 руб. в «системе кассира»:

$$499 \times 100 + 499 \times 50 + 499 \times 25 + 499 \times 10 + 499 \times 5 + 499 \times 1 + 499$$

(Здесь все частиные $a_n, a_{n-1}$ и т. д. набранны красными цифрами, а само число $N$ и остатки $r_{n-1}, r_{n-2}$ и т. д. — синими.)

§ 2. Позиционные системы счисления

Вероятно, вы уже договорались, что в случае базиса

$$q_0 = 1, \quad q_1 = 10,$$

$$q_2 = 10^2, \dots, q_n = 10^n, \dots$$

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

$$4 \cdot 10^5 + 0 \cdot 10^4 + 3 \cdot 10^3 + 0 \cdot 10^2 + 1 \cdot 10 + 7$$

мы пишем просто 403017.

Рассейный или чересчур пунктульный кассир мог бы приготовить для записи своих выдачевedomость, где число выданных купюр разного достинства запосилось бы в отдельные столбцы. В такойedomости выдача 499 рублей выглядела бы так:

| | 100 | 50 | 25 | 10 | 5 | 3 | 1 |
| :— | :— | :— | :— | :— | :— | :— | :— |
| 499 | 4 | 1 | 1 | 2 | 0 | 1 | 1 |

Можно сказать, что в «системе счисления кассира» число 499 записывается в виде

$$4112011.$$

Системы счисления, родственные разобранным в последних двух примерах (т. е. десятичной системе счисления и «системе кассира»), называются позиционными (о значении этого выражения мы еще скажем ниже). Вместо громоздкой записи

$$N = a_nq_n + a_{n-1}q_{n-1} + \dots + a_2q_2 + a_1q_1 + a_0$$

в позиционной системе счисления с базисом (1) удобно пользоваться более компактной записью из $n+1$ «цифры»:

«$a_na_{n-1} \dots a_2a_1a_0$».

При этом предполагается, что «цифры» $a_k$ получены тем способом (алгоритм), который был описан выше.

Из этого описания ясно, что в заданном базисе каждой натуральное число $N$ записьается единственным образом. Далее, так как «старшая цифра» $a_n$ получается как частное от деления на $q_n$ числа $N$, которое по условию меньше $q_{n+1}$ (ибо иначе мы начали бы с деления $N$ на $q_{n+1}$, а не на $q_n$!), то $a_n < q_{n+1}/q_n$. Поэтому,

6

Существование и специальное обозначение для нуля, напоминавшее полузакрытый глаз:

Вот несколько примеров записи чисел в системе майя:

$$[1 \cdot 20 + 0 = 20, \quad 19 \cdot 360 + 13 \cdot 20 + 13 = 7113, \quad 10 \cdot 360 + 7 = 3607]$$

Основное стлиние записи чисел в варианском системе числения и по системе майя от римской нумерации как раз и заключается в «позиционном» принципе этих систем: в то время как у римлян буква I всегда означает единицу, а V — пятерку, независямо от того, где эти буквы стояят, у древних вивилонян и у индейцев майя значение «цифры» существует зависят от занимаемого его места, или «позиции». Именно поэтому такие системы записи чисел (к числу которых принадлежит и общераспространенная «десятичная система», созданная в Индии в VIII—IX вв. или немного раныше) называют позиционными.

Упражнения

1. Записать в «полной системе кассира» (где «ключевыми» является следующие числа: 10000, 5000, 2500, 1000, 500, 300, 100, 50, 20, 15, 10, 5, 3, 2 и 1, отвечающие выраженным в копейках ценностям всех существующих бумажных денег и всех монет сумму в 233 руб. 87 коп. Записать операцию перевода 23387 коп. в «систему кассира» с помощью «непрерывного деления» (см. стр. 4).

2. Прочесть записанное по варианском системе число

3. Прочесть записанное по системе майя число

(Это самое большое число, обнаруженное в памятниках культуры майя.)

§ 3. Системы числения с заданным основанием

Так называются системы числения с базисом

$$q_0 = d^0 = 1, \quad q_1 = d^1 = d, \quad q_2 = d^2, \quad q_3 = d^3, \quad q_4 = d^4, \dots, (2)$$

где $d$ — любое целое число, большее единиц. Это число $d$ называется основным системы числения.

К числу таких систем принадлежит общая десятиная система числения с основанием $d=10$, в варианском шестидесетеричная ($d=60$) и получившая широкое применение в последнее время в связи с нуждами вычислительной техники двойная система числения ($d=2$). В случае произвольного основания $d$ говорят о «d-ичной» системе числения.

В $d$-ичной системе числения запись $N = \langle a_n a_{n-1} \dots a_2 a_1 a_0 \rangle$ имеет следующий смысл:

$$N = a_n d^n + a_{n-1} d^{n-1} + \dots + a_2 d^2 + a_1 d + a_0.$$

8

шне 1, различные или одинаковые.
В такой системе счисления в записи числа

$$N = \lceil a_n a_{n-1} \dots a_2 a_1 a_0 \rceil$$

первая с конца цифра $a_0$ может принимать $d_0$ значений 0, 1, 2, …, $d_0$ — 1. следующего цифра $a_1$ может принимать $d_1$ значений от 0 до $d_1$ — 1; цифра $a_2$ может принимать значения от 0 до $d_2$ — 1 и т. д.

При этом в системе счисления с базисом (3), как и в $d$-ичной системе счисления (в котором наша система обращается в случае $d_0 = d_1 = d_2 = d_3 = \dots = d$), имеет смысл лю б а я запись

$$N = \lceil a_n a_{n-1} \dots a_2 a_1 a_0 \rceil,$$

где $a_0, a_1, a_2, \dots, a_n$ — натуральные числа такие, что $a_0 < d_0, a_1 < d_1, a_2 < d_2$ и т. д. В самом деле, легко проверить, что при обращении числа $N = a_n q_n + a_{n-1} q_{n-1} + \dots + a_2 q_2 + a_1 q_1 + a_0$ в нашу систему счисления по методу «непрерывного деления» (см. выше стр. 4) получается цифры:

$$a_n, a_{n-1}, a_{n-2}, \dots, a_1, a_0.$$

To, что такое благополучное положение не является общим законом, мы показем на примере одной очень простой «системы счисления».

2° «Четная» система счисления.

Прием за базис системы счисления все четные числа (и число $q_0 = 1$):

$$q_0 = 1, \quad q_1 = 2, \quad q_2 = 4, \quad q_3 = 6,$$

$$q_4 = 8, \quad q_5 = 10, \quad q_6 = 12,$$

Так как здесь

$$\frac{q_1}{q_0} = q_1 = 2$$

и

$$\frac{q_{n+1}}{q_n} = \frac{2(n+1)}{2n} = \frac{n+1}{n} = 1 + \frac{1}{n} < 2$$ при всех $n > 1$,

то эта система счисления, подобно двойной, знает всего две «цифры»: 0 и 1. Условия обозначать числа, записанные в этой «четной» системе счисления красным цветом. Тогда, оченьindo,

$$2 = 10, \quad 3 = 11, \quad 4 = 100, \quad 5 = 101, \quad 6 = 1000, \quad 7 = 1001, \quad 8 = 10000, \quad 9 = 10001$$ и т. д.

И вообще все числа изображаются либо единшей с тем или иным количеством нуля в конце (четные числа), либо двуяяяющее большинство последовательности нуля и единиц не выражают ни каких чисел в «четной» системе счисления, поскольку в ней единца может стать лишь на первом месте и — иногда — на последнем месте.

И, наконец, еще один пример.

3° «Системаprodavца». Стандартный набор гирь для чашечных весов в магазине обобщено включает гири: 10 е, 20 е (2), 50 е, 100 е, 200 е (2), 500 е, 1 ке, 2 ке (2) и 5 ке.

Продавец пользовется этим набором гирь, как кассир ассигнациями, имеющимся в кассе. А именно, ответивая товар, он прежде всегоkladет на весы самую тяжелую из не перевишивающих товаров гирь, далее онkladет старшую из оставшихся гирь и т. д.

Так, например, взвешивая кусок мяса весом в 3 ке 460 е, он использует гирь, показанных на рисунке.

9

Обобщая эту хорошего известную всем торговым служащим и всем хозяйским систему «представленной чисел (весов) с помощью заданной системы гирь», мы приходим к системе численения с базисом
1, 2, 5, 10, 20, 50, 100, 200, 500, …
в которой 3 ккал 460 г запишется так
11020101000.

В этой системе численения в записи
$$N \ll a_n a_{n-1} \quad a_2 a_1 a_0$$
последняя цифра $a_0$ может равнять лишь 0 или 1 (ибо $q_1 = 2$); предпоследняя цифра $a_1$ может принимать значения 0, 1 или 2 (так как $2 < q_2/q_1 < 3$); третья от конца цифра $a_2$ снова может принимать лишь значения 0 и 1 (ибо $q_3/q_2 = 2$); цифра $a_3$ также может принимать лишь значения 0 и 1, а вот цифра $a_4$ снова может принимать значения 0, 1 и 2 (ибо $2 < q_5/q_4 < 3$).

И вообще в этой системе численения все цифры
$$a_1, a_4, a_7, a_{10}, \dots, a_{3k+1}$$
могут принимать значения 0, 1 и 2, а все остальные цифры — лишь значения 0 и 1 (Позотому продавцу в магазина достаочно имеет две двухлограммовые гири и только по одной гире в 1 ккал и в 5 ккал.)