Задание 14 ЕГЭ по информатике: системы счисления и выражения — разбор и примеры

Задание 14 проверяет работу с позиционными системами счисления. В одних вариантах нужно записать значение большого выражения со степенями в некоторой системе и посчитать, сколько в записи определённых цифр. В других — в числах, записанных в системе с основанием 11–20, есть неизвестная цифра x, и нужно подобрать x так, чтобы выполнилось условие делимости. На компьютерном экзамене оба типа надёжно решаются перебором на Python, но понимать устройство записи полезно — это помогает заметить ошибку в программе.

Что проверяет задание

• понимание позиционной записи: число abc в системе с основанием q равно a*q**2 + b*q + c;
• умение представлять степени основания: q**k — это единица и k нулей;
• знание, как выглядит q**k - 1 (k цифр q−1) и разность степеней;
• умение организовать перебор неизвестной цифры и перевод из любой системы.

Типичные формулировки

1. «Значение выражения 9**40 + 3**30 - 27 записали в системе счисления с основанием 3. Сколько цифр 2 содержится в этой записи?»
2. «Сколько значащих нулей / ненулевых цифр в записи?»
3. «Операнды выражения записаны в системе с основанием 12, x — неизвестная цифра. Найдите x, при котором значение делится на 19, и запишите частное в десятичной системе».
4. «Найдите наибольшее/наименьшее x, при котором…» — когда подходящих значений несколько.

Пошаговый метод: цифры в записи выражения

1. Приведите все степени к основанию системы: 9**40 = 3**80, 27 = 3**3.
2. Вспомните вид степеней: 3**80 в троичной записи — единица и 80 нулей.
3. Разность степеней q**a - q**b при a > b записывается как (a−b) цифр q−1, за которыми идут b нулей.
4. Сложите части, следя за тем, не перекрываются ли разряды.
5. Проверьте программой: переведите число в систему делением с остатком и посчитайте цифры.

Разбор примера 1

Значение выражения 9**40 + 3**30 - 27 записали в троичной системе. Сколько в записи цифр 2?

9**40 = 3**80 — это 1 и 80 нулей. 3**30 - 27 = 3**30 - 3**3 — это 27 двоек, за которыми идут 3 нуля (всего 30 разрядов). Части не перекрываются: старшая единица стоит в 81-м разряде, а разность занимает младшие 30 разрядов. Получаем запись: 1, затем 50 нулей, затем 27 двоек и 3 нуля. Двоек в записи 27.

Ответ: 27.

Пошаговый метод: неизвестная цифра x

1. Определите допустимые значения x: цифра системы с основанием q принимает значения от 0 до q−1. Если x стоит первой цифрой, иногда 0 запрещён — смотрите условие.
2. Переберите все x и для каждого переведите числа в десятичную систему.
3. Проверьте условие (делимость, равенство) и выпишите подходящие x.
4. Посчитайте то, что спрашивают: частное, сумму, само x.

Разбор примера 2

Числа 5x13 и x7x записаны в системе счисления с основанием 12, x обозначает одну и ту же цифру этой системы (от 0 до 11). Найдите x, при котором сумма чисел делится на 19, и запишите частное от деления суммы на 19 в десятичной системе.

Переведём числа в общем виде: 5x13 = 5*1728 + x*144 + 1*12 + 3 = 8655 + 144x; x7x = x*144 + 7*12 + x = 84 + 145x. Сумма: 8739 + 289x. Перебирая x от 0 до 11, находим единственное подходящее значение x = 5: сумма равна 8739 + 1445 = 10 184 = 19 × 536.

Ответ: 536.

Код на Python

Функция int(строка, основание) переводит запись из любой системы с основанием до 36 в десятичное число. Для перевода в систему обратно пишется короткий цикл деления с остатком.

# пример 1: цифры в записи
x = 9**40 + 3**30 - 27
digits = []
while x > 0:
    digits.append(x % 3)
    x //= 3
print(digits.count(2))      # 27

# пример 2: неизвестная цифра
DIG = '0123456789AB'
for x in range(12):
    s = int('5' + DIG[x] + '13', 12) + int(DIG[x] + '7' + DIG[x], 12)
    if s % 19 == 0:
        print(x, s // 19)   # 5 536

Python работает с целыми числами произвольной длины, поэтому 9**40 вычисляется точно. Не используйте вещественное деление / и функцию math.log для подсчёта цифр: они дают погрешность на больших числах.

Полезные факты для устного счёта

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

• q**k в системе с основанием q — это единица и k нулей, всего k + 1 цифра;
• q**k - 1 — это k цифр q − 1 (в двоичной системе — k единиц);
• q**a + q**b при a > b — две единицы, между которыми a − b − 1 нулей;
• вычитание небольшого числа из степени «превращает» хвост нулей в цифры q − 1;
• число цифр в записи N в системе с основанием q можно получить программой как длину списка остатков.

Например, двоичная запись числа 2**20 - 2**5 — это 15 единиц и 5 нулей. Такие оценки занимают полминуты и сразу показывают, если программа выдала заведомо неверный ответ, например, больше цифр, чем есть в записи.

Частые ошибки

• Неверно переводят степени: 9**40 — это 3**80, а не 3**20.
• Путают вид `qk - 1`**: это k цифр q−1 (в троичной — k двоек), а не k нулей.
• Не учитывают перекрытие разрядов при сложении нескольких слагаемых: если разность «залезает» в разряды другой степени, появляются переносы.
• В переборе x берут цифры не того диапазона: в системе с основанием 12 цифры от 0 до 11, причём 10 и 11 записываются буквами A и B.
• Записывают частное не в той системе: в условии обычно просят десятичную запись.
• При нескольких подходящих x отвечают первым найденным, хотя спрашивают наибольшее.

Потренируйтесь

Решите задания обоих типов: задания № 14 в банке. Для отработки перевода чисел программой подойдут задачи с проверкой кода. Теория — в статье «Системы счисления»; следующая тема — задание 15: истинность логических выражений.