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

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

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

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

Задача 1#7280

Борис составляет 5-буквенные слова из букв Ш, А, Л, Ы, К. Каждая из букв может встречаться в слове любое количество раз или не встречаться совсем, причём первой буквой не может быть гласная. Сколько различных слов может составить Борис?

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

Первой буквой Борис может поставить любую из букв, кроме гласных А и Ы, т.е. одну из 3 букв Ш, Л, К. На остальные 4 места Борис ставит любую из 5 букв. Всего Борис может составить 3 ⋅ 5 ⋅ 5 ⋅ 5 ⋅ 5 = 1875  различных слов.
Решение кодом через циклы:

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

После формирования слова проверяем условие: первая буква не является гласной. Если условие выполнено, добавляем слово в множество ans, чтобы автоматически исключить дубликаты.

# создаем пустое множество для хранения уникальных слов
ans = set()

# набор букв для формирования слов
alf = ’ШАЛЫК’

# первая буква
for x1 in alf:
    # вторая буква
    for x2 in alf:
        # третья буква
        for x3 in alf:
            # четвертая буква
            for x4 in alf:
                # пятая буква
                for x5 in alf:
                    # формируем слово
                    w = x1 + x2 + x3 + x4 + x5
                    # проверяем, что первая буква не гласная (А или Ы)
                    if x1 not in ’АЫ’:
                        # добавляем слово во множество
                        ans.add(w)
# выводим количество допустимых слов
print(len(ans))

Решение кодом через itertools:

Более удобный способ — использовать модуль itertools и функцию product. Она генерирует все возможные комбинации с повторениями заданной длины из букв алфавита. Так как буквы могут повторяться, это именно то, что нам нужно.

После генерации комбинации проверяем только условие: первая буква не гласная. Если условие выполнено, добавляем комбинацию в множество ans.

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

# создаем множество для хранения слов
ans = set()

# исходный набор букв
alf = ’ШАЛЫК’

# перебираем все комбинации длиной 5 с повторениями
for x in product(alf, repeat=5):
    # проверяем, что первая буква не гласная (А или Ы)
    if x[0] not in ’АЫ’:
        # добавляем комбинацию во множество
        ans.add(x)
# выводим количество допустимых слов
print(len(ans))

Ответ: 1875

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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