Задание 5 ЕГЭ по информатике

Теория к заданию 5 ЕГЭ по информатике: алгоритм обработки чисел

Задан алгоритм преобразования числа через его двоичную запись. Нужно найти минимальное или максимальное подходящее исходное число.

Что нужно знать

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

Как разбирать алгоритм с двоичной записью

• Сначала переведите алгоритм на человеческий язык: что дописывается, что отбрасывается, при каком условии.
• Полезно записать преобразование как формулу: дописать 0 справа значит умножить на 2, дописать 1 значит умножить на 2 и прибавить 1.
• Дописать два разряда значит умножить на 4 и прибавить значение этих разрядов.
• Если алгоритм зависит от чётности числа, разбирайте два случая отдельно: чётное и нечётное.
• При поиске минимального R, большего N, идите от N вверх и проверяйте каждое число: перебор обычно короткий.
• Писать программу не обязательно, но она надёжнее ручного перебора, если диапазон большой.
• Проверяйте найденный ответ, прогнав алгоритм вручную от начала до конца.

Как решать задание 5

1. Разберите пример из условия и убедитесь, что правильно поняли правило.
2. Оцените, при каком примерно N результат достигнет нужного значения.
3. Перебирайте N по возрастанию, для каждого выполняя алгоритм.
4. Останавливайтесь на первом N, удовлетворяющем условию.
5. Запишите найденное число.

Разбор примера

Частые ошибки

• Приписывают цифры слева, а не справа.
• Переводят остаток от деления в двоичную запись без умножения на 3.