В предыдущей статье мы научились разбирать результат выражения на цифры. Теперь сделаем следующий шаг: одна цифра в условии спрячется под буквой x, и нам придётся восстановить её. Здесь особенно важно не перепутать два понятия. Во втором типе x — не произвольное целое число, а ровно одна цифра некоторой системы счисления.
Если основание равно 10, x может принимать значения от 0 до 9. Если основание равно 25, допустимы значения от 0 до 24. Одна и та же буква x во всех местах обозначает одну и ту же цифру: нельзя подставить в первое число 7, а во второе — 12.
Алфавитом системы счисления называют набор символов, которыми записывают её цифры. В системе с основанием p требуется ровно p цифр со значениями от 0 до p − 1. Для оснований до 10 всё привычно: например, алфавит восьмеричной системы — 0, 1, 2, 3, 4, 5, 6, 7.
После девятки числовые значения никуда не исчезают, просто для них нужны новые символы. В программировании обычно используют латинские буквы: a обозначает 10, b — 11, c — 12 и так далее. Это всего лишь условность записи. Цифра r в 29-ричной системе имеет числовое значение 27, потому что после a идёт десятое значение, после b — одиннадцатое и так далее.
Удобный и безопасный алфавит можно собрать из двух констант модуля string:
from string import digits, ascii_lowercase
alphabet = digits + ascii_lowercase
print(alphabet)
>>>0123456789abcdefghijklmnopqrstuvwxyzИли же вовсе использовать всего одну константу, правда нужно не забыть про срез:
from string import printable
alphabet = printable[:36]
print(alphabet)
>>>0123456789abcdefghijklmnopqrstuvwxyzВ начале printable расположены десять цифр, а затем 26 строчных латинских букв. Поэтому срез printable[:36] даёт полный алфавит 0123456789abcdefghijklmnopqrstuvwxyz для систем счисления с основаниями до 36. Следующие символы printable — заглавные буквы, знаки пунктуации и пробельные символы — нам не нужны, поэтому мы сразу их отсекаем. Затем срез alphabet[:base] оставляет ровно столько цифр, сколько есть в нужной системе счисления. Например, alphabet[:16] даст 0123456789abcdef.
Да, можно сразу сохранять в alphabet не все 36 значений, а только нужные, то есть не делать еще один срез alphabet[:base]. Обычно так и поступают, то есть тут было бы alphabet = printable[:16]. Но мы для наглядности оставим в примерах оба среза.
Функция int умеет переводить строковую запись числа в обычное целое значение. В вызове int('1a3', 16) первый аргумент — сама запись, второй — её основание. Результатом будет десятичное значение 419. После перевода с числом можно выполнять обычные арифметические действия.
Почему 1a3₁₆ превращается именно в 419? Раскроем позиционную запись: 1 × 16² + 10 × 16 + 3 = 256 + 160 + 3 = 419. Функция int выполняет такое раскрытие сама. Она не «угадывает» основание по буквам: второй аргумент 16 сообщает, какие веса имеют разряды.
Здесь есть естественное ограничение Python: стандартная буквенная запись поддерживается для оснований от 2 до 36. Цифры 0–9 дают первые десять значений, буквы a–z — ещё двадцать шесть. Для типовых заданий ЕГЭ этого достаточно. Если когда-нибудь встретится основание выше 36, потребуется другой способ представления цифр, но в нашем шаблоне это не нужно.
Общий замысел состоит из четырёх действий:
int и вычислить выражение.break.Пусть выражение 1x21 + 4x2 записано в десятичной системе. Нужно найти наибольшую цифру x, при которой сумма кратна 3. Поскольку ищем максимум, начинаем с 9 и движемся вниз.
Мы нашли первое подходящее значение при движении сверху вниз, поэтому x = 7 — наибольшее. Этот ручной разбор полезен: он показывает, что программа не делает ничего таинственного, а просто быстро повторяет те же подстановки.
Можно увидеть эту же задачу через позиционную формулу. Число 1×21₁₀ равно 1 × 10³ + x × 10² + 2 × 10 + 1, а 4×2₁₀ равно 4 × 10² + x × 10 + 2. Для x = 7 получаем 1721 и 472. На экзамене раскрывать каждое число по степеням необязательно, но такой взгляд объясняет, почему x нельзя воспринимать как отдельное слагаемое: его вклад зависит от разряда, в котором он стоит.
Если одна и та же x встречается дважды в одном числе, её вклад появляется в двух разрядах. Например, 2xx₁₀ = 2 × 10² + x × 10 + x. Именно поэтому в f-строке каждое место нужно обозначить отдельно — f'2{x}{x}'. Одна пропущенная вставка изменит уже не мелочь, а само число.
Запишем учебный пример на Python. f-строка f'1{x}21' вставляет текущий символ x в нужное место, а int переводит получившуюся запись из указанной системы счисления.
from string import printable
alphabet = printable[:36]
for x in alphabet[:10][::-1]:
number_1 = int(f'1{x}21', 10)
number_2 = int(f'4{x}2', 10)
value = number_1 + number_2
if value % 3 == 0:
print(x)
breakСрез [::-1] переворачивает алфавит, поэтому перебор идёт от 9 к 0. Как только остаток от деления суммы на 3 становится нулём, программа печатает 7 и завершает цикл. Если бы требовалось наименьшее x, переворачивать алфавит не пришлось бы.
В реальном задании обычно требуется вывести не сам x, а частное от деления выражения на заданное число. Тогда шаблон для поиска наибольшей цифры выглядит так:
from string import printable
alphabet = printable[:36]
base = основание_системы
divisor = делитель_из_условия
for x in alphabet[:base][::-1]:
number_1 = int(f'1{x}1', base)
number_2 = int(f'2{x}2', base)
value = number_1 + number_2
if value % divisor == 0:
print(value // divisor)
breakЧисла 1x1 и 2x2 в шаблоне условные: их обязательно заменяем записями из задачи. Если слагаемых три, добавляем number_3. Если между ними стоит вычитание, точно переносим знак. Для поиска минимального x убираем [::-1]. Сам x остаётся строковым символом, потому что он вставляется внутрь строк; функция int уже превращает всю запись в число.
После написания шаблона полезно провести короткую проверку. Посмотрите, совпадает ли base в срезе алфавита и во всех вызовах int. Посчитайте количество символов до и после {x} в каждой f-строке. Наконец, перечитайте последнюю строку условия: если спрашивают частное, выводим value // divisor; если спрашивают числовое значение x, строковый символ нужно при необходимости преобразовать в его индекс в алфавите.
Почему можно ставить break? Потому что порядок перебора уже выбран в соответствии с вопросом. При поиске максимума первым сверху встретится самое большое подходящее значение; при поиске минимума первым снизу — самое маленькое. Если убрать break, программа может напечатать несколько вариантов, а последний из них окажется совсем не тем экстремумом, который нужен.
Начнём разбор второго типа с задания, где нужно найти наибольшую допустимую цифру x:
Операнды арифметического выражения записаны в системе счисления с основанием 25:
11353x1225 + 135x2125
В записи чисел переменной x обозначена неизвестная цифра из алфавита 25-ричной системы счисления.
Определите наибольшее значение x, при котором значение данного арифметического выражения кратно 24.
Для найденного x вычислите частное от деления значения арифметического выражения на 24 и укажите его в ответе в десятичной системе счисления. Основание системы счисления указывать не нужно.
Берём первые 25 символов алфавита и переворачиваем их, потому что нужен максимум. В обеих f-строках подставляется один и тот же x. Затем проверяем остаток от деления суммы на 24.
from string import printable
alphabet = printable[:36]
for x in alphabet[:25][::-1]:
number_1 = int(f'11353{x}12', 25)
number_2 = int(f'135{x}21', 25)
value = number_1 + number_2
if value % 24 == 0:
print(value // 24)
breakПервой подходит цифра m, её числовое значение равно 22. Но в ответ требуется не x, а частное, поэтому программа выводит 266249847.
В следующем задании также подберём цифру x, но изменятся основание и условие делимости:
Операнды арифметического выражения записаны в системе счисления с основанием 29.
923×87429 + 524×615229
В записи чисел переменной х обозначена неизвестная цифра из алфавита 29-ричной системы счисления.
Определите наибольшее значение х, при котором значение данного арифметического выражения кратно 28.
Для найденного х вычислите частное от деления значения арифметического выражения на 28 и укажите его в ответе в десятичной системе счисления. Основание системы счисления указывать не нужно.
Структура решения не меняется.
from string import printable
alphabet = printable[:36]
for x in alphabet[:29][::-1]:
number_1 = int(f'923{x}874', 29)
number_2 = int(f'524{x}6152', 29)
value = number_1 + number_2
if value % 28 == 0:
print(value // 28)
breakПодходит цифра r со значением 27. Частное равно 3319197720 — его и записываем в ответ.
Закрепим алгоритм на ещё одном задании и отдельно проследим, что именно нужно вывести в ответ:
Операнды арифметического выражения записаны в системе счисления с основанием 21:
82934х221 + 2924хх721 + 67564х821
В записи чисел переменной x обозначена неизвестная цифра из алфавита 21-ричной системы счисления.
Определите наименьшее значение x, при котором значение данного арифметического выражения кратно 20.
Для найденного значения x вычислите частное от деления значения арифметического выражения на 20 и укажите его в ответе в десятичной системе счисления. Основание системы счисления указывать не нужно.
Здесь сразу два изменения. Во-первых, слагаемых три. Во-вторых, требуется наименьшее x, поэтому алфавит оставляем в прямом порядке. В числе 2924xx7 неизвестная цифра встречается дважды; в f-строке пишем {x}{x}, чтобы обе позиции получили одно значение.
from string import printable
alphabet = printable[:36]
for x in alphabet[:21]:
number_1 = int(f'82934{x}2', 21)
number_2 = int(f'2924{x}{x}7', 21)
number_3 = int(f'67564{x}8', 21)
value = number_1 + number_2 + number_3
if value % 20 == 0:
print(value // 20)
breakПервой подходит цифра 3, а искомое частное равно 72450445.
Для каждого кандидата x программа фактически строит новую версию выражения. Пусть основание равно 25 и x сначала равна o, затем n, затем m. На каждой итерации обе записи заново собираются с одним и тем же символом, переводятся в числа и складываются. После этого проверяется только остаток от деления результата на 24. Предыдущая итерация никак не влияет на следующую.
Такая независимость вариантов делает перебор надёжным. Нам не нужно выводить сложную формулу зависимости всей суммы от x, хотя сделать это математически возможно. В задаче всего не более 36 кандидатов, поэтому прямой перебор проще, короче и меньше подвержен алгебраическим ошибкам.
Однако программа остаётся полезной только при аккуратном вводе. Она безупречно проверит неправильное выражение и уверенно выдаст неправильный ответ. Поэтому смысловая проверка — основание, порядок перебора, число разрядов, знаки и требуемый вывод — является частью алгоритма, а не необязательным украшением.
Во втором типе задания 14 мы восстанавливаем неизвестную цифру. Сначала строим алфавит системы, затем перебираем его символы, подставляем один и тот же x во все позиции и переводим каждую запись функцией int. Направление перебора сразу отвечает за максимум или минимум, поэтому после первого подходящего значения цикл можно остановить.
Всегда обращайте внимание на то, что x обозначает именно цифру, а не произвольное число: её значение должно быть меньше основания системы. Помните, что буквы a, b, c и далее — это цифры со значениями 10, 11, 12 и далее. Следите за направлением перебора, за повторением {x} во всех нужных местах и за тем, что требуется вывести: сам x или частное. После переписывания длинного операнда полезно сверить его с условием посимвольно.
В следующей статье разберём третий тип. Там x перестанет быть цифрой внутри записи и станет целым положительным числом из диапазона. Мы объединим перебор x с уже знакомым подсчётом цифр в результате выражения.
