Тип 2
В прошлой статье мы познакомились с тремя типами 8 заданий ЕГЭ по информатике и освоили алгоритм решения первого типа. Сейчас же перейдём к разбору решения второго типа этих заданий.
Как уже говорилось ранее, в 8 заданиях второго типа от нас требуется найти количество комбинаций чисел из исходного набора, которые будут удовлетворять заданным условиям.
По большей части решения здесь будут шаблонными, во многом похожие на решения заданий первого типа. Мы также будем формировать алфавит из исходных символов, производить размещения с повторением этих символов заданной длины. Далее, перебирая все эти размещения в цикле, будем подсчитывать, сколько из них удовлетворяют заданным условиям. Как обычно, самое важное здесь — не ошибиться в написании алфавита и верно переписать условия.
С вводной частью на этом всё, давайте переходить к разбору алгоритма решения.
Алгоритм решения
Сразу выпишем себе типовую формулировку:
«Сколько существует различных трёхзначных чисел, записанных в пятеричной системе счисления, в записи которых цифры следуют слева направо в невозрастающем порядке?»
Разберём её по частям. Итак, нас нужно искать различные трёхзначные числа. То есть это будут размещения по 3 числа: 012, 123, 234 и так далее. Следующее, что стоит уяснить — какие символы будет размещать. Это сказано далее в условии задания: «в пятеричной системе счисления». То есть нам доступны только символы этой системы: от 0 до 4.
Следом уже идёт условия, которым должны удовлетворять перебираемые трёхзначные числа: «Цифры следуют слева направо в невозрастающем порядке». Что это значит? Что левая цифра должна быть больше или равна правой, например, этому условию удовлетворяют такие числа: 321, 331, 444.
Но обратите внимание на ещё один момент, нам сразу говорят, что мы работаем именно с трёхзначными числами! То есть первой цифрой у нас никак не может быть 0! Это условие нам всегда нужно учитывать в заданиях такого типа.
Что же, с условием задания разобрались, давайте приступим к решению. Сначала импортируем нужную функцию из itertools и запишем алфавит. Помните, что для размещений с повторением мы всегда используем функцию product()!
Теперь давайте заведём переменную-счётчик, значение которой будем увеличивать каждый раз, когда рассматриваемое трёхзначное число удовлетворяет нашим условиям. Назовём её просто и понятно: count.
Далее напишем цикл, в котором будем перебирать результаты работы функции product() — размещения исходных цифр «01234» с повторениями. Как уже говорилось ранее, нам удобнее будет работать со строками, следовательно, переведём список цифр, который нам вернёт product() в строку методом join:
Ну а далее осталось лишь записать условие. Первой у нас будет всегда будет идти проверка первой цифры — она не должна быть нулём: val[0] != ‘0’. А вторым запишем условие невозрастающего порядка цифр в числе: val[0] >= val[1] >= val[2]. То есть мы здесь потребовали, чтобы первая цифра была больше или равна второй, а вторая — больше или равна третьей.
Теперь внутри условия напишем операцию увеличения значения переменной count на 1.
Всё, осталось лишь вывести значение переменной-счётчика на экран после завершения работы цикла:
Наша программа готова, смело запускаем её и видим на экране число 34. Оно и будет ответом на это задание.
Пример 1
Рассмотрим еще одну формулировку второго типа 8 задания:
«Сколько существует семеричных пятизначных чисел, содержащих в своей записи ровно одну цифру 6 и не содержащих идущих подряд одинаковых цифр?»
Давайте снова разберём её по частям. Работать мы теперь будем с пятизначными числами, значит параметр repeat в функции product() будет равняться 5. Также у нас теперь семеричные числа, значит нам доступны символы от 0 до 6.
С условием про содержание только одной цифры 6 все понятно. Но вот второе условие уже может вызвать трудности: «не содержащих идущих подряд одинаковых цифр».
Подумаем, как проверить, что идущие подряд цифры числа различны. Очевидно, что нам следует в цикле перебрать каждую цифру и сравнить её с последующей — они не должны быть равны. И если для всех цифр это неравенство сохраняется, то тогда условие будет выполнено.
Осталось лишь записать это на языке Python. Начнём с конца: фраза «для всех» означает, что нам здесь не обойтись без функции all(). Она вернёт истину только в том случае, если все элементы переданного ей итерируемого объекта истинны. Что мы можем ей передать?
Например, мы можем передать список логических значений, которые нам вернёт проверка каждой пары цифр: если две идущие подряд цифры не равны, то это будет истина. Попробуем вручную это продемонстрировать. Рассмотрим число 12345. Сравним идущие подряд цифры:
- 1 не равно 2 => Истина
- 2 не равно 3 => Истина
- 3 не равно 4 => Истина
- 4 не равно 5 => Истина
Как нам таким же образом проверить все цифры и сформировать список с результатами проверок? Это можно сделать, например, списочным включением: в цикле будем перебирать индексы пятизначного числа (от 0 до 4) и сравнивать элементы с текущим индексом и с последующим. Запишем это так:
Отлично, получили такой же список четырёх истин. Теперь, если мы его передадим в функцию all(), она нам даст ответ на вопрос: «для всех ли цифр сохраняется неравенство?». Можем записать это таким образом:
Теперь мы можем избавиться от лишней переменной booleans и сразу записать списочное включение внутри функции all():
Готово! Теперь у нас есть код для проверки условия «содержит ли пятизначное число идущие подряд цифры». Давайте тогда приступим к решению всего задания. Импортируем функцию и выписываем алфавит из условия:
Создаём переменную-счётчик и запускаем цикл по всем размещениям с повторением:
И теперь условия:
- Сразу требуем, чтобы 0 не стоял на месте первой цифры: val[0] != ‘0’
- Далее потребуем, чтобы цифра 6 была только одна: count(‘6’) == 1
- И в конце запишем ранее полученный код: all([num[i] != num[i+1] for i in range(4)])
В итоге получаем такую программу:
Запускаем её и видим ответ на это задание — число 3625.
Пример 2
Для закрепления рассмотрим еще одно задание:
«Определите количество пятизначных чисел, записанных в восьмеричной системе счисления, в записи которых ровно две цифра 4, и при этом никакая нечётная цифра не стоит рядом с цифрой 4.»
По своей структуре, задание очень похоже на прошлое. С двумя цифрами 4 все понятно, а вторая часть формулировки снова может вызвать вопросы. Давайте сконцентрируемся на ней.
Итак, нам нужно определить, что никакая нечётная цифра не стоит рядом с 4. Тут можем пойти от обратного: выписать все «недопустимые» пары — такие, в которых рядом с цифрой 4 стоит нечётная цифра. Это будут следующие пары: 14, 34, 54, 74, 41, 43, 45, 47.
В таком случае нам останется лишь проверить, что ни одной из этих пар нет в наших пятизначных числах. Тут снова придёт на помощь функция all().
Например, определим, что число 12442 удовлетворяет нашему условию. Выпишем сначала наши недопустимые пары:
И теперь такой записью будем перебирать все «недопустимые» пары и проверять, что ни одной из них нет в числе num: all(pair not in num for pair in wrong_pairs). В нашей программе это будет выглядеть так:
Отлично, с этим разобрались, давайте приступим к решению задания. Работаем мы с восьмеричными цифрами, значит, алфавит у нас от 0 до 7:
Выписываем «недопустимые» пары, создаём переменную count и цикл:
Далее добавляем три условия:
- Первая цифра — не 0
- Количество 4 — 2 штуки
- В числе нет «недопустимых» пар
В итоге наша программа приобретает такой вид:
Запускаем её и довольствуемся ответом на данное задание — числом 612.
Итоги
Давайте, как и в прошлой статье, выведем шаблонный код для решения 8 заданий второго типа:
Здесь:
*1 — алфавит из условия (восьмеричные числа — цифры от 0 до 8, троичные — от 0 до 2 и так далее)
*2 — количество цифр в числе (пятизначное — 5, шестизначное — 6 и так далее)
*3 — условия, которым должны соответствовать полученные комбинации (первым всегда идёт неравенство первой цифры нулю!)
На этом мы закончим разбор второго типа 8 заданий ЕГЭ. В следующей статье перейдём к заключительному, третьему, типу и научимся работать с функцией permutations().