Задание №8 ЕГЭ информатика: подсчёт количества кодов, Python

Задание №8 ЕГЭ по информатике: подсчёт количества слов на Python

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

1. Условие задачи

Светлана составляет коды из букв своего имени. Код должен состоять из 8 букв, и каждая буква в нём должна встречаться столько же раз, сколько в имени Светлана. Кроме того, одинаковые буквы в коде не должны стоять рядом. Сколько кодов может составить Светлана?

2. Что нужно понять перед решением

В имени Светлана восемь букв: С, В, Е, Т, Л, А, Н, А.

Обратите внимание: буква А встречается дважды, остальные — по одному разу.

Значит, в коде:

  • буква А должна быть ровно 2 раза;
  • буквы С, В, Е, Т, Л, Н — ровно по 1 разу;
  • две буквы А не должны стоять рядом.

Длина кода — 8 букв. Всё сходится: 2 + 6 = 8.

3. Решение 1: вложенные циклы

Для кода из 8 букв нужно 8 вложенных циклов. Выглядит громоздко, но работает.

s = "СВЕТЛАН"
c = 0
for x1 in s:
    for x2 in s:
        for x3 in s:
            for x4 in s:
                for x5 in s:
                    for x6 in s:
                        for x7 in s:
                            for x8 in s:
                                x = x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8
                                if (x.count("С") == 1) and (x.count("В") == 1) and (x.count("Е") == 1) and (x.count("Т") == 1) and (x.count("Л") == 1) and (x.count("А") == 2) and (x.count("Н") == 1) and (x.count("АА") == 0):
                                    c += 1
print(c)
Разбор по шагам

Шаг 1. Задаём строку с уникальными буквами имени:
s = "СВЕТЛАН"
Здесь семь букв. Восьмая буква кода — вторая А — появится сама, потому что мы разрешаем букве А повторяться при переборе.

Шаг 2. Восемь вложенных циклов перебирают все возможные комбинации из 8 букв. Всего вариантов 7⁸ = 5 764 801. Это много, но компьютер справится за пару секунд.

Шаг 3. Склеиваем слово и проверяем условие:
if (x.count("С") == 1) and (x.count("В") == 1) and ... and (x.count("А") == 2) and (x.count("АА") == 0):
    c += 1
  • x.count("С") == 1 — буква С встречается ровно один раз.
  • x.count("А") == 2 — буква А встречается ровно два раза.
  • x.count("АА") == 0 — нет двух подряд идущих А. Эквивалентно "АА" not in x.
Шаг 4. Выводим счётчик.

Ответ: 15120.

Важное замечание
Проверять «одинаковые буквы не стоят рядом» нужно только для буквы А — единственной, которая повторяется. Остальные буквы встречаются по одному разу, поэтому двух одинаковых подряд просто не может быть.
Если бы повторялись несколько букв, пришлось бы проверять каждую пару: "АА" not in x and "СС" not in x и так далее.

4. Решение 2: itertools.product

Восемь вложенных циклов — это неудобно. Гораздо короче то же самое записать через product.

from itertools import product

letters = "СВЕТЛАН"
c = 0

for tup in product(letters, repeat=8):
    x = ''.join(tup)
    if (x.count("С") == 1 and
        x.count("В") == 1 and
        x.count("Е") == 1 and
        x.count("Т") == 1 and
        x.count("Л") == 1 and
        x.count("А") == 2 and
        x.count("Н") == 1 and
        "АА" not in x):
        c += 1

print(c)
Разбор по шагам

Шаг 1. Подключаем product и задаём буквы:
from itertools import product
letters = "СВЕТЛАН"
Шаг 2. product(letters, repeat=8) создаёт все комбинации из 8 букв. Это ровно то же самое, что восемь вложенных циклов, но записано одной конструкцией.

Шаг 3. Склеиваем кортеж в строку:
x = ''.join(tup)
Без этого шага x останется кортежем, и методы строки не сработают.

Шаг 4. Проверяем условие. Обратите внимание: здесь вместо x.count("АА") == 0 используется "АА" not in x — это то же самое, но читается понятнее.

Шаг 5. Считаем количество подходящих слов в счётчике c.

Ответ: 15120.

5. Плюсы и минусы

Сравнение способов перебора
Главный плюс product — масштабируемость. Если в задаче будет код из 10 букв, писать 10 вложенных циклов просто неразумно, а product(repeat=10) — одна строка.

Главный минус — нужно не забыть ''.join(tup). Без него программа упадёт или выдаст неверный результат.

6. Что запомнить

  1. Считаем количество — заводим счётчик c = 0 и увеличиваем его при каждом подходящем слове.
  2. Проверяем количество букв через x.count("буква").
  3. Проверяем отсутствие пары через "АА" not in x или x.count("АА") == 0.
  4. Длинные слова удобнее перебирать через itertools.product.

Нужна помощь с подготовкой?

Я — Олег Алексеевич, репетитор по информатике. Готовлю к ЕГЭ более 15 лет.

На своих занятиях мы:

  • разбираем структуру экзамена и стратегии решения;
  • пишем код на Python так, чтобы он работал с первого раза;
  • отрабатываем сложные задания 26 и 27 на реальных примерах.

Хотите попробовать? Запишитесь на первое занятие — познакомимся, определим ваш уровень и составим план подготовки.

Переходите на мой сайт, чтобы узнать подробности и записаться: Репетиторы рядом

Made on
Tilda