В 8 задании есть целый спектр задач, где требуется из имеющихся букв составить слова, с определёнными ограничениями. В 98% случаев решать нужно через Python.
Стандартное решение через Python не будет сложным алгоритмически. Там будет стандартный алгоритм: много вложенных циклов, потом по буквам собирается слово, далее идёт проверка, а потом увеличивается счётчик.
На словах это может быть не очень понятно, поэтому рассмотрим на реальном примере.
Пример задания
Георгий составляет коды из букв своего имени. Код должен состоять из 7 букв, и каждая буква в нём должна встречаться столько же раз, сколько в имени Георгий. Кроме того, одинаковые буквы в коде не должны стоять рядом. Сколько кодов может составить Георгий?
Анализ
- Слово будет 7-буквенным
- Две буквы Г, остальных по по одной
- Две буквы Г не стоят рядом
Решение
Типовое решение
Сделаем 7 вложенных циклов и перебором будем формировать разные слова. При помощи условия ограничим подходящие комбинации.
Отдельно хочется сказать о том, как здесь работают вложенные циклы. Первый цикл (i1) зафиксирует сначала букву Г. Потом второй цикл(i2) тоже зафиксирует сначала букву Г и так далее. Первое слово, которое будет создано этими циклами это слово: «ГГГГГГГ». Второе слово, которое будет создано: «ГГГГГГЕ». Когда последний цикл (i7) переберёт все буквы, то произойдёт возврат к циклу i6, который переключится на букву «Е» и вновь запустит цикл i7. Теперь будут сформированы слова: «ГГГГГЕГ», «ГГГГГЕЕ», «ГГГГГЕО», «ГГГГГЕР», «ГГГГГЕИ», «ГГГГГЕЙ». И именно так будут перебраны все возможные комбинации составления слов.
Для каждого созданного слова выполняются проверки:
- s.count('Г') == 2 - в слове всего две буквы «Г»
- s.count('Е') == 1 - в слове только одна буква «Е»
- s.count('О') == 1 - в слове только одна буква «О»
- s.count('Р') == 1 - в слове только одна буква «Р»
- s.count('И') == 1 - в слове только одна буква «И»
- s.count('Й') == 1 - в слове только одна буква «Й»
- «ГГ» not in s - в слове две буквы «Г» не стоят рядом
Важно, что поскольку эти условия связаны логическим И (and), то для того, чтобы условие считалось верным, нужно, чтобы все эти проверки были правдой.
Если это огромное условие выполняется, то счётчик увеличивается на единицу.
Ответ: 1800
Короткое решение
Воспользуемся библиотекой itertools, которая предоставляет очень крутые функции для перебора и создания последовательностей. В данной задаче нас конкретно интересует модуль permutations.
Permutations умеет создавать список из всех возможных комбинаций букв, которые мы ему укажем. Нужно понимать, что эти комбинации - это не строка, а кортеж (кортеж - это неизменяемый список). Но это не беда, потому что всего одной командой join, мы превращаем его в привычную для нас строку
Готовое решение будет выглядеть следующим образом:
Цикл с permutations создаст все возможные комбинации из букв слова 'ГЕОРГИЙ'. То есть он почти полностью заменяет вложенные циклы из предыдущего решения. НО. Есть одно НО. Первая буква «Г» и вторая буква «Г» - будут считаться разными буквами. Поэтому количество комбинаций, которые создаст permutations будет в два раза больше чем нужно.
Можно было бы поделить итоговой результат на два, но это частный случай. В общем случае, лучше использовать set. Set - это такая коллекция, которая не может содержать дубликатов. И если в ней уже лежит слово «ГЕОРГИЙ», то при попытке добавить его второй раз - оно просто не добавится.
Команда ''.join(s) превратит кортеж s в строчку, чтобы было удобнее с ней работать.
__________________________________________________________________________________________
🎓 Хотите больше таких разборов?
Подписывайтесь на наш Telegram-канал, где мы публикуем бонусные материалы для подготовки к экзаменам и для обучения программированию, а также упрощённые варианты решений и видеоразборы! 🚀