Задание 14 ЕГЭ по информатике. Позиционные системы счисления.

Краткая теория

• Позиционные системы счисления — системы, где значение цифры зависит от её позиции (разряда).
• Чтобы перевести число 12345<sub>N</sub> в десятичную систему, нужно:1·N⁴ + 2·N³ + 3·N² + 4·N¹ + 5·N⁰
• Последняя цифра числа в системе с основанием N — это остаток от деления на N.
• Число 10<sub>N</sub> — единица и N нулей; 10<sub>N</sub>−1 — N девяток (или N−1 в любой системе).
• a<sup>N</sup>−1 в системе с основанием a записывается как N старших цифр (a−1).

Стандартные функции Python для перевода

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

• bin(x) → двоичная форма (строка с префиксом 0b)
• oct(x) → восьмеричная форма (строка с префиксом 0o)
• hex(x) → шестнадцатеричная форма (строка с префиксом 0x)

n = 67
print(bin(n))  # 0b1000011
print(oct(n))  # 0o103
print(hex(n))  # 0x43

Чтобы убрать префикс, используем срез: bin(n)[2:].

Использование функции int()

Функция int() позволяет переводить строку, представляющую число в системе с основанием от 2 до 36, в десятичное число:

print(int("1010", 2))   # 10
print(int("7B", 16))    # 123
print(int("234", 5))    # 69

⚠️ Максимальное основание = 36, так как для обозначения цифр используются символы 0–9 и A–Z.

Алгоритмы перевода чисел

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

Алгоритм (Horner):
┌───────────────────────────────────────────────┐
│ Вход: строка s = cₖ…c₂c₁c₀ (в базе N)          │
│ Выход: десятичное значение                    │
├───────────────────────────────────────────────┤
│ value := 0                                    │
│ для каждой цифры c из s слева направо:        │
│    value := value * N + val(c)                │
│ вернуть value                                 │
└───────────────────────────────────────────────┘

Пример: s = 234₅
value = 0
→ (2): value = 0*5 + 2 = 2
→ (3): value = 2*5 + 3 = 13
→ (4): value = 13*5 + 4 = 69
Ответ: 69₁₀

Каждая цифра умножается на основание в степени разряда:

234<sub>5</sub> = 2·5² + 3·5¹ + 4·5⁰ = 50 + 15 + 4 = 69

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

Алгоритм (целая часть):
┌─────────────────────────────────────────┐
│ Вход: десятичное число X, основание N   │
│ Выход: запись X в системе с основанием N│
├─────────────────────────────────────────┤
│ пока X > 0:                             │
│   r := X mod N        ← остаток (цифра) │
│   X := X div N        ← целая часть     │
│   записать r слева к уже найденным      │
│ если цифр нет → результат "0"           │
└─────────────────────────────────────────┘

Пример: X=69, N=5
┌───────────┬──────────┬────────────┬─────────────┐
│ Итерация  │  X : N   │  Остаток r │  Новая X    │
├───────────┼──────────┼────────────┼─────────────┤
│    1      │ 69 : 5   │     4      │    13       │
│    2      │ 13 : 5   │     3      │     2       │
│    3      │  2 : 5   │     2      │     0       │
└───────────┴──────────┴────────────┴─────────────┘
Читаем остатки снизу вверх → 234₅

Используется деление с остатком:

• Делим число на основание N.
• Запоминаем остаток.
• Продолжаем, пока частное ≠ 0.
• Читаем остатки в обратном порядке.

69 : 5 = 13 остаток 4
13 : 5 = 2 остаток 3
2 : 5 = 0 остаток 2
=> 234<sub>5</sub>

Реализация функций перевода в Python

Цикл

def dec2base(n, base):
    digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    res = ""
    while n > 0:
        res = digits[n % base] + res
        n //= base
    return res or "0"

print(dec2base(69, 5))  # 234

Рекурсия

def dec2base_rec(n, base):
    digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    if n < base:
        return digits[n]
    return dec2base_rec(n // base, base) + digits[n % base]

print(dec2base_rec(69, 5))  # 234

Работа с буквами

Отображение цифр:
0 1 2 3 4 5 6 7 8 9 A  B  C  D  E  F  ...  Z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... 35

Пример (HEX): 0x7B  = 7*16 + 11 = 123
Пример (BASE-36): "AZ" = 10*36 + 35 = 395

Для оснований больше 10 цифры выше 9 заменяются буквами: A=10, B=11, ... F=15.
При переводе используем строку-алфавит: abc = "0123456789ABCDEF"

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

def base2dec(s, base):
    digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    s = s.upper()
    n = 0
    for ch in s:
        n = n * base + digits.find(ch)
    return n

print(base2dec("234", 5))  # 69

Разбор типовых заданий

Задание 1

49⁷ + 7²¹ − 7. Найти количество цифр 6 в 7-ичной записи.

res = 49**7 + 7**21 - 7
count6 = 0
while res > 0:
    if res % 7 == 6:
        count6 += 1
    res //= 7
print(count6)

Задание 2

Сколько значащих нулей в двоичной записи числа 4**512 + 8**512 − 2**128 − 250?

res = 4**512 + 8**512 - 2**128 - 250
print(bin(res)[2:].count('0'))

Задание 3

Число 67₁₀ в системе с основанием N оканчивается на 1 и содержит 4 цифры. Найти N.

def dec2x(dig, x):
    res = ''
    while dig:
        d = dig % x
        res = (chr(ord('A') + d - 10) if d >= 10 else str(d)) + res
        dig //= x
    return res

for i in range(2, 36):
    d = dec2x(67, i)
    if d.endswith('1') and len(d) == 4:
        print(i)
        break

Контрольные вопросы и мини-задания

1. Что такое позиционная система счисления?
2. Как перевести число из системы N в 10-ичную?
3. Почему функция int() принимает основание до 36?
4. Чему равен результат int('F', 16)?
5. Сколько значащих нулей имеет число 16**3 в шестнадцатеричной записи?
6. Переведите 345₁₀ в систему с основанием 8.
7. Как записывается 2ⁿ − 1 в двоичной системе?
8. Какое наименьшее основание системы, в которой 30 — трёхзначное число?
9. Запишите число 255 в 16-ричной и 8-ричной системах.
10. Напишите функцию, возвращающую количество цифр «A» в 16-ричной записи чисел от 100 до 200.