Алгоритмы перевода.

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

Алгоритм A2.

1. Положим i=0.

2. Положим равным остатку от деления на и пересчитаем по формуле

3. Если не равно нулю, то положим и переходим на шаг 2, иначе конец.

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

Трудоемкость алгоритма A2 равна .

К следующей группе относятся алгоритмы, использующие информацию об исходном представлении числа. Примером могут служить известные алгоритмы перевода из двоичной системы счисления в восьмеричную или шестнадцатеричную систему счисления. Здесь приведем алгоритм перевода из «обычной» позиционной системы счисления в сокращенную систему счисления по одинаковому основанию. Для определенности, пусть число в позиционной системе счисления хранится в ячейках , а его знак в ячейке .

Алгоритм A3.

1.Положим i=0, и нижней и верхней границе цифрового отрезка, соответственно (То есть, все цифры в сокращенном представлении числа находятся в отрезке от До ).

2. Если , то положим .

Если , то положим , .

Если , то положим , .

3. Увеличим i на 1 и если i>k, то конец, иначе вернемся на шаг 2.

Трудоемкость алгоритма A3 равна .