В задании 14 ЕГЭ по информатике работают с позиционными системами счисления, и бывает оно двух видов. В первом значение большого выражения записывают в системе с основанием b и спрашивают, сколько в записи каких-то цифр. Во втором в записи чисел стоит неизвестная цифра x, и её нужно подобрать. Python считает с целыми числами любой длины точно, поэтому оба вида решаются перебором в несколько строк. Примеры ниже запускаются прямо на странице и составлены для этой статьи: на экзамене числа будут другими, а шаблоны — те же.
Перевод в троичную систему: остатки, прочитанные снизу вверх
digits ниже, и ей всё равно, сколько в числе цифр.Цифры большого числа
Значение выражения 5 · 9³⁰ + 4 · 9¹⁵ − 3 · 9⁷ + 2 записали в системе счисления с основанием 3. Сколько цифр 2 в этой записи?
def digits(n, base):
result = []
while n > 0:
result.append(n % base)
n //= base
return result[::-1]
v = 5 * 9**30 + 4 * 9**15 - 3 * 9**7 + 2
d = digits(v, 3)
print(len(d), d.count(2))62 179**30— возведение в степень. Python считает его точно, сколько бы цифр ни вышло.digitsпереводит число делением с остатком (схема выше) и возвращает список цифр, старшая — первая.d.count(2)считает двойки. Нули считают так же —d.count(0): ведущих нулей в списке нет, так что это и есть значащие нули.
Ответ: 17.
Проверка рассуждением. 9 = 3², поэтому выражение равно 5 · 3⁶⁰ + 4 · 3³⁰ − 3¹⁵ + 2. Число 5 в троичной записи — 12, и первое слагаемое даёт в начале записи цифры 1 и 2. Середина: 4 · 3³⁰ − 3¹⁵ = 3³¹ + 3¹⁵ · (3¹⁵ − 1), а 3¹⁵ − 1 в троичной записи — пятнадцать двоек. Последнее слагаемое — ещё одна двойка в конце. Итого 1 + 15 + 1 = 17.
Делить только через //
Обычное деление / превращает число в дробное, а у дробных чисел точность — около 16 значащих цифр. На больших числах ответ поплывёт:
n = 9**30
print(n // 3)
print(int(n / 3))14130386091738734504764811067
14130386091738735239814447104Первые 16 цифр совпадают, дальше идут другие, и подсчёт цифр по такому числу неверен.
Неизвестная цифра x
Операнды выражения записаны в системе счисления с основанием 13: 7x3A2 + 2x95. Буквой x обозначена неизвестная цифра из алфавита этой системы. Найди наименьшее x, при котором значение выражения делится на 12, и для него укажи частное от деления значения на 12 в десятичной системе.
alphabet = '0123456789ABC'
def value(x):
d = alphabet[x]
return int('7' + d + '3A2', 13) + int('2' + d + '95', 13)
good = [x for x in range(13) if value(x) % 12 == 0]
print(good)
print(value(good[0]) // 12)[5, 11]
18076alphabet[x]— цифра x как символ: при x от 10 до 12 это буквы A, B, C, как в записи числа.int(s, 13)читает запись в системе с основанием 13. Буквы-цифры он понимает сам, строчные и заглавные одинаково.good— все подходящие x. Перебор идёт по возрастанию, поэтому наименьшее — первое в списке.
Ответ: 18076.
Проверка без перебора. В системе с основанием 13 остаток от деления на 12 равен остатку суммы цифр — так же, как в десятичной работает признак делимости на 9. Сумма цифр обоих чисел — 7 + x + 3 + 10 + 2 + 2 + x + 9 + 5 = 38 + 2x. Она делится на 12 при x = 5 (48) и при x = 11 (60), как и нашёл перебор.
Частые ошибки
str(x) вместо буквы. При x = 11 запись '7' + str(11) + '3A2' превращается в 7113A2 — на цифру длиннее. int прочитает её без ошибки, но число выйдет другим:
print(int('7B3A2', 13), int('7' + str(11) + '3A2', 13))224733 2630448Цифра не из алфавита. Если перебирать range(14) и дописать в алфавит букву D, Python остановится на ней: ValueError: invalid literal for int() with base 13: '7D3A2'. Цифры системы с основанием 13 — от 0 до 12, то есть range(13).
Деление через /. Дробные числа теряют цифры после 16-й значащей, поэтому для больших чисел — только // и %.
Какие ещё задания решают программой — в статье «Python для ЕГЭ по информатике», двоичная запись и автомат из задания 5 — в статье «Задание 5 ЕГЭ на Python». Свой вариант удобно проверять в песочнице Python: там можно вывести всю запись числа и посмотреть, где стоят нужные цифры.