Алгоритм решения задания 8. Часть 2

В прошлой статье мы познакомились с тремя типами задания 8 ЕГЭ по информатике и освоили алгоритм решения первого типа. Сейчас же перейдём к разбору решения второго типа этих заданий.

Во втором типе задания 8 требуется найти количество чисел или последовательностей из заданного набора символов, которые удовлетворяют условиям.

Решения во многом похожи на первый тип. Составляем алфавит, генерируем размещения с повторениями и в цикле считаем подходящие варианты. Главное — правильно записать алфавит и все условия.

С вводной частью закончили. Перейдём к алгоритму решения.

Алгоритм решения

Начнём с типовой формулировки:

Сколько существует различных трёхзначных чисел, записанных в пятеричной системе счисления, в записи которых цифры следуют слева направо в невозрастающем порядке?

Открыть задание

Нужно найти количество трёхзначных чисел. Значит, будем составлять последовательности длины 3. Числа записаны в пятеричной системе, поэтому доступны цифры от 0 до 4.

Цифры должны идти слева направо в невозрастающем порядке: каждая следующая цифра не больше предыдущей. Например, условию удовлетворяют числа 321, 331 и 444.

Не забудьте: речь идёт именно о трёхзначных числах, поэтому первая цифра не может быть нулём. Это условие важно учитывать во всех подобных задачах.

Сначала импортируем product() и запишем алфавит. Буквы и цифры здесь могут повторяться, поэтому используем размещения с повторениями.

from itertools import product

alph = "01234"

Создадим переменную-счётчик count. Её значение будем увеличивать каждый раз, когда очередное число удовлетворяет условиям.

from itertools import product

alph = "01234"

count = 0

Теперь переберём результаты product(). Функция возвращает кортежи цифр, поэтому соединим их в строку методом join():

from itertools import product

alph = "01234"

count = 0
for val in product(alph, repeat=3):
    val = "".join(val)

Осталось записать два условия. Первая цифра не должна быть нулём: val[0] != '0'. Цифры должны идти в невозрастающем порядке: val[0] >= val[1] >= val[2].

from itertools import product

alph = "01234"

count = 0
for val in product(alph, repeat=3):
    val = "".join(val)
    if val[0] != '0' and val[0] >= val[1] >= val[2]:

Внутри условия увеличиваем count на единицу:

from itertools import product

alph = "01234"

count = 0
for val in product(alph, repeat=3):
    val = "".join(val)
    if val[0] != '0' and val[0] >= val[1] >= val[2]:
        count += 1

Всё, осталось вывести count после завершения цикла:

from itertools import product

alph = "01234"

count = 0
for val in product(alph, repeat=3):
    val = "".join(val)
    if val[0] != '0' and val[0] >= val[1] >= val[2]:
        count += 1

print(count)

Программа выводит 34. Это ответ.

Пример 1

Рассмотрим ещё одну формулировку второго типа задания 8:

Сколько существует семеричных пятизначных чисел, содержащих в своей записи ровно одну цифру 6 и не содержащих идущих подряд одинаковых цифр?

Открыть задание

Теперь работаем с пятизначными семеричными числами. Поэтому repeat=5, а алфавит состоит из цифр от 0 до 6.

Условие о единственной цифре 6 записать просто. Сложнее проверить, что одинаковые цифры не стоят рядом.

Сравним каждую цифру со следующей. Условие выполнено, если все четыре соседние пары состоят из разных цифр.

Фразе «для всех» соответствует функция all(). Она вернёт True, только если истинны результаты всех переданных проверок.

Передадим в all() результаты сравнения соседних цифр. Например, для числа 12345 проверки будут такими:

1 не равно 2 => Истина
2 не равно 3 => Истина
3 не равно 4 => Истина
4 не равно 5 => Истина

Для пятизначного числа сравниваются пары с индексами 0–1, 1–2, 2–3 и 3–4. Значит, перебираем i от 0 до 3:

num = '12345'

booleans = [num[i] != num[i+1] for i in range(4)]
print(booleans)

>>>[True, True, True, True]

Получили четыре значения True. Если передать их в all(), функция подтвердит, что все соседние цифры различны:

num = '12345'

booleans = [num[i] != num[i+1] for i in range(4)]

if all(booleans):
    print("Для всех")

>>>Для всех

Промежуточный список не нужен: генератор с проверками можно сразу передать в all():

num = '12345'

if all(num[i] != num[i+1] for i in range(4)):
    print("Для всех")

Теперь у нас есть выражение, которое проверяет отсутствие одинаковых соседних цифр. Перейдём к решению всей задачи: импортируем product() и запишем алфавит.

from itertools import product

alph = "0123456"

Создаём переменную-счётчик и запускаем цикл по всем размещениям с повторением:

from itertools import product

alph = "0123456"

count = 0
for val in product(alph, repeat=5):
    val = "".join(val)

Добавим условия:

Первая цифра не равна нулю: val[0] != '0';
Цифра 6 встречается ровно один раз: count('6') == 1;
Все соседние цифры различны: all(val[i] != val[i+1] for i in range(4)).

В итоге получаем такую программу:

from itertools import product

alph = "0123456"

count = 0
for val in product(alph, repeat=5):
    val = "".join(val)
    if (val[0] != '0'
            and val.count('6') == 1
            and all(val[i] != val[i+1] for i in range(4))):
        count += 1

print(count)

Программа выводит 3625. Это ответ.

Пример 2

Для закрепления рассмотрим ещё одно задание:

Определите количество пятизначных чисел, записанных в восьмеричной системе счисления, в записи которых ровно две цифра 4, и при этом никакая нечётная цифра не стоит рядом с цифрой 4.

Открыть задание

По структуре задача похожа на предыдущую. Условие о двух цифрах 4 простое, поэтому сосредоточимся на запрете соседства с нечётными цифрами.

Пойдём от обратного и выпишем запрещённые пары, в которых рядом с цифрой 4 стоит нечётная цифра: 14, 34, 54, 74, 41, 43, 45 и 47.

Остаётся проверить, что ни одна запрещённая пара не входит в число. Снова воспользуемся all().

Проверим на примере числа 12442. Сначала запишем множество запрещённых пар:

num = "12442"

wrong_pairs = {'14', '34', '54', '74', '41', '43', '45', '47'}

Переберём запрещённые пары и проверим, что ни одна из них не входит в строку num: all(pair not in num for pair in wrong_pairs).

num = "12442"

wrong_pairs = {'14', '34', '54', '74', '41', '43', '45', '47'}

if all(pair not in num for pair in wrong_pairs):
    print("Удовлетворяет")

>>>Удовлетворяет

Числа восьмеричные, поэтому алфавит состоит из цифр от 0 до 7:

from itertools import product

alph = '01234567'
Запишем запрещённые пары, создадим счётчик и цикл:
from itertools import product

alph = '01234567'
wrong_pairs = {'14', '34', '54', '74', '41', '43', '45', '47'}

count = 0
for val in product(alph, repeat=5):
    val = "".join(val)

Далее добавляем три условия:

Первая цифра не равна нулю;
Цифра 4 встречается ровно два раза;
В числе нет запрещённых пар.

В итоге наша программа приобретает такой вид:

from itertools import product

alph = '01234567'
wrong_pairs = {'14', '34', '54', '74', '41', '43', '45', '47'}

count = 0
for val in product(alph, repeat=5):
    val = "".join(val)
    if (val[0] != '0'
            and val.count('4') == 2
            and all(pair not in val for pair in wrong_pairs)):
        count += 1

print(count)

Программа выводит 612. Это ответ.

Итоги

Как и в прошлой статье, запишем шаблон решения второго типа задания 8:

from itertools import product

alph = '*1'

count = 0
for val in product(alph, repeat=*2):
    val = "".join(val)
    if val[0] != '0' and *3:
        count += 1

print(count)

Здесь:

*1 — алфавит из условия: для восьмеричной системы цифры от 0 до 7, для троичной — от 0 до 2 и так далее;
*2 — количество цифр в числе; это число подставляется без кавычек;
*3 — остальные условия. Если составляются числа, отдельно проверьте, что первая цифра не равна нулю.

На этом разбор второго типа задания 8 закончен. В следующей статье перейдём к третьему типу и воспользуемся функцией permutations().

Алгоритм решения задания 8. Часть 2

Алгоритм решения

Пример 1

Пример 2

Итоги

Рекомендуемые статьи