Перевод натуральных чисел из одной позиционной системы счисления в другую

Теорема. Любое натуральное число т может быть записано в системе счисления с основанием р, причем запись эта единственная
(p Î N, р > 1).

Доказательство. Итак, необходимо представить число т в виде , где коэффициентами

являются цифрами р-ичной системы счисления. Рассмотрим последовательность чисел: р, р2, р3, ..., рn, рn+1, ... .

Среди членов этой последовательности найдем число р с наибольшим показателем степени, которое не превышает рассматриваемое натуральное число т. Пусть это будет рn, тогда рn ≤ m < pn+1.

1) Так как рn ≤ m, то т можно разделить на рn с остатком. Тогда получим: т = рn an + mn. Частное an и остаток mn всегда существуют и притом единственные, очевидно 0 < an < р и 0 ≤ тn < рn.

2) Полученный остаток тn разделим на pn-1 с остатком. Тогда получим: mn = рn-1 · an-1 + mn-1, очевидно 0 ≤aп-1 < р и 0 ≤ тп-1 < рп-1.

3) Вновь найденный остаток тп-1 разделим на рп-2 с остатком. Тогда получим: mn-1 = рn-2 · an-2 + mn-2; 0 ≤ an-2< р и 0 ≤ тn-2< рn-2.

Процесс деления полученного остатка на соответствующую степень основания р аналогичным образом продолжим до конца.

n) На последнем шаге получим:

m2= р · a1+ m1, 0 ≤ a1< р и 0 ≤ т1 < р. Обозначим т1 = а0.

Таким образом, подставляя значения остатков из выписанных выше равенств 1), 2), 3), …, n) получим: т = an · рn + an-1· рn-1 + ... +
+ a1p + а0, причем 0 ≤ ai < р (i = 0, 1, 2, ..., n), или 0 ≤ ai ≤ р – 1, an ≠ 0.

Мы доказали, что любое натуральное число может быть представлено в р-ичной системе счисления, причем единственным образом.

П р и м е р 1. Запишите в восьмеричной системе счисления число 543710.

Перевод этого числа выполним, как было доказано в теореме.

Рассмотрим последовательность чисел: 8, 82, 83 , 84, 85, …

(81 = 8, 82 = 64, 83=512, 84 = 4096, 85 = 32768).

Заметим, что 4096 < 5437 < 32768. Разделим 5437 на 84 с остатком. Тогда получим: 5437 = 1 · 84 + 1341. Продолжим деление, как описывалось выше:

1341 = 2 · 83 + 317;

317 = 4 · 82 + 61;

61 = 7 · 8 + 5;

Т.е. 5437 = 1 · 84 + 2 · 83 + 4 · 82 + 7 · 8 + 5;

543710 = 124758

На практике вычисления обычно ведутся в обратном порядке.

Рассмотрим снова тоже число 5437 и разделим его на 8.

5437 8

5 679

5437 = 8 · 679 + 5. Это означает, что наше число, кроме некоторого количества восьмерок, содержит еще 5 единиц, т.е. последняя цифра восьмеричной записи есть 5. Для получения следующей цифры нужно полученное частное снова разделить на 8.

Результат выполненных операций можно представить в таком виде:

5437 =8 · 679 + 5

5437 = 8(8 · 84 + 7) + 5

5437 = 8(8(8 · 10 + 4) + 7) + 5

5437 = 8(8(8(1 · 8 + 2) + 4) + 7) + 5 =

= 1 · 84 + 2 · 83 + 4 · 82 + 7 · 8 + 5.

Коротко решение этого примера записывается так:

 
 

 


П р и м е р 2. Запишите в двоичной системе счисления число 4710. Используем тот же прием, здесь р = 2.

 
 

 

 


Общее правило можно сформулировать так.

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

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

63758 = 6 · 83 + 3 · 82 + 7 · 8 + 5 = 332510

111012 = 24 + 23 + 22 + 1 = 16 + 8 + 4+1= 2910.