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

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

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

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

Задача 1#7284

Мария составляет пары слов. Первое 4-буквенное слово состоит из букв Д, Р, У, Г, а второе 4-буквенное из букв В, Р, А, Г. Каждая из букв слов может встречаться в них любое количество раз или не встречаться совсем. Сколько различных пар слов может составить Мария?

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

В первом слове на каждое из 4 мест в слове можно поставить любую из 4 различных букв. Значит первое слово можно составить 4 ⋅ 4 ⋅ 4 ⋅ 4 = 256  способами. Во втором слове на каждое из 4 мест в слове можно поставить любую из 4 различных букв. Значит второе слово можно составить 4 ⋅ 4 ⋅ 4 ⋅ 4 = 256  способами.

Представим, что первые слова — чашки, а вторые слова — блюдца. Сколько различных вариаций кружка+чашка можно составить?

Можно составить 256 ⋅ 256 = 65536  различных пар слов (блюдец с чашкой).
Решение кодом через циклы:

Для решения задачи с помощью циклов создаём вложенные циклы для каждой позиции первого слова (четыре цикла, по одной букве из набора Д, Р, У, Г). Каждая комбинация формируется и присваивается переменной w1.

Для второго слова используем четыре вложенных цикла (по одной букве из набора В, Р, А, Г). Каждая комбинация второго слова формируется и присваивается переменной w2.

После формирования первого и второго слова объединяем их в пару и добавляем во множество ans, чтобы хранить только уникальные пары. В конце программы выводим количество элементов множества, что соответствует числу всех уникальных пар слов.

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

# набор букв для первого слова
alf1 = ’ДРУГ’

# набор букв для второго слова
alf2 = ’ВРАГ’

# перебор всех букв для первой позиции первого слова
for x1 in alf1:
    # перебор всех букв для второй позиции первого слова
    for x2 in alf1:
        # перебор всех букв для третьей позиции первого слова
        for x3 in alf1:
            # перебор всех букв для четвертой позиции первого слова
            for x4 in alf1:
                # формируем первое слово
                w1 = x1 + x2 + x3 + x4
                # перебор всех букв для первой позиции второго слова
                for y1 in alf2:
                    # перебор всех букв для второй позиции второго слова
                    for y2 in alf2:
                        # перебор всех букв для третьей позиции второго слова
                        for y3 in alf2:
                            # перебор всех букв для четвертой позиции второго слова
                            for y4 in alf2:
                                # формируем второе слово
                                w2 = y1 + y2 + y3 + y4
                                # добавляем пару слов во множество
                                ans.add((w1, w2))
# выводим количество уникальных пар слов
print(len(ans))

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

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

Каждое полученное сочетание первого и второго слова объединяем в пару и добавляем во множество ans. В конце программы выводим количество элементов множества, что соответствует числу всех уникальных пар слов.

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

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

# набор букв для первого слова
alf1 = ’ДРУГ’

# набор букв для второго слова
alf2 = ’ВРАГ’

# перебираем все комбинации длиной 4 для первого слова
for x in product(alf1, repeat=4):
    # перебираем все комбинации длиной 4 для второго слова
    for y in product(alf2, repeat=4):
        # добавляем пару слов во множество
        ans.add((x, y))
# выводим количество уникальных пар слов
print(len(ans))

Ответ: 65536

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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