Как найти минимальное основание системы счисления числа

Переведём все строки-числа в массивы со значениями их цифр. Запишем их задом-наперед. Более короткие дополним нулями:

A: 1A -> [10, 1]
B: 2  -> [ 2, 0]
C: 20 -> [ 0, 2]

Пройдемся слева направо имитируя сложение в столбик. Рассмотрим сумму младших разрядов: если бы переноса не возникло, то A[0] + B[0] == C[0]. Это не так (10 + 2 != 0). Значит есть перенос и A[0] + B[0] == base + C[0]. Можно вычислить основание системы счисления.

В следующем разряде нужно учесть пришедший перенос: A[1] + B[1] + carry == C[1]. Равенство выполнено, проверять основание не надо.

Продвигаясь по разрядам выполняем сложение в столбик. При каждом переносе проверяем основание – все переносы должны дать один результат. Кроме этого основание должно быть больше всех цифр в во всех трёх числах.

def read_number(s):
    alphabet = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    return list(map(alphabet.index, reversed(s)))


def align(lists):
    max_length = max(map(len, lists))
    for l in lists:
        l.extend([0] * (max_length - len(l)))


def determine_base(a, b, c):
    align((a, b, c))
    max_digit = max(a + b + c)
    base = None
    carry = 0
    for ai, bi, ci in zip(a, b, c):
        s = ai + bi + carry
        if s < ci:
            return -1
        if s > ci:
            if base is None:
                base = s - ci
                if base <= max_digit:
                    return -1
            if s - ci != base:
                return -1
            carry = 1
        else:
            carry = 0
    if carry != 0:
        return -1
    if base is None:
        return max_digit + 1
    return base

    
def main():
    a, b, c = tuple(map(read_number, input().split()))
    print(determine_base(a, b, c))


main()

Изменение основания для позиционных систем счисления

В позиционной системе счисления с основанием q число может быть представлено в виде полинома

… + a₂∙q²+ a₁q¹ + a₀∙q⁰ + a_-1∙q^-1 + a_-2∙q^-2 + …

где коэффициенты a_i – это цифры системы счисления с основанием q.

Например, в десятичной системе счисления

124.733 = 1∙10² + 2∙10¹ + 4∙10⁰ + 7∙10^-1 + 3∙10^-2 + 3∙10^-3

Число цифр в системе счисления с основанием q равно q, при этом максимальная цифра равна q – 1. Цифра не может стать равной q, потому что в этом случае произойдёт перенос
единицы в новый разряд.

Например, нужно найти минимальное основание системы счисления, в которой записано число 7832. Так как максимальная цифра равна 8, то минимальное значение q = 8 + 1 = 9.

Основанием системы счисления может быть, в принципе, любой число: целое, отрицательное, рациональное, иррациональное, комплексное и т.д. Будем рассматривать только положительные целые основания.

Особый интерес для нас будут представлять основание 2 и основания, являющиеся степенью двойки – 8 и 16.

В случае, если основание с. с. больше десяти, то новые цифры берутся по порядку из алфавита. Например, для 16-ричной системы это будут цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

Перевод целой части десятичной системы счисления

Первый способ перевода из десятичной системы счисления в n-ричную заключается в последовательном делении числа на новое основание.

123₁₀ → X₁₂

123/12 = 10 (3)
10/12 = 0 (10=A)

Собираем в обратном порядке, сначала последнее значение (это 0), потом сверху вниз все остатки. Получаем 0A3 = A3

4563₁₀ → X₈

4563/8 = 570 (3)
570/8 = 71 (2)
71/8 = 8 (7)
8/8 = 1 (0)

Собираем обратно, получаем 10723

3349₁₀ → X₁₆

3349/16 = 209 (5)
209/16 = 13 (1)
13/16 = 0 (13 = D)

Собираем вместе: 0D15 = D15

545₁₀ → X₂

545/2 = 272 (1)
272/2 = 136 (0)
136/2 = 68 (0)
68/2 = 34 (0)
34/2 = 17 (0)
17/2 = 8 (1)
8/2 = 4 (0)
4/2 = 2(0)
2/2 = 1 (0)
1/2 = 0(1)

Собираем 01000100001 = 1000100001

Перевод на бумаге обычно осуществляется делением в столбик. Пока деление не приведёт к нулю, каждый следующий ответ делится на основание с. с. В конце, из остатков от деления собирается ответ.

Также часто можно перевести число в другую с. с. , если в уме представить его как сумму степеней соответствующего основания, в которое мы хотим перевести число.

Например, 129 очевидно 128 + 1 = 2⁷ + 1 = 10000001₂

80 = 81 – 1 = 3⁴ – 1 = 10000 – 1 = 2222₃

Перевод в десятичную систему счисления целой части

Перевод осуществляется, используя представление числа в позиционной системе счисления. Пусть необходимо перевести A3₁₂ → X₁₀
Известно, что A3 – это 3∙q⁰ + A∙q¹, то есть 3*1 + A*12 = 3 + 120 = 123

10723₈ → X₁₀

1∙q⁴ + 0∙q³ + 7∙q² + 2∙q¹ + 3∙q⁰ = 1∙8⁴ + 0 + 7∙8² + 2∙8 + 3 = 1∙4096 + 7∙64 + 2∙8 + 3 = 4563

D15₁₆ → X₁₀

D∙16² + 1∙16¹+5∙16⁰ = 13∙256 + 16 + 5 = 3349

1000100001₂ → X₁₀

2⁹ + 2⁵ + 1 = 512 + 32 + 1 = 545.

Перевод на бумаге обычно осуществляется следующим образом. Над каждой цифрой по порядку пишут номер степени. Затем уже выписывают все слагаемые.

Перевод дробной части из десятичной системы

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

0.625₁₀ → X₂

0.625 * 2 = 1.250 (1)
0.25 * 2 = 0.5 (0)
0.5 * 2 = 1.0 (1)

0 – дальнейшее умножение будет давать только нули

Собираем сверху вниз, получаем 0.101

0.310 → X2
0.3 * 2 = 0.6 (0)
0.6 * 2 = 1.2 (1)
0.2 * 2 = 0.4 (0)
0.4 * 2 = 0.8 (0)
0.8 * 2 = 1.6 (1)
0.6 * 2 = 1.2 (1)

0.2 … получим периодическую дробь

Собираем, получаем 0.0100110011001… = 0.0(1001)

0.64510 → X5
0.645 * 5 = 3.225 (3)
0.255 * 5 = 1.275 (1)
0.275 * 5 = 1.375 (1)
0.375 * 5 = 1.875 (1)
0.875 * 5 = 4.375 (4)
0.375 * 5 = 1.875 (1)
…

0.3111414… = 0.311(14)

Перевод дробной части в десятичную систему

Осуществляется аналогично переводу целой части, путём домножения цифры разряда на основание в степени, равной положению разряда в числе.

0.101₂ → X₁₀

1∙2^-1 + 0∙2^-2 + 1∙2^-3 = 0.5 + 0.125 = 0.625

0.134₅ → X₁₀

1∙5^-1 + 3∙5^-2 +4∙5^-3 = 0.2 + 3∙0.04 + 4∙0.008 = 0.2 + 0.12 + 0.032 = 0.352

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

Перевод из произвольной системы счисления в произвольную с. с. осуществляется с помощью десятичной с. с.

X_N → X_M ≡ X_N → X₁₀ → X_M

Например

1221201₃ → X₇

1221201₃ = 1∙3⁶ + 2∙3⁵ + 2∙3⁴ + 1∙3³ + 2∙3² + 1 = 729 + 2∙243 + 2∙81 + 27 + 9 + 1 = 1414₁₀

1414/7 = 202 (0)
202/7 = 28 (6)
28/7 = 4 (0)
4/7 = 0 (4)

4060₇

1221201₃ → 4060₇

Родственные системы счисления

Системы счисления называют родственными, когда их основания являются степенями одного числа. Например, 2, 4, 8, 16. Перевод между родственными системами счисления можно осуществлять, воспользовавшись таблицей

Таблица для перевода между родственными системами счисления с базой 2

10	2	4	8	16
0	0000	000	00	0
1	0001	001	01	1
2	0010	002	02	2
3	0011	003	03	3
4	0100	010	04	4
5	0101	011	05	5
6	0110	012	06	6
7	0111	013	07	7
8	1000	020	10	8
9	1001	021	11	9
10	1010	022	12	A
11	1011	023	13	B
12	1100	030	14	C
13	1101	031	15	D
14	1110	032	16	E
15	1111	033	17	F

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

Для 123₄ единица подменяется на 01, двойка на 10, тройка нa 11, получаем 11011₂

Для 5721₈ соответственно 101, 111, 010, 001, итого 101111010001₂

Для E12₁₆ получим 111000010010₂

Для перевода из двоичной системы следует разбить число на двойки (4-я), тройки (8-я) или четвёрки чисел (16-я), а затем подменить на соответствующие значения.

110100101₂ = 01.10.10.01.01 = 12211₄

110100101₂ = 110.100.101 = 645₈

110100101₂ = 0001.1010.0101 = 1A5₁₆

Переход из одной родственной системы в другую осуществляется транзитом через наименьшее основание, в нашем случае через двойку.

33232₄ → X₁₆

33232₄ → 1111101110₂ → 0011.1110.1110 → 3EE₁₆

Понятно, что все эти рассуждения применимы и для систем счисления 3, 9, 21, 81 и 5, 25, 125 и т.п.

Q&A