Тип 2
В прошлой статье мы уже научились работать с различными системами счисления на языке Python и освоили алгоритм решения первого типа 5 заданий ЕГЭ по информатике.
Теперь же приступим к разбору алгоритма решения второго типа этих заданий. Напомним, что в прошлый раз нам необходимо было найти исходное число N, подходящее под условия. В заданиях второго типа от нас требуется вывести уже результат работы алгоритма – число R – при некотором условии для исходного числа N, поступающего на вход алгоритма.
Давайте рассмотрим, как этот момент отразится на алгоритме решения.
Алгоритм решения
Как и в заданиях прошлого типа, от нас потребуется вывести максимальное или минимальное значение некоторого числа R. Вот только в случае с исходным числом мы могли просто «перевернуть» диапазон натуральных чисел в цикле. Но для определения числа R такой способ не сработает.
Все дело в том, что никто не гарантирует линейное поведение заданного алгоритма! Иными словами, у нас нет абсолютно никакой уверенности, что минимальное R будет в начале работы алгоритма, а максимальное – в конце.
Давайте убедимся в этом на реальном примере. Рассмотрим такую формулировку:
«Строится двоичная запись натурального числа N.
Далее эта запись обрабатывается по следующему правилу:
- если число чётное, то к двоичной записи числа слева дописывается 10;
- если число нечётное, то к двоичной записи числа слева дописывается 1 и справа дописывается 01.
Результат переводится в десятичную систему. Нужно найти минимальное R, при условии, что N меньше 10»
Пока не будем расписывать программное решение, обратимся только к результатам работы такого алгоритма. При передачи в него значений от 1 до 9, числа R будут следующими: 13, 10, 29, 20, 53, 22, 61, 40, 101.
Как нетрудно догадаться, минимальным здесь является число 10. Но находится оно совсем не на первой позиции. Как же быть в таком случае?
Решение очевидно – нужно сохранять все результаты работы алгоритма в отдельный список. Сделать это несложно, достаточно к нашему привычному циклу добавить буквально две строчки: переменную res с пустым списком в начале и внутри цикла добавление значения R в res методом append.
Для вывода максимального или минимального значения R воспользуемся встроенными функциями max() и min(), которые применим к списку со всеми значениями R:
Это буквально все изменения в типовом алгоритме решения. Давайте скорее его опробуем на реальной задаче.
Пример 1
Начнём сегодня с такой формулировки:
«На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
- если число чётное, то к двоичной записи числа слева дописывается 10;
- если число нечётное, то к двоичной записи числа слева дописывается 1 и справа дописывается 01.
Полученная таким образом запись является двоичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 410 = 1002 результатом является число 2010 = 101002, а для исходного числа 510 = 1012 это число 5310 = 1101012.
Укажите максимальное число R, которое может быть результатом работы данного алгоритма, при условии, что N не больше 12. В ответе запишите это число в десятичной системе счисления.»
Сразу обратим внимание на условие «N не больше 12». Для его выполнения нам достаточно просто указать диапазон натуральных чисел от 1 до 12 (включительно): range(1, 13).
С правилами, по которым работает алгоритм, мы уже знакомились ранее. В них нет ничего необычного для нас: нужно определить чётность числа и, в зависимости от неё, дописывать значения к числу. Давайте приступим к написанию кода.
Сначала определим переменную для результатов работы алгоритма:
Далее создадим цикл с рассмотренным выше диапазоном:
Построим двоичную запись для каждого числа:
Далее, если число чётное, то будем слева двоичной записи дописывать 10, а в противном случае слева 1 и справа 01. Распишем все это на языке Python:
Осталось лишь перевести результат работы алгоритма в десятичную систему счисления. Это и будет наше число R:
Теперь проверим наш алгоритм на примерах из формулировки задания: подставим в качестве N числа 4 и 5 и выведем на экран результат:
В итоге видим числа 20 и 53, которые совпадают с теми, что даны в условии. Значит, программа написана верно, можем добавлять каждое значение R в список и выводить на экран максимальное число из этого списка. Итоговый код у нас выглядит так:
А в результате его работы получаем число 109, которое и будет ответом на это задание.
Пример 2
Теперь рассмотрим 5 задание с такой формулировкой:
«На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
- если число N делится на 3, то к этой записи дописываются две последние троичные цифры;
- если число N на 3 не делится, то вычисляется сумма цифр полученной троичной записи, эта сумма переводится в троичную систему счисления и дописывается в конец числа.
Полученная таким образом запись является троичной записью искомого
числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 1110 = 1023 результатом является число 102103 = 10210, а для исходного числа 1210 = 1103 это число 110103 = 11110.
Укажите минимальное чётное число R, большее 220, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления»
Нам предстоит работа с троичной системой счисления. Вспомним функцию для перевода чисел в троичную систему из прошлой статьи:
Дальше решение будет типовым: создаём переменную для сохранения результатов, цикл натуральных чисел до 250 и строим троичную запись:
Проверяем делимость на 3 и дописываем две последние цифры в случае истинности условия, либо дописываем сумму цифр в троичной системе в противоположном случае. Работу с суммой цифр мы подробно разобрали в предыдущей статье, останавливаться на этом не будем.
Далее обойдёмся без проверок значений из условия. Сразу переведём полученное после работы алгоритма число в десятичную систему и далее запишем условие для определения подходящего числа.
Это число должно быть, во-первых, чётным, во-вторых, большим 220. Отразим это в условии:
Осталось лишь вывести минимальное значение из списка на экран. Итоговый код для решения этого задания будет такой:
Да, здесь можно было воспользоваться оператором break для остановки цикла и сразу вывести первое подходящее R. Но мы не будем отходить от типового решения. К тому же, в следующем примере вы сами убедитесь в том, что всегда лучше сохранять результаты в список!
В любом случае, после завершения работы программы, мы готовы дать ответ на это задание – число 222.
Пример 3
В заключении рассмотрим такую формулировку:
«На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
- если число N делится на 3, то к этой двоичной записи дописываются две последние троичные цифры;
- если число N на 3 не делится, то остаток от деления умножается на 5, переводится в троичную запись и дописывается в конец полученной ранее двоичной записи числа N.
Полученная таким образом запись является троичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 1110 = 1023 результатом является число 1021013 = 30710, а для исходного числа 1210 = 1103 это число 110103 = 11110.
Укажите минимальное число R, большее 150, которое может быть получено с
помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.»
Помните, что мы только что говорили про сохранения результатов в список? Из примера в условии мы уже можем увидеть, что алгоритм выдаёт значения не линейно: для числа 11 результатом является 307, а для 12 – 111. То есть итоговые значения идут не в строгом порядке возрастания!
В своём решении это задание похоже на второй пример из прошлой статьи. Так что подробно останавливаться на разборе кода в этот раз не будем. Запишем его следующим образом:
Больше заданий данного типа с подробным решением вы можете найти в нашем тренажёре