Первые два типа задания 14 уже знакомы. В первом мы считали цифры в результате выражения, во втором подбирали неизвестную цифру внутри записи числа. Третий тип соединяет эти идеи, но делает важную замену: теперь x — целое положительное число, а не один символ из алфавита системы счисления.
Разница кажется небольшой, но именно она определяет код. Если x — цифра, мы вставляем её в f-строку и переводим запись функцией int. Если x — целое число, оно уже участвует в обычном арифметическом выражении: например, 3¹⁰⁰ − x. Никакие f-строки и алфавиты здесь не нужны.
В задаче одновременно работают два независимых механизма. Внешний цикл перебирает допустимые значения x. Внутренняя функция для каждого результата разбирает число на цифры и возвращает, сколько раз встретился ноль или другая нужная цифра. Такое разделение удобно: функция отвечает только за запись числа, а цикл — только за поиск x.
Оформим знакомый алгоритм подсчёта нулей в отдельную функцию. Названия base и count_zeros сразу подсказывают смысл лучше, чем сокращения sys и count_zero.
def count_zeros(num, base):
if num == 0:
return 1
count = 0
while num:
if num % base == 0:
count += 1
num //= base
return countФункция получает десятичное значение num и основание base. На каждом шаге num % base даёт последнюю цифру записи в этой системе. Если она равна нулю, счётчик увеличивается. Затем num //= base отбрасывает найденную цифру. Когда число заканчивается, return возвращает количество нулей во внешний код.
Проверка num == 0 нужна для общей корректности: запись числа 0 состоит из одной цифры 0, а обычный цикл while num не запустился бы ни разу. В экзаменационных примерах выражения остаются положительными, но полезно понимать этот крайний случай.
Не перепутайте «количество нулей во всей записи» с «количеством нулей в конце записи». В нашей функции проверяется каждый остаток, поэтому учитываются нули в любых разрядах. Если бы требовались только конечные нули, алгоритм остановился бы на первой ненулевой цифре и был бы другим. В условии примеров сказано «содержится ровно … нулей», значит, просматриваем запись целиком.
Внутри функции исходное значение num постепенно уменьшается. Это безопасно: переменная является локальной, а во внешнем цикле на следующей итерации expression заново вычисляется и создаёт новое value. Мы не «портим» выражение для следующих значений x.
Пусть дано выражение 5¹² − x, где x — целое положительное число, не превышающее 6. Значение выражения записывают в троичной системе. Нужно найти наибольшее x, при котором в записи ровно шесть нулей.
Сначала переводим словесное условие диапазона. «Положительное» означает x ≥ 1, а «не превышающее 6» — x ≤ 6. Значит, возможны 1, 2, 3, 4, 5 и 6. Поскольку нужен максимум, удобнее проверять их в обратном порядке: 6, 5, 4, 3, 2, 1.
Значение 5¹² равно 244 140 625. Теперь для каждого кандидата вычитаем x, переводим результат в троичную систему и считаем нули:
Дальше проверять не требуется: мы двигались от большего x к меньшему, поэтому первое найденное значение автоматически является максимальным. В этом и состоит маленькая стратегия перебора — правильный порядок позволяет не хранить все подходящие ответы.
Перенесём рассуждение в программу. В диапазоне range(6, 0, -1) начальное значение 6 входит, правая граница 0 не входит, а шаг −1 заставляет x уменьшаться.
def count_zeros(num, base):
if num == 0:
return 1
count = 0
while num:
if num % base == 0:
count += 1
num //= base
return count
for x in range(6, 0, -1):
value = 5 ** 12 - x
if count_zeros(value, 3) == 6:
print(x)
breakПрограмма выводит 4 — тот же результат, который мы получили вручную. Обратите внимание: функция ничего не знает о переменной x и выражении 5¹² − x. Ей передают уже вычисленное число value, и она занимается только его цифрами.
Проследим один вызов чуть внимательнее. При x = 4 переменная value получает 244 140 621. Функция делит это число на 3, проверяет остаток, затем работает уже с частным. Каждый нулевой остаток увеличивает count. Когда частное становится нулём, функция возвращает 6, сравнение == 6 становится истинным, и внешний цикл печатает текущее x.
Важно, что return расположен после цикла while. Если случайно сдвинуть его внутрь, функция завершится после первой же цифры и никогда не просмотрит число целиком. В Python отступы задают структуру программы, поэтому здесь они несут тот же смысл, что фигурные скобки в некоторых других языках.
Для третьего типа можно держать в голове следующую последовательность:
def count_zeros(num, base):
if num == 0:
return 1
count = 0
while num:
if num % base == 0:
count += 1
num //= base
return count
max_x = верхняя_граница_из_условия
for x in range(max_x, 0, -1):
value = выражение_из_условия
if count_zeros(value, основание_системы) == нужное_количество:
print(x)
breakЭто шаблон для наибольшего положительного x. Если нужен минимум, цикл меняется на range(1, max_x + 1): единица включается сразу, а к верхней границе прибавляем 1, потому что правая граница range не входит в диапазон.
Перебор иногда называют методом грубой силы, но в задачах ЕГЭ это не бессмысленное угадывание. Мы систематически проверяем конечное множество вариантов, заранее знаем его границы и для каждого кандидата применяем точное условие. Когда вариантов несколько тысяч, компьютер выполняет такую работу практически мгновенно.
Хотя в примерах требуется искать нули, функцию легко сделать универсальной. Добавим третий параметр target_digit и сравним остаток с ним. Тогда один и тот же код сможет считать любую цифру допустимого диапазона.
def count_digits(num, base, target_digit):
if num == 0:
return int(target_digit == 0)
count = 0
while num:
if num % base == target_digit:
count += 1
num //= base
return countДля нулей вызов будет выглядеть как count_digits(value, 11, 0), для двоек в троичной системе — count_digits(value, 3, 2). В текущей статье оставляем более короткое имя count_zeros, потому что все реальные примеры спрашивают именно нули, но теперь вы понимаете, что внутри нет специальной магии, связанной только с нулём.
Начнём разбор третьего типа с задания, в котором нужно найти наибольшее целое x:
Значение арифметического выражения 9 ⋅ 11210 + 8 ⋅ 11150 – x, где x – целое положительное число, не превышающее 3000, записали в 11-ричной системе счисления.
Определите наибольшее значение x, при котором в 11-ричной записи числа, являющегося значением данного арифметического выражения, содержится ровно 60 нулей.
В ответе запишите число в десятичной системе счисления.
Из условия получаем три настройки: верхняя граница равна 3000, основание равно 11, нужное количество нулей равно 60. Число 3000 обязательно проверяем: «не превышает 3000» включает его в диапазон.
def count_zeros(num, base):
if num == 0:
return 1
count = 0
while num:
if num % base == 0:
count += 1
num //= base
return count
for x in range(3000, 0, -1):
value = 9 * 11 ** 210 + 8 * 11 ** 150 - x
if count_zeros(value, 11) == 60:
print(x)
breakПервое подходящее значение — 2992. Оно и является ответом, потому что перебор шёл от 3000 вниз.
Теперь рассмотрим более короткое выражение и убедимся, что общая схема перебора не меняется:
Значение арифметического выражения 3100 — x, где x – целое положительное число, не превышающее 2030, записали в троичной системе счисления.
Определите наибольшее значение x, при котором в троичной записи числа, являющегося значением данного арифметического выражения, содержится ровно один нуль.
В ответе запишите число в десятичной системе счисления.
Меняются только три фрагмента: верхняя граница становится 2030, выражение — 3 ** 100 - x, основание — 3, а функция должна вернуть 1. Сам механизм остаётся прежним.
def count_zeros(num, base):
if num == 0:
return 1
count = 0
while num:
if num % base == 0:
count += 1
num //= base
return count
for x in range(2030, 0, -1):
value = 3 ** 100 - x
if count_zeros(value, 3) == 1:
print(x)
breakПрограмма выводит 1823. Не пытайтесь заранее вычислять 3¹⁰⁰ вручную: Python спокойно работает с этим целым числом, а наша задача — точно перенести условие.
В последнем примере изменятся граница, основание и нужное количество нулей, но сам алгоритм останется прежним:
Значение арифметического выражения 7350 + 7150 – x, где x – целое положительное число, не превышающее 2300, записали в семеричной системе счисления.
Определите наибольшее значение x, при котором в семеричной записи числа, являющегося значением данного арифметического выражения, содержится ровно 200 нулей.
В ответе запишите число в десятичной системе счисления.
Здесь легко механически оставить границу из предыдущего примера. Но в условии указано 2300, значит, цикл обязан начинаться именно с 2300. Основание и в остатке, и в целочисленном делении внутри функции равно 7.
def count_zeros(num, base):
if num == 0:
return 1
count = 0
while num:
if num % base == 0:
count += 1
num //= base
return count
for x in range(2300, 0, -1):
value = 7 ** 350 + 7 ** 150 - x
if count_zeros(value, 7) == 200:
print(x)
breakОтвет — 2001.
Третий тип задания 14 соединяет перебор целого x с анализом цифр результата. Мы вынесли подсчёт нулей в отдельную функцию, а во внешнем цикле оставили только то, что меняется от кандидата к кандидату: вычисление выражения и проверку количества цифр. Благодаря этому код читается почти как условие задачи.
Всегда обращайте внимание на роль x: здесь это целое число, поэтому не нужно составлять алфавит или использовать f-строки. Помните, что фраза «не превышает M» включает значение M, а правая граница range не включается. Следите за направлением перебора: для максимума идём вниз и берём первое совпадение, для минимума — вверх. Проверяйте основание в функции и не переносите границы или показатели степеней из предыдущего примера.
На этом мы закончили разбор всех трёх типов задания 14 ЕГЭ по информатике. А закрепить алгоритмы и научиться узнавать тип задачи по формулировке вы можете в нашем тренажёре.
