Тип 3
Пришло время рассмотреть третий тип 8 заданий ЕГЭ по информатике. Ранее мы уже научились применять функцию product() для поиска номера подходящего слова в первом типе и количества комбинаций во втором типе этих заданий.
Задания третьего типа очень похожи на задания второго: мы также работаем с цифрами, ищем количество комбинаций, которые удовлетворяют условиям. Отличия только в одной фразе: «все цифры различны». То есть здесь мы будем работать с перестановками.
Задания такого типа крайне редко попадаются на экзаменах. Так что и примеры сегодня будут все очень похожи друг на друга. Приступим к разбору алгоритма решения.
Алгоритм решения
На самом деле алгоритм решения заданий третьего типа практически идентичен алгоритму решения заданий второго типа. Единственное отличие заключается в том, что вместо функции product() теперь мы будем использовать функцию permutations().
Но многие формулировки 8 заданий этого типа содержат в себе одно условие, которое может ввести в ступор неподготовленного ученика. Именно его разбору мы и посвятим большую часть времени.
Сразу рассмотрим такую типовую формулировку:
«Сколько существует восьмеричных пятизначных чисел, не содержащих в своей записи цифру 1, в которых все цифры различны и никакие две чётные или две нечётные цифры не стоят рядом?»
Тут уже все для нас знакомо, восьмеричные числа, значит, алфавит от 0 до 7. Пятизначные — значит, будет перестановка 5 символов, то есть параметр r функции permutations() равняется 5. Необычное для нас здесь следующее: «никакие две чётные или две нечётные цифры не стоят рядом». Давайте подумаем, как это можно определить.
Первое, что приходит в голову — пройтись по каждой паре цифр числа и проверить, если текущая цифра четная, а последующая нечётная, то такая пара нам подходит. И так продолжать проверять пары цифр, пока не переберём все.
Нечто похожее у нас было в прошлой статье, когда мы рассматривали текущую цифру числа и следующую, чтобы определить, что у нас не идут подряд одинаковые цифры. Тогда мы пользовались функцией all() и списочным включением. Теперь же задача более объемная, так что нагляднее будет создать отдельную функцию. Назовём её «is_even_pair» (хоть логичней было бы назвать «is_not_even_pair», но остановимся на более коротком варианте). И, как следует из названия, проверять будем четность пар цифр.
Определим нашу функцию. Принимать она будет всего один аргумент — проверяемое число (в виде строки, само собой):
Теперь в ней создадим цикл по индексам этого числа. Поскольку мы делаем универсальную функцию, то в качестве аргумента в range() передадим количество символов числа минус 1, поскольку у нас индексы «сдвинуты» в сторону нуля (для пятизначного числа индексы будут от 0 до 4).
Теперь проверим четность текущей цифры (с индексом i):
Аналогично проверим четность следующей цифры (с индексом i+1):
Осталось лишь написать условие завершения работы функции. То есть если текущее число чётное (в current_is_even истина) и следующее тоже чётное (в next_is_even истина), то такое число нам не подходит, завершаем работу функции и возвращаем ложь:
Тогда в противном случае — если все проверки пройдены и условие в if ни разу не сработало, то это означает, что цифры в числе чередуются: четное-нечётное-чётное (или наоборот) и так далее. Следовательно, такое число нам подходит, и функция должна вернуть истину. Значит, после завершения работы цикла мы пишем return True:
Все, наша функция для проверки чередования чётности цифр готова! Именно её мы и будем использовать во всех примерах в этой статье.
Можем смело переходить к решению рассматриваемого задания. Вспомним, что работаем мы с восьмеричными числами, следовательно, алфавит у нас от 0 до 7, верно? По сути верно, но в условии у нас сказано, что числа не содержат в своей записи цифру 1. Так давайте сразу её и исключим из алфавита:
Далее вставляем код нашей функции:
А затем идёт уже знакомая нам конструкция: создание переменной-счётчика, цикл по перестановкам из 5 элементов, проверка, что первая цифра не является нулём и проверка второго условия нашей функцией, после прохождения всех проверок увеличивается значение счётчика, а по завершении работы цикла — выводится значение счётчика на экран.
Вся наша программа в итоге выглядит так:
А в результате её работы получается число 180. Его и запишем в ответ.
Пример 1
Перейдём к следующему заданию:
«Сколько существует десятичных четырёхзначных чисел, в которых все цифры различны и никакие две чётные или две нечётные цифры не стоят рядом?»
Здесь все еще проще. Алфавит у нас состоит из десяти привычных нам цифр от 0 до 9. Работать будем с четырёхзначными числами, в качестве второго аргумента в функцию permutations() передаём число 4.
А для проверки, что две чётные или две нечётные цифры не стоят рядом, у нас уже есть готовая функция. Таким образом, нам остаётся лишь поменять алфавит и второй аргумент функции. В итоге наша программа будет выглядеть так:
А в результате её работы получим число 720, которое и будет ответом на это задание.
Пример 2
Для закрепления рассмотрим еще одно задание:
«Сколько существует шестнадцатеричных трёхзначных чисел, в которых все цифры различны и никакие две чётные или две нечётные цифры не стоят рядом?»
Тут мы впервые работаем с системой счисления выше 10 в рамках 8 заданий. Но это не должно нас пугать, ведь еще с 14 заданий мы умеем получать все цифры любой системы счисления через константу printable из модуля string.
Вспомним, как получит все цифры шестнадцатеричной системы счисления:
С помощью этого же среза сформируем наш алфавит:
Но не спешите переписывать нашу функцию is_even_pair()! Дело в том, что при работе с системами счисления свыше десятой, нужно указывать основание этой системы в функции int().
То есть если мы попытаемся перевести шестизначное число «А1» в десятичное с помощью функции int(), то получим ошибку:
Здесь необходимо вторым аргументом в функции int() написать основание нашей системы счисления — число 16:
Учитывая этот момент, поправим код функции is_even_pair():
Оставшийся же код программы вам уже знаком. Целиком программа выглядит так:
Запустив её, получим число 840, которое и запишем в ответ на это задание.
Итоги
Мы разобрали все три типа 8 заданий и научились пользоваться функциями product() и permutations() для реализации размещений с повторением и перестановок элементов. Давайте не будем отступать от формата и составим такой же шаблонный код для решения третьего типа 8 заданий:
Здесь:
*1 — алфавит из условия (восьмеричные числа — цифры от 0 до 8, троичные — от 0 до 2 и так далее)
*2 — количество цифр в числе (пятизначное — 5, шестизначное — 6 и так далее)
*3 — условия, которым должны соответствовать полученные комбинации (первым всегда идёт неравенство первой цифры нулю!)
Больше заданий данного типа с подробным решением вы можете найти в нашем тренажёре.