Зад 8 2

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

В предыдущей статье мы разобрали основы комбинаторики и её принципы, которые лежат в основе этих задач. Теперь настало время углубиться в практическую сторону вопроса и рассмотреть конкретные алгоритмы и инструменты, которые помогут вам эффективно справляться с заданием 8.

Особенно полезными в этом контексте оказываются функции из встроенного в Python модуля itertools, такие как product() и permutations(). Эти функции позволяют быстро генерировать различные комбинации и перестановки элементов, что нередко требуется при решении комбинаторных задач.

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

В данной статье мы выделим основные формулировки задания 8, научимся использовать функции модуля itertools, а также подробно разберём несколько типовых примеров этого задания.

Функции Python

Прежде, чем перейти к разбору формулировок задания 8, рассмотрим некоторые функции Python, которые будем использовать в процессе решения.

На повестке у нас две функции из модуля itertools: product() и permutations(). А также, не лишним будет вспомнить работу функции enumerate() внутри цикла for.

Функция product()

Функция product() позволяет генерировать декартово произведение нескольких итерируемых объектов, а также используется для генерации размещений с повторением. Работу с декартовым произведением рассматривать в рамках данной статьи мы не будем.

В комбинаторике размещение с повторениями — это способ выбора n-элементных последовательностей из m-элементного множества, где каждый элемент может быть выбран неограниченное количество раз.

Например, если у нас есть множество A={1,2} и мы хотим сформировать все возможные последовательности длины 3, то результатом будут следующие комбинации: (1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2).

Функция product() реализует этот процесс автоматически, позволяя нам указать исходные множества и длину комбинаций. Она особенно полезна при решении задач, связанных с перебором вариантов или генерацией кодовых слов.

Давайте рассмотрим синтаксис данной функции:

product(*iterables, repeat=1)

Параметры функции:

  • *iterables: Один или несколько итерируемых объектов (например, списки, строки, кортежи).
  • repeat: Необязательный параметр, определяющий, сколько раз нужно взять декартово произведение множества с самим собой. По умолчанию равен 1.

Именно параметр repeat позволяет выбирать, что именно мы хотим получить: декартово произведение или размещение с повторением. Если указан параметр repeat, отличный от 1, то будут сгенерированы размещения с повторением элементов исходного итерируемого объекта, указанной длины.

Такая функциональность очень полезна при решении задач типа 8 ЕГЭ, где требуется найти количество кодовых слов или комбинаций символов. Например, если в условии говорится, что кодовое слово состоит из 4 букв, выбранных из набора {A, B, C}, и буквы могут повторяться, то мы можем использовать product() для генерации всех возможных вариантов:

from itertools import product

# Исходное множество букв
letters = ['A', 'B', 'C']

# Генерация всех четырёхбуквенных слов
words = list(product(letters, repeat=4))

# Подсчёт количества слов
print(len(words))

>>>81

В результате работы программы, получаем число 81, что означает количество размещений из 3 элементов по 4 или же 34.

Функция permutations()

Давайте аналогичным образом разберем функцию permutations().

Данная функция позволяет генерировать все возможные перестановки элементов заданного итерируемого объекта.

Как и в случае с product(), которая по умолчанию вычисляет декартово произведение, так и permutations(), без передачи второго аргумента будет вычислять только перестановки элементов множества.

Но также, эту функцию можно использовать и для генерации размещений элементов без повторений. Для этого необходимо ограничивать длину перестановок.

Рассмотрим синтаксис функции permutations():

permutations(iterable, r=None)

Параметры функции:

  • iterable : Итерируемый объект (например, список, строка, кортеж), из которого нужно формировать перестановки.
  • r : Необязательный параметр, указывающий длину перестановок. Если параметр не указан, то по умолчанию используется длина исходного итерируемого объекта.

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

Рассмотрим пример, где мы хотим получить все возможные перестановки из трёх букв {′A′,′B′,′C′}:

from itertools import permutations

# Исходное множество
letters = ['A', 'B', 'C']

# Генерация всех перестановок
permutations = list(permutations(letters))

# Вывод результатов
for p in permutations:
    print(p)

>>> ('A', 'B', 'C') ('A', 'C', 'B') ('B', 'A', 'C') ('B', 'C', 'A') ('C', 'A', 'B') ('C', 'B', 'A')

Теперь же, ограничим длину перестановок до 2. То есть получим таким образом размещения из 3 элементов по 2.

from itertools import permutations

# Исходное множество
letters = ['A', 'B', 'C']

# Генерация всех перестановок
permutations = list(permutations(letters, 2))

# Вывод результатов
for p in permutations:
    print(p, end=" ")

>>> ('A', 'B') ('A', 'C') ('B', 'A') ('B', 'C') ('C', 'A') ('C', 'B')

В каких случаях можно использовать данную функцию в заданиях ЕГЭ? Поскольку, в permutations() все элементы в каждой комбинации различны, то она подходит в тех случаях, когда требуется составить кодовые слова без повторений или проверить, что все цифры числа различны.

Например, в условии говорится, что нужно составить все возможные четырёхбуквенные слова из букв {A, B, C, D} без повторений и вывести количество таких слов.

Можем использовать такую программу для решения:

from itertools import permutations

# Исходное множество букв
letters = ['A', 'B', 'C', 'D']

# Генерация всех четырёхбуквенных слов без повторений
words = list(permutations(letters, 4))

# Подсчёт количества слов
print(len(words)) 

>>>24

Функция enumerate()

Функция enumerate() в Python — это встроенная функция, которая позволяет добавить к элементам итерируемого объекта их порядковые номера (индексы).

Это удобный инструмент для работы с коллекциями данных, когда требуется одновременно получать как сам элемент, так и его позицию в коллекции. Вместо того чтобы вручную отслеживать индекс при переборе элементов, enumerate() автоматически генерирует пары (индекс, значение).

Основной синтаксис функции выглядит так:

enumerate(iterable, start=0)

Параметры функции:

  • iterable: Итерируемый объект, который нужно обойти.
  • start: Необязательный параметр, определяющий начальное значение индекса. По умолчанию равен 0.

Функция enumerate возвращает объект-итератор, состоящий из пар (индекс, значение). Этот объект можно преобразовать в список или использовать непосредственно в цикле for.

Рассмотрим простой пример, где мы хотим получить индексы и значения элементов списка:

fruits = ['Яблоко', 'Банан', 'Вишня']

# Использование enumerate
for index, fruit in enumerate(fruits, start=1):
    print(f"{index}. {fruit}")

>>>1. Яблоко
>>>2. Банан
>>>3. Вишня

Как вы видите, использование enumerate() позволяет легко определить индекс нужного элемента итерируемого объекта. Так, вы можете сформировать все размещения элементов множества, с помощью цикла проверять каждую комбинацию, и, если она соответствует требуемому условию, вывести порядковый номер этой комбинации.

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

Базовых формулировок задания 8 у нас всего 3. Их легко отличить по условию, согласно которому формируется ответ. Причем решения заданий разных типов не особо отличаются друг от друга.

Главным, на что стоит обратить внимание — это наличие повторений элементов. От этого зависит, какую из двух функций будем использовать: product() или permutations().

Тип 1

К первому типу отнесём задания, в которых даётся алфавит, обычно записанный кириллицей, буквы которого записываются в алфавитном порядке и формируют некоторый пронумерованный список слов. В ответ же нам требуется дать порядковый номер слова, которое удовлетворяет заданному условию.

Рассмотрим такую формулировку:

Задание 800

«Все пятибуквенные слове, в составе которых могут быть только русские буквы Я, Н, В, А, Р, Ь, записаны в алфавитном порядке и пронумерованы, начиная с 1. Ниже приведено начало списка.
1. ААААА
2. ААААВ
3. ААААН
4. ААААР
5. ААААЬ
6. ААААЯ
7. АААВА

Под каким номером в списке идёт последнее слово, которое не начинается с буквы Я, содержит не более одной буквы Ь и не содержит букв Я, стоящих рядом?»

Мы сразу видим, что буквы в словах могут повторяться. Это говорит о том, что использовать будем размещения с повторением или же функцию product(). Слова у нас пятибуквенные, значит параметр repeat будет принимать значение 5.

Далее, нам нужно найти порядковый номер слова. Следовательно, в этом поможет функция enumerate() в цикле for.

Начинаем решение этого задания с импорта product() из модуля itertools и формирования алфавита, который сразу же отсортируем в алфавитном порядке:

from itertools import product

# Алфавит из условия
alph = "ЯНВАРЬ"
# В алфавитном порядке
alph = sorted(alph)

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

В цикле будем перебирать все размещения элементов из алфавита и проверять условие: первый элемент не должен быть символом “Я”, количество символов “Ь” должно быть меньше или равно 1 и сочетание символов “Я” не должно входить в рассматриваемую строку. Поскольку все условия должны выполняться одновременно, то между каждым условием будем использовать оператор and.

for pos, val in enumerate(product(alph, repeat=5), start=1):
    val = "".join(val)
    if val[0] != "Я" and val.count("Ь") <= 1 and "ЯЯ" not in val:
        last_pos = pos

Итоговый код для решения данного задания будет такой:

 from itertools import product

# Алфавит из условия
alph = "ЯНВАРЬ"
# В алфавитном порядке
alph = sorted(alph)

# Переменная для хранения последней позиции
last_pos = 0

for pos, val in enumerate(product(alph, repeat=5), start=1):
    val = "".join(val)
    if val[0] != "Я" and val.count("Ь") <= 1 and "ЯЯ" not in val:
        last_pos = pos

print(last_pos)

В результате на экран выводится число 6406, которое мы и запишем в ответ.

Пример 1

Задание 801

«Все пятибуквенные слова, в составе которых могут быть только русские буквы Л, А, Й, М, записаны в алфавитном порядке и пронумерованы начиная с 1.
Вот начало списка:
1. ААААА
2. ААААЙ
3. ААААЛ
4. ААААМ
5. АААЙА

Под каким номером в списке идёт последнее слово, которое не содержит ни одной буквы М, ни одной буквы Л и не содержит букв Й стоящих рядом?»

Решение, в целом, здесь будет аналогичное. Составляем алфавит и сортируем в алфавитном порядке:

from itertools import product

# Алфавит из условия
alph = "ЛАЙМ"
# В алфавитном порядке
alph = sorted(alph)

Проверять отсутствие какой-либо буквы в слове будем операторами not in:

for pos, val in enumerate(product(alph, repeat=5), start=1):
    val = "".join(val)
    if "М" not in val and "Л" not in val and "ЙЙ" not in val:
        last_pos = pos

Составляем такую программу:

from itertools import product

# Алфавит из условия
alph = "ЛАЙМ"
# В алфавитном порядке
alph = sorted(alph)

# Переменная для хранения последней позиции
last_pos = 0

for pos, val in enumerate(product(alph, repeat=5), start=1):
    val = "".join(val)
    if "М" not in val and "Л" not in val and "ЙЙ" not in val:
        last_pos = pos

print(last_pos)

И в ответе получаем число 274.

Тип 2

Оставшиеся два типа заданий 8 очень похожи друг на друга. Здесь нам также даётся алфавит, содержащий в себе цифры какой-либо позиционной системы счисления или же буквы. В ответ требуется дать количество комбинаций, которые удовлетворяют заданному условию.

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

Формулировка может быть такой:

Задание 802

«Определите количество 12-ричных пятизначных чисел, в записи которых ровно одна цифра 7 и не более трёх цифр с числовым значением, превышающим 8.»

Сразу отметим, что не стоит вручную записывать все цифры 12-ричной системы счисления. Воспользуемся для этого модулем string, в котором константа printable содержит в себе все печатаемые символы: цифры от 0 до 9, строчные буквы латинского алфавита, заглавные и прочие символы, которые нас мало интересуют.

Что примечательно в этой константе, так это полное совпадение первых n символов с алфавитом n-ричной системы счисления.

Давайте убедимся в этом. Сделаем срез константы printable до 8 элемента:

import string

alph = string.printable[:8]

print(alph)

В результате получаем строку 01234567. Именно из этих символов состоит алфавит восьмеричной системы счисления.

Так что для получения всего алфавита нужной системы счисления нам достаточно сделать срез до основания этой системы.

В данном задании мы работаем с 12-ричной системой, следовательно алфавит сформируем следующим образом:

import string
from itertools import product

# Алфавит из условия
alph = string.printable[:12]

Далее переходим к написанию цикла. Поскольку у нас пятизначные числа, то параметр repeat будет принимать значение 5.

Здесь стоит сделать важное замечание. Мы должны формировать числа без незначащих (ведущих) нулей. Так что мы должны всегда при работе с числами проверять, что первая цифра не ноль: val[0] != '0'.

В условии, помимо проверки первой цифры, выполняем подсчет семёрок, которых должно быть ровно одна штука, а также считаем сумму всех цифр, больших 8. В 12-ричной системе это 9, “a” и “b”. Их сумма должна не превышать число 3.

Собираем все условия вместе и получаем такой код:

count = 0
for val in product(alph, repeat=5):
    val = "".join(val)
    if val[0] != '0' and val.count('7') == 1 and val.count('9') + val.count('a') + val.count('b') <= 3:
        count += 1

Вся же наша программа будет иметь следующий вид:

import string
from itertools import product

# Алфавит из условия
alph = string.printable[:12]

count = 0
for val in product(alph, repeat=5):
    val = "".join(val)
    if val[0] != '0' and val.count('7') == 1 and val.count('9') + val.count('a') + val.count('b') <= 3:
        count += 1

print(count) 

В качестве ответа она выводит число 67476.

Пример 2

Задание 803

«Определите количество 15-ричных пятизначных чисел, в записи которых ровно одна цифра 8 и не менее двух цифр с числовым значением, превышающим 9.»

Здесь также требуется определить количество цифр, с числовым значением, превышающим определённое число. В прошлой задаче таких цифр было всего 3 и можно было подсчет чисел расписать сразу в условии.

Теперь же цифр гораздо больше, так что давайте напишем отдельную функцию-предикат, которая будет возвращать True, когда в строке находятся не менее двух цифр с числовым значением больше 9.

# Не менее двух цифр с числовым значением, превышающим 9
def over_9(digits):
    alph_over_9 = string.printable[10:15]
    sum_of_digits = sum([1 for i in digits if i in alph_over_9])
    if sum_of_digits >= 2:
        return True
    else:
        return False

Для определения нужных цифр используем срез от 10 до 15 элемента константы printable. А такую запись для подсчёта количества цифр мы уже использовали при разборе задания 5, так что подробно на ней останавливаться не будем.

В остальном же код будет аналогичен предыдущему:

import string
from itertools import product

# Алфавит из условия
alph = string.printable[:15]


# Не менее двух цифр с числовым значением, превышающим 9
def over_9(digits):
    alph_over_9 = string.printable[10:15]
    sum_of_digits = sum([1 for i in digits if i in alph_over_9])
    if sum_of_digits >= 2:
        return True
    else:
        return False


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

print(count)

В результате работы программы получаем число 83175, что и будет ответом на это задание.

Тип 3

Как мы уже говорили ранее, второй и третий типы практически идентичны друг другу. Главное отличие в том, что теперь у нас элементы не могут повторятся в комбинации. То есть здесь будут использоваться размещения без повторений, получаемые функцией permutations().

Определить, что задание относится к третьему типу можно по фразам «все цифры различны», «буквы в коде не должны повторяться» или любой другой, которая отражает суть отсутствия повторений в комбинации.

Примером может служить такая формулировка:

Задание 804

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

Главная сложность этого задания заключается в необходимости проверить, что две чётные (или нечётные) цифры не идут друг за другом. Для этого целесообразно будет написать отдельную функцию.

Нам достаточно будет проверить, что две идущие подряд цифры имеют разную чётность. То есть при проверке одного числа на чётность возвращается True, а второго — False, или наоборот. Если чётность двух цифр совпала, то это число нам не подходит и функция возвращает False. В противном случае, возвращается True.

Функция будет выглядеть следующим образом:

def is_even_pair(digits):
    for i in range(len(digits) - 1):
        current_is_even = int(digits[i], 16) % 2 == 0
        next_is_even = int(digits[i + 1], 16) % 2 == 0
        if current_is_even == next_is_even:
            return False
    return True

Обратите внимание, что эта функция для работы с 16-ричной системой счисления! Для работы с другими системами, необходимо будет поправить перевод символа в целое число здесь: int(digits[i], 16) и int(digits[i + 1], 16).

В остальном же, решение заданий данного типа аналогично заданиям второго типа. Только здесь будем использовать функцию permutations():

import string
from itertools import permutations

# Алфавит из условия, сразу исключаем 1
alph = string.printable[:16]


# Проверяем, что две чётные не стоят рядом => четные с нечётными чередуются
def is_even_pair(digits):
    for i in range(len(digits) - 1):
        current_is_even = int(digits[i], 16) % 2 == 0
        next_is_even = int(digits[i + 1], 16) % 2 == 0
        if current_is_even == next_is_even:
            return False
    return True


count = 0
for val in permutations(alph, 3):
    val = "".join(val)
    if val[0] != '0' and is_even_pair(val):
        count += 1

print(count) 

Результатом работы нашей программы будет число 840.

Пример 3

Задание 805

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

Отличия в решении этого задания от прошлого в том, что мы сразу исключим цифру 1 из алфавита, а в permutations() вторым аргументом передадим число 5, так как будем работать с пятизначными числами.

Функция для определения, что никакие две чётные или две нечётные цифры не стоят рядом, будем использовать ту же самую, с незначительными изменениями.

Код решения будет такой:

from itertools import permutations

# Алфавит из условия, сразу исключаем 1
alph = '0234567'


# Проверяем, что две чётные не стоят рядом => четные с нечётными чередуются
def is_even_pair(digits):
    for i in range(len(digits) - 1):
        current_is_even = int(digits[i]) % 2 == 0
        next_is_even = int(digits[i + 1]) % 2 == 0
        if current_is_even == next_is_even:
            return False
    return True


count = 0
for val in permutations(alph, 5):
    val = "".join(val)
    if val[0] != '0' and is_even_pair(val):
        count += 1

print(count)

А ответ на это задание будет 180.