Разбор и сборка

Ранее мы показали, что в позиционной системе счисления с основанием p число N может быть представлено в виде разложения по степеням основания, где цифры числа играют роль коэффициентов.

N_k = c_k * 10^k + c_k-1 * 10^k-1 + … + c₁ * 10¹ + c₀ * 10⁰ (*)

Примеры: Число 1234 в десятичной системе можно записать в виде: 1*10³ + 2*10² + 3*10¹ + 4*10⁰

Число 1101₂ в двоичной системе можно записать в виде: 1*10³ + 1*10² + 0*10¹ + 1*10⁰

Поскольку в двоичной системе число 10 равно 2 в десятичной системе то последнюю запись в десятичном представлении можно записать в виде: 1*2³ + 1*2² + 0*2¹ + 1*2⁰

В любой системе счисления основание системы p представимо числом 10. Поэтому для любой системы справедлива запись:

N_k = c_k * p^k + c_k-1 * p^k-1 + … + c₁ * p¹ + c₀ * p⁰ (**)

Это означает, что любое десятичное число можно представить в виде разложения по степеням основания любой системы счисления с основанием p. В роли коэффициентов при степенях основания выступают цифры системы счисления.

Запись (**) является основой для того чтобы разобрать число на цифры, если известно основание p. Задача разложения числа по степеням основания (задача разбора числа) называется задачей перевода десятичного числа в систему с основанием p.

Запись (**) является основой для решения обратной задачи - сборки числа из цифр, если известна запись числа в системе с основанием p. Задача сборки десятичного числа называется задачей перевода числа из системы с основанием p в десятичную систему.

Перевод из системы P в десятичную систему решается простыми вычислениями.

Задача дана запись числа N в двоичной системе: 10111. Перевести число в десятичную систему

10111₂ = 1*2⁰ + 1*2¹ + 1*2² + 0*2³ + 1*2⁴ = 1 + 2 +4 + 16 = 23₁₀

Задача: Дано число N в десятичной системе. Необходимо разобрать это число, получив его цифры в системе с основанием p.

Используя базисное соотношение (**), запишем число N_k в виде:

N_k = (c_k * p^k-1 + c_k-1 * p^k-2 + … + c₁) * p¹ + c₀ * p⁰ = N_k-1 * p + c₀ (***)

Сведем нашу задачу к более простой задаче, как зная N_k получить последнюю цифру этого числа - c₀ и число N_k-1,

Две замечательные операции над целыми числами помогают решить нашу задачу:

В математике и программировании нет общепринятых обозначений этих важных операций. В языке Pascal эти операции обозначаются словами: mod (остаток) и div (деление нацело). Такие же обозначения приняты при записи на алгоритмическом языке, применяемом при записи школьных программ. В языках С, С++, Java, C# операцию взятия остатка обозначает знак ‘%’, деление нацело -знак ‘/’ (предполагается, что операнды представляют целые числа). Справедливы следующие соотношения:

С₀ = N_k mod p; N_k-1 = N_k div p;

С₀ = N_k % p; N_k-1 = N_k / p; (****)

Переведем десятичное число 78 в восьмеричную систему

Шаг 1 с₀ = 78 mod 8 = 6; N = 78 div 8= 9

Шаг 2 с₁ = 9 mod 8 = 1; N = 9 div 8 = 1;

Шаг 3 c₂ = 1 mod 8 = 1; N = 1 div 8 = 0; Stop

78₁₀ = 116₈ = 64 + 8 + 6 = 78₁₀

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

Задачи для самостоятельного решения: