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

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

Задание 14 – выражение в недесятичной системе счисления.

1 балл, норматив 3 минуты.

Условия номера сводятся к трём типам, разобранным ниже:

неизвестная цифра в записи операндов – перебирается цифра под нужное условие;
нули в записи выражения – вычисляется число и считаются нули в его записи;
нули в записи выражения со слагаемым x – тот же подсчёт, но для каждого значения x.

Что нужно знать заранее:

значение записи числа в системе с основанием p: каждая цифра умножается на степень основания; подробно в учебнике: перевод из любой системы в десятичную;
цифры числа в системе p достаются с конца: n % p – последняя цифра, n //= p – отбросить её. Это обратный перевод: перевод из десятичной в любую систему;
встроенная int(s, p) переводит строку только ИЗ системы и только при $p \le 36$, а обратной функции в языке нет. Отсюда и оба приёма выше: быстрый перевод через Python.

Тип 1. Неизвестная цифра в записи

Задание 14 демонстрационного варианта ЕГЭ-2027 (ФИПИ).

Операнды арифметического выражения записаны в системе счисления с основанием 22.

$27x98876_{22} + 26x51_{22} + 711x5_{22}$

В записи чисел переменной x обозначена неизвестная цифра из алфавита 22-ричной системы счисления. Определите наименьшее значение x, при котором значение данного арифметического выражения кратно 21. Для найденного x вычислите частное от деления значения арифметического выражения на 21 и укажите его в ответе в десятичной системе счисления. Основание системы счисления указывать не нужно.

Тип 1: как рассуждать

x – это цифра, а не число. Основание системы 22 задаёт алфавит: цифры идут от 0 до 21, всего 22 варианта, и перебор мгновенный. Цифры старше 9 записываются латинскими буквами: 10 – A, 11 – B и так далее, 21 – L.
Алфавит уже есть в Python. string.digits – это '0123456789', string.ascii_uppercase – буквы от A до Z. Склеив их, получаем все цифры до 35, а первые 22 символа (alphabet[:22]) – ровно алфавит 22-ричной системы.
Подставляем x в запись и переводим через int. Каждый x – один символ, поэтому f'27{x}98876' даёт запись нужной длины, а int(запись, 22) переводит её в число.
«Наименьшее» – значит снизу вверх. Идём от нуля и останавливаемся (break) на первом подходящем x; проверять остальные незачем.
В ответ идёт не x. Найденная цифра здесь x = 3, а нам нужно частное от деления значения выражения на 21 – в десятичной системе счисления.

Ответ: 276296118.

from string import digits, ascii_uppercase

alphabet = digits + ascii_uppercase     # 0–9, затем A–Z

for x in alphabet[:22]:                 # цифры 22-ричной системы: от 0 до L
    total = int(f'27{x}98876', 22) + int(f'26{x}51', 22) + int(f'711{x}5', 22)
    if total % 21 == 0:                 # первое подходящее x и есть наименьшее
        print(total // 21)              # 276296118
        break

Тип 2. Нули в записи выражения

Задание 14 демонстрационного варианта ЕГЭ-2027 (ФИПИ, тип 2).

Значение арифметического выражения

$3 \cdot 3125^8 + 2 \cdot 625^7 - 4 \cdot 625^6 + 3 \cdot 125^5 - 2 \cdot 25^4 - 2025$

записали в системе счисления с основанием 25. Сколько значащих нулей содержится в этой записи?

Тип 2: как рассуждать

Выражение вычисляется как написано. В нём 29 десятичных цифр – для Python это обычное целое, точное до последней цифры.
Цифры снимаем с конца. Встроенной функции перевода в 25-ричную систему нет, поэтому n % 25 даёт последнюю цифру записи, а n //= 25 её отбрасывает. Цифра равна нулю – прибавляем к счётчику.
«Значащие» – значит без ведущих нулей. Цикл while n > 0 кончается вместе со старшей цифрой, ведущих нулей он не видит и считает ровно значащие.

Ответ: 10.

n = 3 * 3125**8 + 2 * 625**7 - 4 * 625**6 + 3 * 125**5 - 2 * 25**4 - 2025

count = 0
while n > 0:
    if n % 25 == 0:                 # последняя цифра 25-ричной записи – ноль
        count += 1
    n //= 25                        # отбрасываем её
print(count)                        # 10

Тип 3. Нули в записи выражения с x

Задание 14 демонстрационного варианта ЕГЭ-2027 (ФИПИ, тип 3).

Значение арифметического выражения $7^{170} + 7^{100} - x$, где x – целое положительное число, не превышающее 2030, записали в 7-ричной системе счисления. Определите наибольшее значение x, при котором в 7-ричной записи числа, являющегося значением данного арифметического выражения, содержится ровно 71 нуль.

В ответе запишите число в десятичной системе счисления.

Тип 3: как рассуждать

x здесь не цифра, а слагаемое. «Целое положительное, не превышающее 2030» – это числа от 1 до 2030 включительно: range(1, 2031). Идти можно и сверху вниз, range(2030, 0, -1), – тогда первое найденное значение сразу наибольшее.
Считаем значение выражения целиком. Python держит $7^{170}$ точно, без округления: целые числа в нём не ограничены по длине. 2030 вариантов по паре сотен цифр – доли секунды, оптимизировать тут нечего.
Нули считаем тем же циклом, что в типе 2: n % 7 – последняя цифра, n //= 7 – отбросить её. Раз цикл нужен для каждого x, он вынесен в функцию zeros.
«Наибольшее» – значит сверху вниз. break на первом подходящем x.

Ответ: 2029.

def zeros(n, p):
    # сколько нулей в записи числа n в системе с основанием p
    count = 0
    while n > 0:
        if n % p == 0:
            count += 1
        n //= p
    return count


for x in range(2030, 0, -1):        # наибольшее x – перебираем сверху вниз
    if zeros(7**170 + 7**100 - x, 7) == 71:
        print(x)                    # 2029
        break

Типичные ошибки

Перебор x числами. При x от 10 запись f'27{x}98876' получает две цифры вместо одной и становится другим числом. Перебирать нужно символы alphabet[:22].
Ответили не на тот вопрос. В типе 1 записали x вместо частного, в типе 3 – число нулей вместо x. Вопрос надо внимательно читать.
Деление / вместо //. / возвращает float с точностью около 16 цифр. В типе 2 у числа 29 цифр, младшие теряются, и int(n / 25) даёт 8 нулей вместо 10.
Промахнулись с границей перебора. «Не превышающее 2030» включает 2030, а range(2030) заканчивается на 2029 и начинается с нуля, хотя x положительное. Правая граница range в перебор не входит, поэтому пишут range(1, 2031).