Системы счисления

Система счисления

Система счисления — символический метод записи чисел, представление чисел с помощью письменных знаков.

Системы счисления подразделяются на:

позиционные (десятичная и др.);
непозиционные (римские цифры);
смешанные (представление времени в виде количества суток, часов, минут и секунд).

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

Позиционная система счисления определяется целым числом \(b > 1\), называемым основанием системы счисления. Система счисления с основанием \(b\) также называется \(b\)-ичной (в частности, двоичной, троичной, десятичной и т.п.).

Число \(x\) в \(b\)-ичной системе счисления представляется в виде:

\(x = \displaystyle\sum_{k=0}^{n-1} a_k \cdot b^k\)

где \(a_k\) — цифра, удовлетворяющая неравенству \(0 \leq a_k \leq b - 1\).

Для записи чисел в системах счисления с основанием до \(36\) включительно в качестве цифр (знаков) используются арабские цифры (\(0\), \(1\), \(2\), \(3\), \(4\), \(5\), \(6\), \(7\), \(8\), \(9\)) и, затем, буквы латинского алфавита (\(a\), \(b\), \(c\) и т.д.). При этом, \(a = 10\), \(b = 11\) и т. д.

При одновременной работе с несколькими системами счисления для их различения основание системы обычно указывается в виде нижнего индекса, который записывается в десятичной системе:

● \(123_{10}\) — это число \(123\) в десятичной системе счисления;

● \(173_8\) — то же число в восьмеричной системе счисления;

● \(1111011_2 \) — то же число, но в двоичной системе счисления.

Переход к другому основанию

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

Если целое число в \(b\)-ичной системе счисления равно

\(a_n a_{n-1} \ldots a_1 a_0\)

то для перевода в десятичную систему вычисляем следующую сумму:

\(\displaystyle\sum_{k=0}^{n} a_k \cdot b^k = a_0 \cdot b^0 + a_1 \cdot b^1 + \ldots + a_n \cdot b^n\)

Например:

\(101100_2 = 0 \cdot 2^0 + 0 \cdot 2^1 + 1 \cdot 2^2 + 1 \cdot 2^3 + 0 \cdot 2^4 + 1 \cdot 2^5 = 4 + 8 + 32 = 44\)

Для перевода в десятичную систему счисления можно использовать функцию int:

>>> int('101100', 2)
44

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

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

Переведём число \(44_{10}\) в двоичную систему:

\(44\) делим на \(2\): частное \(22\), остаток \(0\)
\(22\) делим на \(2\): частное\(11\), остаток \(0\)
\(11\) делим на \(2\): частное \(5\), остаток \(1\)
\(5\) делим на \(2\): частное \(2\), остаток \(1\)
\(2\) делим на \(2\): частное \(1\), остаток \(0\)
\(1\) делим на \(2\): частное \(0\), остаток \(1\)

Частное равно нулю — деление закончено. Теперь, записав все остатки снизу вверх, получим число \(101100_2\).

В языке Python есть встроенные функции, которые позволяют перевести число из десятичной системы счисления в двоичную, восьмеричную и шестнадцатеричную:

>>> bin(123) # двоичная
'0b1111011'
>>> oct(123) # восьмеричная
'0o173'
>>> hex(123) # шестнадцатеричная
'0x7b'

Ниже показана функция dec_to_base, которая переводит число n из десятичной системы счисления в систему счисления с основанием \(base\):

def dec_to_base(n, base):
    if n == 0:
        return '0'
    table = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    r = ''
    while n > 0:
        o = n % base
        r = table[o] + r
        n //= base
    return r

Чтобы перевести число из k-й системы счисления в \(m\)-ю систему счисления, нужно:

Перевести число из из \(k\)-й системы счисления в десятичную.
Полученное в десятичной системы счисления число перевести в \(m\)-ю систему счисления.

Римские цифры

Римские цифры — цифры, использовавшиеся древними римлянами в их непозиционной системе счисления.

Правила записи римских чисел

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

Римскими цифрами можно записать целые числа от \(1\) до \(3999\). Число представляется в виде суммы тысяч, сотен, десятков и единиц. Далее из следующей таблицы берётся по одному элементу, соответствующему тысячам, сотням, десяткам, единицам ровно в таком порядке.

Цифра	Тысячи	Сотни	Десятки	Единицы
`1`	`M`	`C`	`X`	`I`
`2`	`MM`	`CC`	`XX`	`II`
`3`	`MMM`	`CCC`	`XXX`	`III`
`4`		`CD`	`XL`	`IV`
`5`		`D`	`L`	`V`
`6`		`DC`	`LX`	`VI`
`7`		`DCC`	`LXX`	`VII`
`8`		`DCCC`	`LXXX`	`VIII`
`9`		`CM`	`XC`	`IX`

Если число тысяч, сотен, десятков, единиц равно \(0\), то из соответствующего столбца ничего не берётся. Например, число \(1990\) записывается, как \(1000 + 900 + 90 = \mathrm{MCMXC}\).

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

Для перевода в римскую систему счисления сделаем словарь из десятичных чисел и их аналогов в римской системе в порядке убывания:

ROMAN_NUMBERS = {
    'M': 1000,
    'CM': 900,
    'D': 500,
    'CD': 400,
    'C': 100,
    'XC': 90,
    'L': 50,
    'XL': 40,
    'X': 10,
    'IX': 9,
    'V': 5,
    'IV': 4,
    'I': 1
}

Алгоритм можно записать следующим образом:

Берём наше число и смотрим, какое максимальное число из нашего словаря можно оттуда вычесть.
Для этого мы проходим словарь слева направо (поэтому мы сразу отсортировали его по убыванию) и как только находим первое подходящее число — вычитаем его из нашего.
Сразу после этого мы добавляем к результату букву (одну или две), которая соответствовала вычтенному числу.
Так раз за разом алгоритм будет уменьшать наше исходное число и добавлять буквы к римскому.
Когда от нашего числа ничего не останется (станет равно нулю), алгоритм остановится, а буквы, которые мы добавляли, и дадут нам римское число.

Ниже показана функция dec_to_roman, которая переводит число \(n\) из десятичной системы счисления в римскую:

def dec_to_roman(n):
    res = ''
    for roman, dec in ROMAN_NUMBERS.items():
        k = n // dec
        n %= dec
        res += k * roman
    return res

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

Будем обходить строку, состоящую из римских цифр, слева направо.
Рассматриваем два соседних символа: если они формируют правильное римское число (из словаря ROMAN_NUMBERS), то к ответу добавляем его десятичное число и пропускаем эти два символа.
Иначе наше число состоит из одной римской цифры, значит к ответу добавляем десятичной аналог (из словаря ROMAN_NUMBERS) и пропускаем один символ.
Когда рассмотрим всю строку, состоящую из римских цифр, алгоритм останавливается.

Ниже показана функция roman_to_dec, которая переводит число n из десятичной системы счисления в римскую:

def roman_to_dec(s):
    s += '-'
    res = 0
    i = 0
    while i < len(s) - 1:
        if s[i] + s[i + 1] in ROMAN_NUMBERS:
            ans += ROMAN_NUMBERS[s[i] + s[i + 1]]
            i += 2
        else:
            ans += ROMAN_NUMBERS[s[i]]
            i += 1
    return res

Практические задания

Авторизация