Алгоритм решения задания 14. Часть 1

О задании

В задании 14 ЕГЭ по информатике мы работаем с позиционными системами счисления. На первый взгляд тема выглядит необычно: огромные степени, непривычные основания, числа, которые невозможно целиком выписать на бумаге. Но внутри почти всех задач скрывается одна и та же спокойная идея: число состоит из разрядов, а каждый разряд можно по очереди получить с помощью деления с остатком.

Слово «позиционная» здесь главное. Значение цифры определяется не только самой цифрой, но и её местом. В десятичном числе 505 две пятёрки обозначают разные величины: левая — пять сотен, правая — пять единиц. Ноль между ними ничего не добавляет сам по себе, зато удерживает разряды на своих местах. Без него запись 505 превратилась бы в 55 и стала бы обозначать совсем другое число.

То, что сейчас кажется естественным, человечество осваивало долго. Например, вавилоняне пользовались позиционной системой с основанием 60, но долгое время обходились без полноценного обозначения пустого разряда: смысл приходилось восстанавливать по контексту. История нуля особенно хорошо показывает, насколько важна позиция цифры. Ноль понадобился сначала как «сторож места», а уже позднее стал восприниматься как самостоятельное число.

Для компьютера выбор основания тоже не является декоративной деталью. Внутри вычислительной техники особенно удобна двоичная система, а восьмеричная и шестнадцатеричная помогают компактно записывать длинные двоичные последовательности. В задании 14 основания могут быть и другими — например, 3, 25 или 27. Принцип от этого не меняется.

В этой линии можно выделить три распространённых типа заданий:

• В первом типе неизвестных нет. Нужно вычислить выражение и посчитать в записи результата определённые цифры.
• Во втором типе одна и та же неизвестная цифра x встречается внутри одного или нескольких чисел. Мы перебираем цифры алфавита системы счисления и ищем подходящую.
• В третьем типе x — уже не цифра внутри записи, а целое число из заданного диапазона. Для каждого x вычисляем выражение и проверяем условие.

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

Алгоритм решения

Число и его запись — не одно и то же

Прежде чем идти дальше, договоримся о языке. Само число — это количество, математический объект. А запись числа — способ показать его с помощью выбранного алфавита. Один и тот же объект можно записать по-разному: десятичное 10, двоичное 1010₂ и шестнадцатеричное a₁₆ обозначают одно и то же число. Меняется оболочка, но не величина.

Эта мысль избавляет от частой путаницы. Когда Python вычисляет выражение 3 ** 333 + 3 ** 22 - 9 ** 111 - 8, результат хранится как целое число. У него нет приклеенной надписи «я троичное» или «я десятичное». Система счисления появляется только в тот момент, когда мы решаем, как читать разряды этого числа. Именно поэтому в цикле нужно явно указать основание: остатки от деления на 3 покажут троичные цифры, а остатки от деления на 10 — десятичные.

Представьте одну и ту же мелодию, записанную обычными нотами и буквенными обозначениями аккордов. Мелодия не изменилась, изменился язык записи. Так же и с числом: основание определяет язык, на котором мы раскладываем значение по разрядам.

Из позиционного принципа следует формула записи. Если цифры числа в системе с основанием p равны aₙ, aₙ₋₁, …, a₁, a₀, то значение равно aₙ × pⁿ + aₙ₋₁ × pⁿ⁻¹ + … + a₁ × p + a₀. Последнее слагаемое a₀ не умножается на полную степень основания, поэтому при делении всего числа на p именно оно остаётся в остатке. Так математическая формула напрямую приводит нас к программному алгоритму.

Почему остаток от деления даёт последнюю цифру

Прежде чем писать программу, разберём саму математику. Любое неотрицательное целое число N при делении на основание p можно представить так:

N = q × p + r, где q — целая часть от деления, а r — остаток, причём 0 ≤ r < p.

Остаток r всегда находится в диапазоне от 0 до p − 1. А это как раз все возможные цифры системы счисления с основанием p. Поэтому r совпадает с последней цифрой записи числа. Частное q — всё число без этой последней цифры. Повторяя операцию, мы снимаем цифры справа налево, словно по одной бусине с нити.

Учебный пример: разбираем число 7233

Возьмём число 7233 в десятичной системе. Основание равно 10, поэтому делим на 10 и записываем остатки:

• 7233 = 723 × 10 + 3. Последняя цифра — 3, дальше работаем с числом 723.
• 723 = 72 × 10 + 3. Получили ещё одну цифру 3.
• 72 = 7 × 10 + 2. Следующая цифра — 2.
• 7 = 0 × 10 + 7. Последняя найденная цифра — 7, после деления осталось 0, поэтому останавливаемся.

Остатки появились в обратном порядке: 3, 3, 2, 7. Если прочитать их с конца, снова получим 7233. Для подсчёта цифр переворачивать последовательность не нужно: нам важно лишь проверить каждый остаток.

Теперь сменим основание. Десятичное число 220 записывается в восьмеричной системе как 334. Проверим последнюю цифру: 220 = 27 × 8 + 4. Остаток 4 действительно совпал с последней цифрой восьмеричной записи. Затем 27 = 3 × 8 + 3 и 3 = 0 × 8 + 3. Получили остатки 4, 3, 3 — то есть запись 334 справа налево.

Первый тип задания удобно разделить на два больших шага. Сначала переносим арифметическое выражение в Python. Затем разбираем полученное число на цифры и считаем те, которые подходят условию.

Шаг 1. Записываем выражение

Сложение и вычитание записываются привычными знаками + и −. Для умножения в Python используется одна звёздочка *, а для возведения в степень — две звёздочки **. Возьмём выражение 2 × 5² + 3 × 7⁴ − 20 и запишем его на языке Python:

num = 2 * 5 ** 2 + 3 * 7 ** 4 - 20
print(num)

Программа выведет 7233. Обратите внимание на порядок действий: степень выполняется раньше умножения, а умножение — раньше сложения и вычитания. Скобки ставим тогда, когда они есть в исходном выражении или когда длинную запись нужно безопасно перенести на несколько строк.

Шаг 2. Считаем нужные цифры

Пусть требуется определить количество троек в числе 7233. Создадим счётчик count. Пока число не стало нулём, будем получать последнюю цифру оператором %, сравнивать её с 3 и отбрасывать оператором //.

num = 2 * 5 ** 2 + 3 * 7 ** 4 - 20

count = 0
while num:
    digit = num % 10
    if digit == 3:
        count += 1
    num //= 10

print(count)

Ответ равен 2.

Условие while num читается как «пока число не равно нулю». В Python ноль считается ложным значением, поэтому более длинная запись while num != 0 дала бы тот же результат. Строка num //= 10 означает то же самое, что num = num // 10: мы делим число нацело и сохраняем частное обратно в num.

Если система счисления другая, меняется делитель. Для восьмеричной записи берём остаток от деления на 8 и делим нацело на 8; для 25-ричной — используем 25. В общем виде шаблон выглядит так:

num = выражение_из_условия
base = основание_системы
target_digit = нужная_цифра

count = 0
while num:
    digit = num % base
    if digit == target_digit:
        count += 1
    num //= base

print(count)

Этот шаблон рассчитан на положительное значение выражения — именно такие числа встречаются в рассматриваемых примерах. Отдельный крайний случай — само число 0: его запись состоит из одного нуля, хотя цикл while num не выполнится ни разу. Если в условии теоретически может получиться ноль, этот случай нужно проверить отдельно.

Иногда требуется считать не одну конкретную цифру, а целую группу. Тогда меняется только условие внутри цикла. Например, запись digit > 9 подсчитывает все цифры с числовым значением больше 9, а digit in (0, 2, 4) — только цифры 0, 2 и 4.

Как узнать первый тип по формулировке

Перед написанием кода прочитайте условие как короткий рассказ. Сначала дано полностью определённое арифметическое выражение, без каких либо неизвестных. Затем говорится, в какой системе счисления записали значение. Наконец, задаётся вопрос о цифрах этой записи: сколько нулей, двоек или значений больше некоторой границы она содержит. Эта последовательность и выдаёт первый тип.

Подчеркните три элемента: само выражение, основание системы и условие на цифру. Можно даже выписать рядом небольшую тройку: «num — base — проверка». После этого почти весь код восстанавливается автоматически.

Не ориентируйтесь только на огромные степени. Большие числа встречаются и в других линиях, а здесь важна именно фраза о записи результата в некоторой системе счисления. И наоборот, отсутствие явной команды «переведите число» не должно смущать: подсчёт цифр уже означает, что запись нужно исследовать, пусть мы и делаем это остатками без построения строки.

Как проверить себя до запуска программы

Полезная привычка — сделать маленькую мысленную проверку на знакомом числе. Если основание равно 8, возьмите число 220 и убедитесь, что первый остаток равен 4. Если в коде внезапно получается другая цифра, значит, вы перепутали оператор, основание или переменную. Такая мини-проверка занимает несколько секунд, зато помогает понять ошибку, а не просто увидеть неверный ответ.

Проверьте и границы возможных цифр. В системе с основанием p ни одна цифра не может быть равна p или превосходить его. Поэтому num % p всегда должно давать значение от 0 до p − 1. Если условие просит считать цифры больше 9 в 27-ричной системе, это осмысленно: там существуют значения от 10 до 26. А в восьмеричной системе такое условие никогда бы не выполнилось.

Наконец, оцените знак выражения. Наш цикл рассчитан на неотрицательные числа. В заданиях этого типа выражения подобраны так, чтобы результат был положительным, однако при ошибке в знаке можно случайно получить отрицательное значение и столкнуться с неожиданным поведением целочисленного деления. Если программа не завершается или выдаёт странный результат, первым делом ещё раз сверьте все плюсы и минусы.

Пример 1

Начнём разбор первого типа с такого задания:

№ 14102. Типовая задача Значение арифметического выражения 3³³³ + 3²² — 9¹¹¹ — 9 записали в системе счисления с основанием 3. Определите количество цифр 2 в записи этого числа.

Значение арифметического выражения 3³³³ + 3²² — 9¹¹¹ — 9 записали в системе счисления с основанием 3.

Определите количество цифр 2 в записи этого числа.

Открыть задание

Здесь основание равно 3, поэтому каждый остаток может быть только 0, 1 или 2. Ищем остатки, равные 2. Самая опасная часть — переписать степени без потери показателей: 9¹¹¹ превращается в 9 ** 111, а не в 9 * 111.

num = 3 ** 333 + 3 ** 22 - 9 ** 111 - 8

count = 0
while num:
    if num % 3 == 2:
        count += 1
    num //= 3

print(count)

Программа выводит 131. Это и есть количество двоек в троичной записи результата.

Пример 2

Теперь рассмотрим задание с более высоким основанием и подсчётом значащих нулей:

№ 14002. Демоверсия Значение арифметического выражения 3 ⋅ 3125⁸ + 2 ⋅ 625⁷ — 4 ⋅ 625⁶ + 3 ⋅ 125⁵ — 2 ⋅ 25⁴ — 2025 записали в системе счисления…

Значение арифметического выражения 3 ⋅ 3125⁸ + 2 ⋅ 625⁷ — 4 ⋅ 625⁶ + 3 ⋅ 125⁵ — 2 ⋅ 25⁴ — 2025 записали в системе счисления с основанием 25.

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

Открыть задание

Фраза «значащие нули» может насторожить, но здесь она лишь напоминает: считать нужно нули, которые входят в обычную запись числа. Нули слева можно дописать сколько угодно — 7, 07 и 0007 обозначают одно и то же число, поэтому такие ведущие нули в каноническую запись не входят. Нули внутри записи или в её конце уже занимают разряды и влияют на значение числа; именно их алгоритм и подсчитает.

Выражение длинное, поэтому переносим его на несколько строк и заключаем в круглые скобки. Так заметно проще сверить каждый знак с условием.

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

count = 0
while num:
    if num % 25 == 0:
        count += 1
    num //= 25

print(count)

Ответ программы — 10. Обратите внимание: мы не переводили огромное число в строку и не пытались придумывать символы для цифр 10–24. Для подсчёта нулей достаточно числовых остатков.

Пример 3

В третьем примере изменится условие на цифры: будем считать все значения, которые больше 9:

№ 14021. Демоверсия Значение арифметического выражения 2 · 2187²⁰²⁰ + 729²⁰²¹ – 2 · 243²⁰²² + 81²⁰²³ – 2 · 27²⁰²⁴ – 6561 записали в системе счисления с основанием 27. Определите…

Значение арифметического выражения 2 · 2187²⁰²⁰ + 729²⁰²¹ – 2 · 243²⁰²² + 81²⁰²³ – 2 · 27²⁰²⁴ – 6561 записали в системе счисления с основанием 27.

Определите в 27-ричной записи числа количество цифр с числовым значением, превышающим 9.

Открыть задание

Теперь условию подходят сразу значения 10, 11, …, 26. В программе не нужно перечислять их по одному: очередная цифра равна num % 27, поэтому достаточно сравнить этот остаток с 9 (num % 27 > 9).

num = (2 * 2187 ** 2020
       + 729 ** 2021
       - 2 * 243 ** 2022
       + 81 ** 2023
       - 2 * 27 ** 2024
       - 6561)

count = 0
while num:
    if num % 27 > 9:
        count += 1
    num //= 27

print(count)

Получаем 3367. Хотя само число содержит тысячи цифр, программа рассматривает их по одной и не хранит отдельную строковую запись в 27-ричной системе.

Почему не обязательно переводить число в строку

Можно встретить и другой подход: написать собственную функцию перевода, собрать строку из цифр, а затем воспользоваться методом count. Такой способ тоже имеет право на жизнь, но для первого типа задания он часто делает решение длиннее. Нам не нужна вся запись одновременно — достаточно узнать каждую цифру и сразу проверить её.

Числовой алгоритм особенно удобен для оснований больше 10. Остаток 17 остаётся обычным числом 17, и нам не приходится решать, каким символом его показать. Если же строить строку, пришлось бы заранее договориться, что значения 10–35 обозначаются буквами. Получается, работа с остатками ближе к самой математике задачи и меньше зависит от оформления записи.

При этом важно понимать, а не заучивать цикл. Строка num % base отвечает на вопрос «какова последняя цифра?», а num //= base — «что останется, если эту цифру убрать?». Если можете проговорить две строки словами, шаблон легко восстановится даже тогда, когда вы забыли точную запись.

Итоги

Мы разобрали первый тип задания 14 и увидели, что его основа — обычное деление с остатком. Остаток от деления на основание системы даёт последнюю цифру, а целая часть от деления оставляет число без этой цифры. Повторяя два действия в цикле, можно исследовать запись числа в любой системе счисления, не переводя её вручную.

Всегда обращайте внимание на основание системы и на условие проверки. В обеих строках — с оператором % и с оператором // — должно стоять одно и то же основание. Следите за степенями, знаками и скобками в длинном выражении; полезно переносить его на несколько строк и сверять по одному слагаемому. Если ищется группа цифр, изменяйте только условие внутри цикла, а не весь алгоритм.

В следующей статье перейдём ко второму типу задания 14. Там внутри чисел появится неизвестная цифра x: составим алфавит системы счисления, научимся перебирать его в нужном направлении и разберёмся, как функция int переводит запись числа в десятичное значение.