Ах, ЕГЭ по информатике — тот самый экзамен, который заставляет даже калькуляторы задумываться: «А зачем я вообще существую?» В прошлом году я сам с этим сражался, сейчас уже в МИРЭА прокачиваю свои навыки программирования и решил поделиться своими наработками в рубрике #хакнем_информатика.
Сегодня мы возьмёмся за задание номер 23 — оно считается одним из самых простых, но кто сказал, что простое не может быть весёлым? Представьте себе исполнителя — не робота-пылесоса, а такого виртуального героя с двумя-тремя командами: прибавить 1, прибавить 2 или умножить на 3. Задача звучит просто — посчитать, сколько программ приведут исполнителя из числа A в число Б.
Например, из 2 в 12. Казалось бы, можно и ручками посчитать, если вы любите считать быстрее улитки бегом марафон. Но мы же люди умные!
Вместо того чтобы мучиться с бумажкой и карандашом (или как у меня было — с пятой попыткой найти ластик), просто напишем маленькую программку на Python.
Вот первый пример для разминки. Исполнитель Калькулятор умеет две команды: прибавить 1 и умножить на 2. Вопрос: сколько существует программ, которые при старте от числа 2 приводят к числу 29 так, чтобы по пути встретилось число 14 и ни в коем случае не было числа 25? Ответ вас удивит — их аж тринадцать!
Кто-то скажет: «Почему именно тринадцать? Это ж несчастливое число!» А я отвечу: «В информатике счастье не зависит от суеверий». Вот так математика и магия программирования идут рука об руку.
Если вам кажется этот пример слишком лёгким — держитесь крепче!
Второй пример чуть сложнее: теперь команды изменились на прибавить 1 и прибавить 2. Стартуем с единицы и добираемся до числа 13 так, чтобы обязательно пройти через семёрку.
Сколько таких программ? Целых сто шестьдесят девять!
На этом месте вспоминается анекдот про программиста: «Сколько программистов нужно, чтобы поменять лампочку? Ни одного — это аппаратная проблема». Так вот здесь без программирования никак!
Третий пример добавляет остроты нашему приключению: теперь у исполнителя целых три команды — прибавить единичку, умножить на три и умножить на четыре.
Предположим стартуем с двойки и хотим получить шестьдесят при условии наличия в траектории числа шестнадцать и отсутствии двадцати одного. Ответ — сорок вариантов! Тут даже вспоминается история моего друга-программиста: он пытался объяснить бабушке свой код, а она сказала: «Лучше бы ты мне пирог написал».
Но пироги не считаются алгоритмами!
Ну а теперь самое вкусное — четвёртый пример с командой «возвести в квадрат». Да-да, у нашего Калькулятора появился суперприём! Начинаем со второго числа и стремимся к тридцати восьми. Сколько способов достичь цели?
Целых двести шестьдесят шесть! Это почти как призрак дьявола среди чисел… но без страха! Ведь для нашей программы возведение в квадрат — это всего лишь ещё одна строчка кода.
В общем, решая эти задачки руками вы рискуете превратиться в современного Сизифа — катать камень по горам бумаг и формул без конца.
А мы ведь живём в эпоху Python’а! Пару строчек кода — и ответ у вас на ладони. Помните старую поговорку программиста: «Зачем делать вручную то, что можно автоматизировать?» Именно так я разбираюсь со всеми заданиями №23 ЕГЭ по информатике.
Всем удачи на экзаменах!
Пусть ваши программы будут быстрыми как гепард (ну или хотя бы быстрее вашей бабушкиного компьютера). Надеюсь мои рассказы помогут вам победить этот страшный тест раз и навсегда.