Разбирал со своими учениками очередной ЕГЭ тест и наткнулся на задачу, с помощью которой можно потренировать как аналитические способности алгоритмического мышления, так и навыки программирования с помощью численного решения. А ещё по ходу дела вспомнить математическую статистику и логику. Готовы? Тогда приятного чтения...
А пока попрошу подписаться на мой канал в telegram IT mentor . Краткие заметки и наблюдения по физике, математике, программированию, железу и технике 💡
Задача
Матвей составляет 6-буквенные коды из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Й и не может содержать сочетания АЕ. Сколько различных кодов может составить Матвей?
Решение:
Задачу можно решить двумя способами. Сложно сказать какой из них будет легче. На мой взгляд, аналитическое решение можно выполнить также быстро, как и написать алгоритм брутфорса (перебора всех решений) для этой задачи.
Мы конечно же рассмотрим с вами оба варианта.
Аналитическое решение
Принцип будем использовать следующий. Найдем общее количество слов из данного алфавита, а затем вычтем из него количества всех слов, которые будут удовлетворять описанным условиям. Получим ответ.
1. Количество всех слов, полученных из букв М, А, Т, В, Е, Й с учетом того, что каждую букву можем использовать один раз, совпадает с числом перестановок из n элементов, где n = 6. Такое число перестановок P(n) = n! = 6!
2. Число вариантов слов с буквой Й на первом месте равно числу перестановок оставшихся пяти букв:
3. Количество слов, в которых есть сочетания АЕ найдем через схему, описывающую все варианты: АЕ может быть на 1-м и 2-м месте, на 2-м и 3-м месте, на 3-м и 4-месте, на 4-м и 5-м месте, на 5-м и 6-м месте. Всего 5 схем:
Когда АЕ стоит в начале, то в оставшихся буквах мы можем использовать букву Й, поэтому в этом случае имеем 4! слов. В остальных четырех вариантов, когда АЕ стоит со 2-го по 5-ю позицию, у нас накладываются ограничения на первую букву, но не накладываются ограничения на последующие. Поэтому в каждой из таких схем 3·3! варианта. Всего имеем 4! + 4·3·3! = 4·4! слов с АЕ.
В конечном результате получаем 504 слова, удовлетворяющих заданным условиям:
Численное решение
Теперь попробуем закодить решение. Будем использовать Python. Для более быстрого решения нам понадобится модуль itertools. Данный модуль позволяет работать с итерируемыми объектами. Итерируемый объект — это любой объект, предоставляющий возможность пройти по своим элементам, например список, кортеж и словарь, строка символов.
Из данного модуля нам понадобится функция permutations. Или более подробно: itertools.permutations(iterable, r = None)
Что делает itertools.permutations(iterable, r = None):
◼ Возвращает последовательные перестановки элементов из итерационной таблицы длиной r.
◼ Если значение r не указано или равно None, то значение r по умолчанию равно длине итерационной структуры, и генерируются все возможные полноразмерные перестановки.
◼ Результатом является подпоследовательность product(), в которой были отфильтрованы записи с повторяющимися элементами. Длина выходных данных определяется функцией math.perm(), которая вычисляет n! / (n - r)! когда 0 ≤ r ≤ n или ноль, когда r > n. Обратите внимание, что если r = n, то получается как раз число перестановок P(n) = n!
Если кому-то интересен код реализации из документации, то вот:
* permutations переводится как перестановки
Теперь мы можем реализовать нашу брутфорс-программу, используя одну сложную библиотечную функцию, возвращающую нам список из кортежей переставленных символов, из которых состоит исходное (входное) слово.
Если Вам нужен репетитор по физике, математике или информатике/программированию, Вы можете написать мне или в мою группу Репетитор IT mentor в VK
Библиотека с книгами для физиков, математиков и программистов Репетитор IT mentor в VK
Репетитор IT mentor в telegram