|
|
Перевести натуральное число n в систему счисления с основанием p. |
|
Очевидно, в результате нужно получить
разложение числа n в позиционной
нумерации Ap, то есть
символьную строку вида akak-1... a1a0 (ai принадлежит Ap), которая
соответствует сумме n=ak*pk+ak-1*pk-1+...+a
1*p1+a0. В частном
случае, при p=10, мы как раз и имеем
"обычное" десятичное разложение.
|
| Пример #1. |
|
Проиллюстрируем механизм работы алгоритма на
примере перевода числа 41210
в 6-ричную нумерацию. Как видим, он представляет собой обычное
деление в столбик; получающиеся остатки и есть символы из
разложения числа в новой нумерации; а последнее частное -
старший символ в разложении. Получаем: 15246. Таблица справа отражает
пошаговое изменение переменных, используемых в программе.
Отметим, что приведенная ниже программная
реализация алгоритма связана с некоторыми ограничениями.
Во-первых, как значение аргумента, так и значение функции не
должны выходить за пределы выделенного им диапазона, хотя
можно было бы предусмотреть и контроль. Во-вторых, поскольку в
вычислениях применяются операции div и mod, используемые в языке программирования для
обработки десятичных чисел, да и результат тоже представлен
как десятичная запись - символами из A10, - мы ограничимся диапазоном
2£p£9. Разумеется, последнее ограничение
нетрудно снять, но тогда придется использовать структуру
данных типа линейный массив, а мы пока обсуждаем
алгоритмы, работающие с неструктурированными данными.
type
t = 2..9;
function Decimal_P (n : word; p : t) : longint;
var
a, r : longint;
begin
a := 0; r := 1;
while n >= 1 do
begin
a := a + (n mod p) * r;
r := r * 10;
n := n div p
end;
Decimal_P := a
end;
|
При работе алгоритма Decimal_P
очередные символы разложения вычисляются от правого края записи к
левому, от a0 к ak.
Можно предложить иной вариант (назовем его Dec_P_v2), когда разложение формируется в
противоположном порядке - слева направо, от ak к a0. Для этого следует
затем, на каждом очередном шаге k, определять значение множителя ak из алфавита Ap, минимизирующее разность (n-ak*pk).
Ясно, что этот алгоритм, в сравнении с предыдущим,
более трудоемок. Однако в ряде частных случаев он вполне
жизнеспособен.
Так, при p=2 в алфавите A2 только два элемента, 0 и 1. Поэтому и вычисления столь
элементарны, что их несложно проделывать в уме (вспомним: таблицу
степеней 2 мы давно выучили наизусть - Занятие
B1
Для того же примера с числом n=412:
Конечно, нет смысла подменять компьютер и
подсовывать ему собственную реализацию перевода вводимых десятичных
данных в двоичный код, кроме как в учебных целях.
Назад
|
