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

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

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

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

Задача 1#7629

Друг составляет пары чисел, используя цифры от 0  до 9  . Первое число состоит из 2  цифр, а второе — из 7  . Цифры в каждом из чисел могут использоваться любое количество раз, причём второе число не содержит в себе чётных цифр. Сколько различных пар чисел друг может составить?

Примечание: в данной задаче число может начинаться с нуля.

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

В первом числе друг может на первое и второе место поставить по 10  цифр. Значит первое число можно составить 10 ⋅ 10 = 100  различными способами. Во втором числе на каждой из позиций может стоять любая из 5 нечётных цифр. Значит второе число можно составить 5 ⋅ 5 ⋅ 5 ⋅ 5 ⋅ 5 ⋅ 5 ⋅ 5 = 78125  различными способами.

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

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

Для решения задачи с помощью циклов создаём пустое множество ans, куда будем добавлять все допустимые пары чисел. Строки alf1 = ’0123456789’ и alf2 = ’13579’ содержат доступные цифры для первого и второго числа соответственно. Для первого числа используем два вложенных цикла по переменным x1 и x2, формируя число w1 = x1+x2. Для второго числа используем семь вложенных циклов по переменным y1, ..., y7, формируя число w2 = y1+y2+...+y7. Добавляем пару (w1, w2) в множество ans. После завершения перебора выводим количество элементов множества.

# Создаем множество для хранения уникальных пар чисел
ans = set()
# Цифры для первого числа
alf1 = ’0123456789’
# Цифры для второго числа (только нечётные)
alf2 = ’13579’

# Перебор всех возможных 2-значных чисел
for x1 in alf1:
    for x2 in alf1:
        w1 = x1 + x2 # Формируем первое число
        # Перебор всех возможных 7-значных чисел из нечётных цифр
        for y1 in alf2:
            for y2 in alf2:
                for y3 in alf2:
                    for y4 in alf2:
                        for y5 in alf2:
                            for y6 in alf2:
                                for y7 in alf2:
                                    w2 = y1 + y2 + y3 + y4 + y5 + y6 + y7
                                    # Добавляем пару чисел в множество
                                    ans.add((w1, w2))
# Выводим количество уникальных пар чисел
print(len(ans))

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

Используем модуль itertools и функцию product для генерации всех возможных комбинаций цифр с повторениями. Создаём пустое множество ans. Перебираем все пары чисел: для первого числа — все комбинации длины 2 из alf1, для второго числа — все комбинации длины 7 из alf2. Каждую пару добавляем в множество. После перебора выводим длину множества.

from itertools import product

# Создаем множество для хранения уникальных пар чисел
ans = set()
# Цифры для первого числа
alf1 = ’0123456789’
# Цифры для второго числа (только нечётные)
alf2 = ’13579’

# Перебираем все возможные 2-значные числа
for x in product(alf1, repeat=2):
    # Перебираем все возможные 7-значные числа из нечётных цифр
    for y in product(alf2, repeat=7):
        # Добавляем пару чисел в множество
        ans.add((x, y))

# Выводим количество уникальных пар чисел
print(len(ans))

Ответ: 7812500

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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