© Данная статья была опубликована в № 17/2007 журнала "Информатика" издательского дома "Первое сентября". Все права принадлежат автору и издателю и охраняются.      Главная страница "Первого сентября"
     Главная страница журнала "Информатика"
     Содержание № 17/2007
 В мир информатики # 93 (1-16 сентября). Семинар.Системы счисления.


В мир информатики # 93 (1–16 сентября).
Семинар

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

Окончание. Начало см. “В мир информатики” № 90
(“Информатика” № 8/2007)

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

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

q0 = d0 = l, q1 = d1 = d, q2 = d2, q3 = d3, q4 = d4, …,

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

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

В d-ичной системе счисления запись числа в виде anan-1a2a1a0 имеет следующий смысл:

andn + an-1dn-1 + … + a2d2 + ad + a0.

Ясно, что каждая цифра в записи числа по d-ичной системе счисления может принимать лишь d значений: 0, или 1, или 2, или 3, …, или d – 1. В частности, если d = 10 и, следовательно, базис системы счисления q0 = 1, q1 = 10, q2 = 100, q3 = 1000, …, мы приходим к общепринятой десятичной системе счисления (счет единицами, затем десятками, затем сотнями, тысячами, десятками тысяч и т.д.); в ней все цифры принимают значения, не превосходящие 9. Самой простой из всех d-ичных систем счисления является двоичная система счисления с базисом

q0 = 1, q1 = 2, q2 = 4, q3 = 8, q4 = 16, …

Эта система счисления использует всего две цифры — 0 и 1. Как известно, при использовании двоичной системы счисления все расчеты становятся довольно длинными, но чрезвычайно простыми. Если бы мы в повседневной жизни всегда пользовались именно этой системой счисления, то школьникам пришлось бы запоминать лишь следующую “таблицу умножения”:

0 x 0 = 0, 0 x 1 = 0, 1 x 0 = 0, 1 x 1 = 1.

Хотели бы вы такого, учась в младших классах? :).

Так же просто выглядит в двоичной системе “таблица сложения”:

0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 10,

— ведь число 10 — это аналог “нашей” двойки (и не только — школьной отметки :).

Задания для самостоятельной работы

1. Число N = 123 456, записанное в десятичной системе счисления, запишите:

а) в 7-ричной системе счисления;

б) в 12-ричной системе счисления (в этой системе счисления для записи чисел используются 12 цифр, например, такие: 0, 1, 2, …, 9, X = 10, Y = 11);

в) в двоичной системе счисления.

2. Запишите в десятичной системе счисления числа, записанные в двоичной системе:

Р = 100 100, Q = 101 010 101.

3. Составьте таблицу сложения и таблицу умножения в троичной и четверичной системах счисления.

Системы счисления с другими базисами

Системы счисления с базисами, не образующими геометрическую прогрессию 1, d, d2, d3, …, не имеют широких применений. Но при решении некоторых математических задач они оказываются полезными.

Рассмотрим несколько примеров таких систем счисления.

1. Система майя

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

q0 = 1, q1 = 20, q2 = 18q1 (= 18 · 20),

q3 = 20q2 (= 18 · 202),

q4 = 20q3 (= 18 · 203), …

Эта система счисления во всем подобна двадцатеричной, отличаясь от нее лишь в одном отношении: в ней вторая с конца цифра в записи anan-1a2a1a0 произвольного числа (которую мы привычно располагаем горизонтально, а не сверху вниз, как майя) a1 < , в то время как все другие цифры могут принимать 20 значений: 0, 1, 2, …, 19.

Аналогично будет обстоять дело в системе счисления с базисом, в котором qn+1 делится на qn без остатка для всех n = 0, 1, 2, …:

q0 = 1, q1 = d0, q2 = d1q1 (= d1d0),

q3 = d2q2, q4 = d3q3, …, (1)

где d0, d1, d2, d3, … — какие угодно целые положительные числа, большие 1, различные или одинаковые. В такой системе счисления в записи числа anan – 1…a2a1a0 первая с конца цифра a0 может принимать d0 значений: 0, 1, 2, …, d0 – 1, следующая цифра a1 может принимать d1 значений (от 0 до d1 – 1), цифра a2 может принимать значения от 0 до d2 – 1 и т.д.

При этом в системе счисления с базисом (1), как и в d-ичной системе счисления (в которую наша система обращается в случае d0 = d1 = d2 = ... = d), имеет смысл любая запись anan-1a2a1a0, где a0, a1, a2, …, an — натуральные числа такие, что a0 < d0,
a
1 < d1, a2 < d2 и т.д. В самом деле, легко проверить, что при обращении числа N = anqn + an – 1qn – 1 + … + a2q2 + a1q1 + a0 в нашу систему счисления по методу “непрерывного деления” (см. первую часть статьи) получаются цифры an, an – 1, …, a2, a1, a0.

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

2. “Четная” система счисления

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

q0 = 1, q1 = 2, q2 = 4, q3 = 6, q4 = 8, q5 = 10, …

Так как здесь

q1 = 2

при всех n > 1, то эта система счисления, подобно двоичной, знает всего две цифры: 0 и 1.

Условимся обозначать числа, записанные в этой “четной” системе счисления, жирным оформлением. Тогда, очевидно, 210 = 10, 310 = 11, 410 = 100, 510 = 101, 610 = 1000, 710 = 1001, 810 = 10000, 910 = 10001 и т.д.

И вообще, все числа в ней изображаются либо единицей с тем или иным количеством нулей в конце (четные числа), либо двумя единицами в начале и в конце числа, разделенными известным числом нулей (нечетные числа).

Таким образом, в “четной” системе счисления запись каждого числа имеет вид:

anan-1a2a1a0,

где каждая из цифр an, an-1, …, a2, a1, a0 может принимать только одно из двух значений: 0 или 1.

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

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

3. “Система продавца”

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

Он пользуется набором гирь, как кассир ассигнациями и монетами, имеющимися в кассе (действия кассира описаны в первой части статьи). А именно, отвешивая товар, он прежде всего кладет на весы самую тяжелую из не перевешивающих товар гирь, далее он кладет старшую из оставшихся гирь и т.д. Так, например, взвешивая кусок мяса весом в 3 кг 460 г, он использует гири 2 кг, 1 кг, 200 г, 200 г, 50 г и 10 г.

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

11020101000.

В этой системе счисления в записи anan-1a2a1a0 последняя цифра a0 может равняться лишь 0 или 1 (ибо q1 = 2); предпоследняя цифра a1 может принимать значения 0, 1 или 2 (так как 2 < q2/q1 < 3), третья от конца цифра a2 снова может принимать лишь значения 0 и 1 (ибо q3/q2 = 2); цифра a3 также может принимать лишь значения 0 и 1, а вот цифра a4 cнова может принимать значения 0, 1 и 2 (ибо 2 < q5/q4 < 3). И вообще, в этой системе счисления все цифры а1, а4, а7, а10, ..., а3k+1 могут принимать значения 0, 1 и 2, а все остальные цифры — лишь значения 0 и 1. (Поэтому продавцу в магазине достаточно иметь две двухкилограммовые гири и только по одной гире в 1 кг и в 5 кг.)

Задания для самостоятельной работы

4. Запишите числа X, Y и Z в десятичной системе, если

а) в “четной” системе счисления X = 1 000 000 001;

б) в “системе продавца” Y = 121 121;

в) в “системе продавца” Z = 20 120.

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

а) какое наименьшее число гирь необходимо, чтобы отвесить любое целое число килограммов от 1 до 40 на чашечных весах, если гири можно класть только на одну чашку весов? (Вы можете подбирать такие веса гирь, какие хотите.)

б) тот же вопрос, если разрешается класть гири на обе чашки весов;

в) какое наименьшее число гирь необходимо в том и другом случае, чтобы взвесить любой груз (в целое число граммов) от 1 г до 1000 г?

Литература 

1. Яглом И. Системы счисления. / “Квант” № 6/1970.

2. Бедный торговец (старинная задача). / “В мир информатики” № 50 (“Информатика” № 3/2005).

3. О троичной системе счисления. / “В мир информатики” № 69 (“Информатика” № 4/2006).


1 О том, что такое базис системы счисления, см. первую часть статьи