Тема 8. Комбинаторика

8.02 Подсчет количества слов/чисел

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела комбинаторика
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#85469

Вениамин составляет семибуквенные слова из букв своего имени, следуя правилам: каждая буква может встречаться любое количество раз, в слове должна быть последовательность из трёх одинаковых символов, попарно разделенных любыми другими символами. (Например в слове ВЕВИВМН три буквы В разделены буквами Е и И). Сколько различных слов может составить Вениамин?

Показать ответ и решение

Идея решения через itertools:

Мы хотим найти все семибуквенные слова из букв имени "ВЕНИАМИН которые содержат последовательность из трёх одинаковых символов, разделённых любыми другими символами. Для этого используем генерацию всех возможных комбинаций букв и проверку каждого слова на наличие требуемой последовательности.

1. Задаём множество букв имени "ВЕНИАМИН". Это позволяет исключить повторяющиеся буквы и сгенерировать все комбинации только из уникальных букв.

2. Генерируем все семибуквенные слова с помощью функции product(s, repeat=7):

     - Каждый результат product возвращает кортеж из 7 букв.

     - Преобразуем кортеж в строку методом join для удобной проверки последовательностей.

3. Проверяем наличие требуемой последовательности трёх одинаковых букв:

     - Перебираем индексы k = 0, 1, 2, чтобы проверить все возможные позиции для трёх одинаковых букв, разделённых двумя другими символами.

     - Условие проверки:

     * буквы на позициях k, k+2 и k+4 должны быть одинаковыми;

     * буквы на позициях k+1 и k+3 не должны совпадать с выбранной буквой последовательности.

     - Если условие выполнено, добавляем слово в множество для учёта только уникальных слов.

4. После перебора всех комбинаций выводим количество элементов в множестве, что даёт ответ задачи.

Решение через itertools:

from itertools import product # Импортируем функцию product для генерации комбинаций

s = set("ВЕНИАМИН") # Множество уникальных букв имени
ot = set() # Множество для хранения уникальных слов, удовлетворяющих условию

# Генерация всех 7-буквенных слов
for i in product(s, repeat=7):
    word = "".join(i) # Преобразуем кортеж букв в строку слова
    # Проверяем все возможные позиции для трёх одинаковых букв, разделённых двумя другими символами
    for k in range(3):
        if word[k] == word[k + 2] == word[k + 4] and word[k + 1] != word[k] and word[k + 3] != word[k]:
            ot.add(word) # Добавляем слово в множество уникальных слов
print(len(ot)) # Выводим количество уникальных слов, удовлетворяющих условию

Ответ: 15120

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!