Системы счисления в задачах

В задачах разных уровней сложности иногда встречаются системы счисления, но чаще всего суть таких задач заключается не в переводе чисел из одной системы в другую. Почти всегда эти задачи лучше характеризует другая тема. Это может быть динамическое программирование, теория чисел, комбинаторика, да и любая другая. Системы счисления в этих задачах представляют собой лишь элемент условия, но не решения. Поэтому материал этой лекции стоит рассматривать лишь как ознакомительный: для решения большинства задач на системы счисления его будет недостаточно.

Позиционные системы счисления

Системы счисления, с которыми мы сталкиваемся повседневно - десятичная, двоичная и шестнадцатеричная - являются т.н. позиционными системами счисления. Позиционная система счисления характеризуется основанием - целым числом, большим 1. Числа записываются как последовательность “цифр” (это могут быть как привычные нам цифры, так и буквы и любые другие символы). Позиция цифры в числе влияет на порядок, который она описывает (отсюда название “позиционные”). Значимость (описываемый порядок) цифры повышается справа налево. Например, рассмотрим запись “547” как число в позиционной системе с произвольным основанием \(b\):

\[547_b = 5 * b^2 + 4 * b^1 + 7 * b^0\]

Как можно заметить, каждая цифра описывает коэффициент перед определённой степенью основания. Давайте примем \(b = 21\), и выразим значение этого числа в десятичной системе счисления:

\[547_{21} = 5 * 21^2 + 4 * 21^1 + 7 * 21^0 = 2205 + 84 + 7 = 2296_{10}\]

В системе с основанием \(b\) существуют “цифры” значениями от \(0\) до \(b - 1\). Для “цифр” со значением больше \(9\) традиционно используют латинские буквы. Например, в шестнадцатиричной системе, также часто встречающейся в информатике, используются буквы от \(A\) до \(F\) для “цифр” от \(10\) до \(15\):

\[BEEF_{16} = 11 * 16^3 + 14 * 16^2 + 14 * 16^1 + 15 * 16^0 = 45056 + 3584 + 224 + 15 = 48879_{10}\]

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

Так как речь идёт о переводе между системами счисления в информатике, нужно сразу отметить важный момент. “Числа” в информатике могут быть представлены разными типами данных: числами (int) и строками (string). Можно сказать, что тип int не учитывает систему счисления чисел, а хранит лишь их значение (что логично, ведь система счисления - это всего лишь способ представления, или записи). Для работы с системами счисления используются строки. Чтобы перевести число из одной системы счисления (string) в другую (string), нужно сначала найти его значение (int), а потом записать это значение в конечной системе счисления. Другими словами, нужно выполнить два действия.

Давайте рассмотрим эти действия на примере: будем переводить числа из 12-ичной системы в 32-ичную. Сначала нам нужно найти значение числа, представленного строкой в 12-ичной системе. Алгоритм тривиален: просто выполним те же действия, которые мы разбирали в предыдущем разделе.

Реализация на C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//Перевод символа "цифры" в её значение.
int get_digit_value(char d) {
    if ('0' <= d && d <= '9') {
        return d - '0';
    } else {
        return d - 'A' + 10;
    }
}

int get_number_value(string num) {
    int result = 0;

    int len = num.length();
    //Обрабатываем "цифры" справа налево,
    //каждая описывает коэффициент перед очередной степенью основания (12).
    for (int i = len - 1; i >= 0; i--) {
        //рекомендуется использовать собственную реализацию pow
        result += get_digit_value(num[i]) * pow(12, len - 1 - i);
    }

    return result;
}

Выражение числа в 32-ичной системе счисления тоже выполняется тривиально. Заметим следующее свойство:

\[abcd_{32} = a * 32^3 + b * 32^2 + c * 32 + d,\ где\ d < 32\]

Давайте рассмотрим целую часть и остаток от деления числа на 32:

\[\left\lfloor {abcd_{32} \over 32} \right\rfloor = a * 32^2 + b * 32 + c = abc_{32} \\ abcd_{32} \bmod 32 = d = d_{32}\]

Это позволяет нам найти последнюю цифру числа, записать её, и откинуть. Для записи всего числа просто будем повторять это действие, пока левая часть (все цифры кроме последней) не станет равной нулю.

Реализация на C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//Перевод значения "цифры" в её символ.
int get_digit_char(int d) {
    if (d < 10) {
        return '0' + d;
    } else {
        return 'A' + (d - 10);
    }
}

string convert_to_32(int num) {
    string result = "";

    while (num) {
        int last_digit = num % 32;
        result += get_digit_char(last_digit);   //При добавлении цифр в начало
                                                //пришлось бы каждый раз сдвигать все остальные.
                                                //Для избежания этого, мы добавляем цифры в конец,
                                                //а в конце просто разворачиваем строку.
        num /= 32;
    }

    reverse(result.begin(), result.end());
    return result;
}

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

Непозиционные системы счисления

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