О задании
Задание 5 ЕГЭ по информатике нацелено на проверку умений учащихся выполнять и анализировать простые алгоритмы.
В данном задании дан некий алгоритм – последовательность действий, которая:
- Берет обычное натуральное число (1, 2, 3, 4 и так далее)
- Переводит его в заданную систему счисления (например, в двоичную, где есть только 0 и 1)
- Обрабатывает полученную запись по определённым правилам (добавляет цифры, считает сумму, проверяет условия)
- Выдает результат
В ответ, обычно, требуется дать число, являющееся результатом работы данного алгоритма при определённых условиях, при этом выполнив перевод этого числа обратно в десятичную систему счисления.
Правда, в иных формулировках в ответ требуется дать исходное число, после обработки которого получается заданное число.
На этом принципе мы и разделим 5 задания на два типа:
- В заданиях первого типа на вход алгоритма подаётся число N, а в ответ нужно дать минимальное или максимальное число N, после обработки которого с помощью алгоритма получается число R, удовлетворяющее заданному условию
- В заданиях второго типа, напротив, нужно вывести результат работы алгоритма – число R – при некотором условии для исходного числа N, поступающего на вход алгоритма
Каждый из этих типов мы разберём в отдельной статье. Сегодня же мы вспомним, как работать с системами счисления в Python, научимся обрабатывать числа по заданному алгоритму и разберём основные алгоритмы решения первого типа 5 заданий.
Алгоритм решения
Первым делом внимательно читаем условие и выясняем, с какой системой счисления предстоит работать.
Python предоставляет нам встроенные функции для работы с популярными системами счисления:
- bin() – для двоичной
- oct() – для восьмеричной
- hex() – для шестнадцатеричной
Но что делать, если нужна, например, пятеричная система? Тут придется написать свою функцию перевода. Не волнуйтесь, это не так сложно, как кажется! В предыдущей статье мы подробно разбирали, как создать универсальную функцию для перевода в любую систему счисления.
Теперь начинается самое интересное – поиск нужного числа. Мы будем действовать методично, перебирая каждое число в цикле:
Важный момент: верхнюю границу диапазона придется подбирать самостоятельно! Начните с небольших значений (например, 20), и, если ответ не находится – увеличивайте.
При этом не забывайте, что диапазон можно «переворачивать», если требуется найти максимальное значение N.
Внутри цикла для каждого числа N выполняем следующие действия:
- Переводим число в нужную систему счисления встроенными функциями или вызываем собственную.
- Проверяем условия из задания. В задании обычно даются условия по типу: «Если число четное, то…», «Если сумма цифр делится на 3, то…». Это развилки на нашем пути – в зависимости от условия мы идем по разным маршрутам обработки.
- Выполняем требуемые преобразования. Может потребоваться вычислить сумму цифр этого числа, дописать к нему слева или справа какие-либо цифры или выполнить еще какие математические действия.
Итог выполнения этих действий как раз и будет записью искомого числа R в заданной системе счисления. Останется лишь перевести эту запись обратно в десятичную систему и выполнить последнее условие. Для перевода будем пользоваться стандартной функцией int():
После чего требуется сравнить это число R с каким-либо другим и при выполнении этого условия вывести число N.
На этом все, словесное описание базового алгоритма решения 5 задания закончено. Давайте опробуем его на практике и решим пару заданий.
Пример 1
Начнём сегодня с такой формулировки:
«На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
- a) если число N делится на 3, то к этой записи дописываются её три последние двоичные цифры;
- б) если число N на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
Полученная таким образом запись является двоичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее 200.»
Обратите особое внимание, что к заданиям 5 даются примеры! Обязательно проверяйте свои решения на числах из примеров, прежде чем давать ответ на это задание.
Итак, проанализируем условие. Работать мы будем с двоичной системой счисления – уже хорошо, не надо будет писать собственную функцию. Нам нужно будет определить делимость числа N на 3. Причем остаток от деления на 3 лучше выписать в отдельную переменную, так как он нам еще понадобится: «…остаток от деления умножается на 3…».
Что же, приступим к решению. Первым делом напишем цикл for и создадим диапазон чисел от 1 до 30 (число 30 подобрано опытным путём, вы можете использовать любое другое):
Далее переведём наше число N в двоичную систему счисления. Для этого воспользуемся функционалом f-строк:
Найдём остаток от деления этого числа на 3:
Тогда, если число делится на 3 без остатка, то есть он равен 0, будем выполнять действия из пункта а):
В противном случае, если остаток не равен 0, то умножаем его на 3 и переводим через f-строку в двоичную систему:
Осталось лишь перевести результат выполнения одного из условия в десятичную систему – это и будет искомое число R:
В целом, задание почти решено. Но давайте для начала проверим наш алгоритм на числах из условия. Для этого воспользуемся условной конструкцией, в которой приравняем число N к 12 или 4 и выведем результат работы программы – R. По условию мы ожидаем увидеть значения 100 и 19, соответственно:
Запускаем наш код и видим на экране два числа: 19 и 100. То есть мы все сделали верно и получили ожидаемые числа.
Теперь можем завершить нашу программу для получения ответа на задание. С помощью все того же условного оператора определим момент, в который число R станет не меньше 200. Как только это неравенство выполнится – выведем исходное число N и завершим работу цикла:
Весь наш код будет выглядеть так:
В результате работы программы получаем число 26. Оно и будет ответом на это задание.
Пример 2
Следующим рассмотрим задание с такой формулировкой:
«На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
a) если число N делится на 3, то слева к нему приписывается «1», а справа «02»;
б) если число N на 3 не делится, то остаток от деления на 3 умножается на 4, переводится в троичную запись и дописывается в конец числа.
Полученная таким образом запись является троичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, меньшее 100.»
Теперь нам предстоит поработать с троичной системой счисления. Для этого сначала напишем функцию перевода числа из десятичной в троичную систему. Можно воспользоваться универсальной, которую мы писали в прошлой статье. Но мы немного подправим её для перевода только в троичную систему. Выглядеть наша функция будет так:
Теперь, поскольку нам нужно найти максимальное значение N, в цикле будем перебирать натуральные числа «перевёрнутого» диапазона от 1 до 20 (точнее от 19 до 1):
Строим троичную записать натурального числа N:
Все так же находим остаток от деления на 3:
Условие будет все тем же, что и в прошлом задании – если остаток равен нулю, то выполняем действия из пункта а):
Иначе умножаем остаток на 4 и переводим в троичную систему:
Осталось перевести R в десятичную систему и проверить наш алгоритм на числах из условия:
Весь код у нас записывается так:
Запускаем его и получаем два числа: 353 и 107, которые совпадают с теми, что даны в условии. Значит, программа написана верно, можем дописывать последнее условие. Итоговый код выглядит следующим образом:
Запускаем его и получаем ответ на это задание – число 10.
Пример 3
Разберём еще одно задание:
«На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
- Из числа N вычитается остаток от деления N на 4
- Строится двоичная запись полученного результата
- К этой записи дописываются справа ещё два разряда по следующему правилу:
- складываются все цифры построенной двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
- над этой записью проводятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись является двоичной записью искомого числа R.
Укажите такое наибольшее N, для которого результат работы данного алгоритма меньше числа 47. В ответе это число запишите в десятичной системе счисления.»
Как вы могли заметить, эта формулировка немного отличается от двух предыдущих. Это же отразится и на решении.
Давайте по порядку. Цикл у нас стандартный с «перевёрнутым» диапазоном для поиска максимального N:
Теперь в отдельной переменной сохраним результат первого пункта алгоритма: «из числа N вычитается остаток от деления N на 4»:
Переведём число N_1 в двоичную систему:
И дальше есть несколько способов записать нужные действия. Тут снова распишем все подробно и по порядку:
- У нас двоичное число N_bin записано в виде строки
- Чтобы сложить все цифры этого числа, их нужно сначала перевести в целые числа. Для этого применим функцию int() к каждому элементу строки N_bin с помощью функции map(): map(int, N_bin)
- Результат работы map() теперь можно передать в функцию sum(), которая вернёт сумму всех цифр исходного числа N_bin
- Найти остаток от деления несложно: sum(map(int, N_bin)) % 2
- Но, чтобы дописать этот остаток к исходному числу N_bin, нужно перевести его в строчный тип данных: str(sum(map(int, N_bin)) % 2)
- Теперь уже можно дописать в конце N_bin полученное значение: N_bin += str(sum(map(int, N_bin)) % 2)
Разберём простой пример, чтобы лучше понять работу этого алгоритма. Представим, что число N у нас равно 19. Переведём его в двоичную систему и последовательно выполним каждое действие с выводом результата на экран:
То есть к исходному числу 10011 приписали остаток от деления суммы его цифр на 2 и получили число 100111, как это и было описано в условии.
Вернёмся к решению. На данный момент наша программа состоит из трех строчек:
Добавим к ней только что разобранную запись:
И далее в условии говорится: «над этой записью проводятся те же действия». Что же, не будем мудрить и просто продублируем последнюю строчку:
Теперь переводим получившееся число N_bin в десятичную систему и проверяем, в какой момент это число будет меньше 47. После чего выводим исходное N и останавливаем программу. Весь код у нас будет таким:
После успешного завершения программы получаем ответ на это задание – число 11.
На этом мы завершим разбор алгоритма решения первого типа 5 заданий. В следующей же статье научимся решать задания второго типа.
