В новых тренировочных вариантах ЕГЭ по информатике появился необычный вариант задания 25.
Он не требует перебора делителей или анализа цифр числа, как обычно.
Вместо этого — задача на представление числа в виде суммы двух различных натуральных степеней двойки.
И решение — специальный алгоритм, который мы реализуем в коде.
Ниже — пошаговый разбор задачи.
Условие задачи
Напишите программу, которая перебирает целые числа, больше 2 000 000, в порядке возрастания и ищет среди них такие, которые можно представить в виде суммы двух различных натуральных степеней двойки.
В ответе в первом столбце таблицы запишите первые 5 найденных чисел в порядке возрастания, а во втором столбце — сумму показателей степеней двоек.
⚠️ Важно: «натуральные степени» означают, что показатели — натуральные числа, то есть начинаются с 1.
Следовательно, 2**0 не участвует, потому что 0 — не натуральное число.
💻 Код решения:
🔍 Пошаговое объяснение
🔹 Функция stepen(x)
Что делает: проверяет, является ли число x степенью двойки.
Если да — возвращает показатель степени.
Если нет — возвращает 0.
Как работает: Делит x на 2 до тех пор, пока x > 1.
После выхода из цикла проверяет: если x == 1, значит, исходное число было степенью двойки (2^p).
Иначе — не степень.
✅ Примеры:
stepen(8) → 8→4→2→1 → p=3 → return 3
stepen(12) → 12→6→3→1.5 → x != 1 → return 0
Это реализация для проверки степени двойки. Меняя двойку на другую цифру, можно также проверить условие для степеней другого числа.
Запись на занятия здесь: https://t.me/nka39
🔹 Функция F(x)
Что делает: для заданного x перебирает возможные степени двойки
a = 2^i, где i от 1 до 20.
Вычисляет b = x - a.
Проверяет: b > 0 — чтобы не было отрицательных или нулевых значений,
p = stepen(b) != 0 — чтобы b была степенью двойки,
i != p — чтобы степени были различными.
✅ Ловушка с b > 0:
Если x ≤ a, то b = x - a ≤ 0.
Отрицательное или нулевое b не может быть степенью двойки.
Поэтому условие if b > 0 — обязательное, иначе stepen(b) вернёт неверный результат.
🔸 Почему i до 20?
Потому что:
но меньшая степень (i) всегда имеет показатель ≤ 20 (на практике — ≤ 4 для первых 5 чисел).
Более того, первые 5 чисел будут иметь вид:
→ то есть i = 1, 2, 3, 4, 5 — все в диапазоне range(1,21).
Это ключевое понимание: вы перебираете меньшую степень, а большая — вычисляется как остаток.
🔹 Основной цикл
Что делает:
Перебирает x от 2 000 001 до огромного числа.
Для каждого вызывает F(x).
Если F(x) вернула не -5 — значит, нашлось представление.
Выводит x и сумму показателей.
Считает количество найденных.
Останавливается на 5-м числе.
✅ Это — прямой перебор с фильтрацией, и он работает, потому что первые подходящие числа находятся сразу после 2 млн.
🧮 Какие числа находятся?
Первые 5 чисел > 2 000 000, представимые как сумма двух различных натуральных степеней двойки:
✅ Итог
Алгоритм:
- Перебирает меньшую степень i от 1 до 20,
- Вычисляет остаток b = x - 2^i,
- Проверяет, является ли b степенью двойки,
- Убеждается, что степени различны,
- Находит первые 5 подходящих x.
Ловушка b > 0 — критически важна: без неё в stepen() попадут недопустимые значения.
Ограничение i < 21 — разумно, потому что меньшая степень в первых 5 числах не превышает 5, а 20 — с запасом.
Код работает и даёт правильный ответ.
Задача для самостоятельного решения.
Попробуйте самостоятельно решить аналогичную задачу. Свои результаты присылайте в комментарии.
Напишите программу, которая перебирает все целые шестизначные числа в порядке возрастания и ищет среди них те, которые не содержат в своей записи цифру 0 и которые можно представить в виде суммы нечётного натурального числа, делящегося без остатка на 113, и натуральной степени числа 3. В ответе в первом столбце таблицы запишите первые 5 найденных чисел в порядке возрастания, а во втором столбце - для каждого числа соответствующий показатель степени числа 3.
➕ Есть и другие прототипы задания 25
Этот вариант — лишь один из возможных.
В других могут быть:
- поиск чисел с заданным количеством делителей,
- проверка чисел масками,
- разложение чисел на простые множители.
О них — в следующих материалах.
Если Вам информация была для Вас полезна, то можно поддержать автора, нажав на кнопку "Поддержать".
Подпишитесь на канал и научитесь решать все задания ЕГЭ по информатике!
Удачи на экзамене!
Записаться ко мне на занятия можно тут https://t.me/nka39