Арифметические выражения и системы счисления
Задание 14 · Билет 1 · ЕГЭ по информатике
Условие
Значение арифметического выражения
записали в системе счисления с основанием 27.
Попробуйте программой
Необязательно, но удобно: напишите здесь свой код на Python, который найдёт ответ. Если не получится — откройте решение и вставьте готовую программу одной кнопкой.
Решите программой на Python
в браузереНапишите свой код, который найдёт ответ, и нажмите «Выполнить». Горячая клавиша запуска: Ctrl/⌘ + Enter.
Разбор задачи
Задание 14 ЕГЭ по информатике — это системы счисления и арифметические выражения. Значение выражения записывают в системе счисления с заданным основанием и спрашивают про свойства этой записи.
Вопрос бывает трёх видов: сколько цифр имеют числовое значение больше 9; при какой цифре x выражение делится нацело (и чему равно частное); при каком наибольшем x в записи ровно N нулей. Степени огромные, поэтому задачу решают короткой программой.
Что важно знать
- Задание базового уровня — оценивается в 1 балл
- В системе с основанием цифры — значения от 0 до ; при есть цифры со значением 10, 11, …
- Перевод в систему с основанием b — деление с остатком; остатки читают снизу вверх
- Степени в выражении огромные — считают программой (Python)
План решения
- Прочитайте вопрос: что именно нужно найти в записи по заданному основанию
- Вычислите значение выражения — большие числа удобны в Python
- Переведите число в нужную систему делением с остатком
- Подсчитайте цифры со значением больше 9 или нулевые разряды
- В задачах с x переберите подходящие значения (нужен максимум — перебор сверху вниз)
- Проверьте ответ программой и коротким ручным примером
Наглядно: кликай по битам и смотри, как десятичное число превращается в двоичное и обратно.
Решение
Теория с нуля: что нужно знать
Цифры в системе с основанием — это значения от 0 до . Если основание больше 10, старшие цифры имеют числовое значение 10, 11 и так далее (в 16-ричной системе их обозначают A–F). Именно поэтому в задании 14 встречается формулировка «цифры с числовым значением больше 9».
Пример: переведём 377 в 7-ричную систему. 377 = 7·53 + 6; 53 = 7·7 + 4; 7 = 7·1 + 0; 1 = 7·0 + 1. Остатки: 6, 4, 0, 1 — читаем снизу вверх, получаем 1046.
Обратно: расставляем веса — степени основания справа налево — и складываем.
А) сколько в записи цифр с числовым значением больше 9;
Б) при какой цифре x выражение делится нацело — и чему равно частное;
В) при каком наибольшем x в записи ровно N нулей.
Выражение выглядит пугающе — основание в степени больше двух тысяч. Но само число не такое уж большое: здесь около 6750 десятичных цифр, то есть примерно 3 КБ. Это совсем немного.
Переполнения нет. В Python целые числа — не 64-битные (как long long в C++ или Int64 в Pascal), а произвольной длины — bigint. Число хранится, пока хватает памяти, поэтому 2187**2020 считается точно и мгновенно, без переполнения.
Памяти нужно немного. Каждое слагаемое — меньше 3 КБ (само число в Python занимает около 3000 байт), а на всё выражение уходит несколько десятков килобайт. Это ничто на фоне гигабайтов оперативной памяти.
Когда прямой расчёт не сработает. Только в языках с фиксированными целыми: long long держит примерно 19 цифр и переполнится. Там нужна библиотека длинной арифметики или разбор по разрядам степени. На ЕГЭ обычно берут Python — и расчёт «в лоб» абсолютно законен.
Решение
открыто шагов: 4 из 4Программа, которая находит ответ:
n = 2 * 2187**2020 + 729**2021 - 2 * 243**2022 + 81**2023 - 2 * 27**2024 - 6561 # значение выражения
ans = 0 # счётчик цифр со значением больше 9
while n > 0: # переводим в 27-ричную делением с остатком
if n % 27 > 9: # очередная цифра больше 9?
ans += 1 # да — считаем
n //= 27 # переходим к следующему разряду
print(ans) # выводим ответ Проверка
Типовые ошибки и проверка
- Неверно понимают «цифра со значением больше 9» — это цифра-разряд от 10 до основания−1, а не «9».
- В задачах с x не проверяют все значения (иногда x может быть двузначным числом до основания−1).
- Путают «частное от деления» с самим значением.
- Считают «ровно N нулей» с учётом ведущих нулей (их нет).
- Проверка: пересчитайте программой и сравните с переводом «вручную» для малого примера.
Режимы
Сейчас открыт режим обучения: теория, разбор и ответ видны. Скоро появится режим проверки — только условие и поле ответа, без подсказок.
Практикум Все задания Режим проверки — скоро