На этом шаге мы рассмотрим перевод целых чисел из одной системы счисления в другую.
Поскольку одно и то же число может быть записано в различных системах счисления, встает вопрос о переводе представления числа из одной системы (p) в другую (q) – будем обозначать такое преобразование Zp Zq. Теоретически возможно произвести его при любых q и p. Однако подобный прямой перевод будет затруднен тем, что придется выполнять операции по правилам арифметики недесятичных систем счисления. По этой причине более удобными с практической точки зрения оказываются варианты преобразования с промежуточным переводом ZpZr Zq с основанием r, для которого арифметические операции выполнить легко. Такими удобными основаниями являются r = 1 и r = 10, т.е. перевод осуществляется через унарную или десятичную систему счисления.
Преобразование Zp Z1 Zq
Идея алгоритма перевода предельно проста: положим начальное значение Zq := 0; из числа Zp вычтем 1 по правилам вычитания системы p, т.е. Zp := Zp–1 и добавим ее к Zq по правилам сложения системы q, т.е. Zq := Zq + 1; будем повторять эту последовательность действий, пока не достигнем Zp = 0.
Правила сложения с 1 и вычитания 1 могут быть записаны следующим образом:
Промежуточный переход к унарной системе счисления в данном случае осуществляется неявно – используется упоминавшееся выше свойство независимости значения числа от формы его представления. Рассмотренный алгоритм перевода может быть легко реализован программным путем, в частности, машиной Тьюринга.
Шаг | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Z3 - 1 | 22 | 21 | 20 | 12 | 11 | 10 | 2 | 1 | 0 |
Z6 + 1 | 0 | 1 | 2 | 3 | 4 | 5 | 10 | 11 | 12 |
Следовательно, 223 = 126.
Преобразование Zp Z10 Zq
Очевидно, первая и вторая часть преобразования не связаны друг с другом, что дает основание рассматривать их по отдельности.
Алгоритмы перевода Z10 Zq вытекают из следующих соображений. Многочлен (1) для Zq может быть представлен таким образом:
(2)
где m – число разрядов в записи Zq, а bj (j = 0...m–1) – цифры числа Zq.
Разделим число Zq на две части по разряду номер i; число, включающее m–i разрядов с m–1-го по i-й обозначим i, а число с i разрядами с i–1-го по 0-ой – i. Очевидно, i [0,m–1], 0 = m-1 = Zq. Позаимствуем из языка PASCAL обозначение двух операций: div – результат целочисленного деления двух целых чисел и mod – остаток от целочисленного деления (13 div 4=3; 13 mod 4 = 1). Теперь если принять m-1 = bm-1, то в (2) усматривается следующее рекуррентное соотношение: i = i+1 · q + bi, из которого, в свою очередь, получаются выражения:
(3)
Аналогично, если принять 0 = b0, то для правой части числа будет справедливо другое рекуррентное соотношение: i = i-1 + bi ·qi, из которого следуют:
(4)
Из соотношений (3) и (4) непосредственно вытекают два способа перевода целых чисел из 10-й системы счисления в систему с произвольным основанием q.
Способ 1 является следствием соотношений (3), из которых просматривается следующий алгоритм перевода.
Рис.1. Блок-схема алгоритма
Блок-схема алгоритма представлена на рисунке 1. Обычно его представляют в виде "лестницы".
Остатки от деления (3,4) и результат последнего целочисленного деления (4) образуют обратный порядок цифр нового числа. Следовательно, 12310 = 4435.
Необходимо заметить, что полученное число нельзя читать "четыреста сорок три", поскольку десятки, сотни, тысячи и прочие подобные обозначения чисел относятся только к десятичной системе счисления. Прочитывать число следует простым перечислением его цифр с указанием системы счисления ("число четыре, четыре, три в пятеричной системе счисления").
Способ 2 вытекает из соотношения (4); действия производятся в соответствии со следующим алгоритмом:
Продемонстрируем
действие алгоритма на той же задаче, что была рассмотрена выше. Определить m–1
можно либо путем подбора (50=1<123; 51=5<123; 52=25<123;
53=125>123, следовательно, m–1 =2), либо логарифмированием с
оставлением целой части логарифма (log5123=2,99, т.е. m–1=2).
Далее:
b2 = 123 div 52 = 4;
1 = 123 mod 52 = 23;
(i = 2 - 1 = 1);
b1 = 23 div 51 = 4;
0 = 23 mod 51 = 3;
i = 0.
Алгоритмы перевода
ZpZ10
явно вытекает из представлений (1) или (2): необходимо
Zp
представить в форме многочлена и выполнить все операции по правилам десятичной
арифметики.
4435 = 4·52+4·51+3·50 = 4·25+4·5+3·1 = 12310.
Необходимо еще раз
подчеркнуть, что приведенными алгоритмами удобно пользоваться при переводе
числа из десятичной системы в какую-то иную или наоборот. Они работают и для
перевода между любыми иными системами счисления, однако, преобразование будет
затруднено тем, что все арифметические операции необходимо осуществлять по
правилам исходной (в первых алгоритмах) или конечной (в последнем алгоритме)
системы счисления. По этой причине переход, например, Z3
Z8
проще осуществить через промежуточное преобразование к 10-й системе
Z3
Z10
Z8.
Ситуация, однако, значительно упрощается, если основания исходной и конечной
систем счисления оказываются связанными соотношением p = qr, где r –
целое число (естественно, большее 1) или r = 1/n ( n>1, целое) – эти случаи
будут рассмотрены ниже.
На следующем шаге мы рассмотрим перевод дробных чисел из одной системы счисления в другую.
Пример 3. Выполнить преобразование 4435
Z10