informatikstr.ru

Решение задач по комбинаторике на примере заданий №8 из ЕГЭ по информатик. В качестве языка программирования — язык Python 3

Все задания так или иначе связанны с комбинаторикой — перестановками, количеством вариантов выборки и т.д. Для решения заданий такого типа чаще всего используется модуль itertools языка python.
Модуль itertools – это Python-модуль, который предоставляет набор функций для работы с итерируемыми объектами. Итерируемый объект  —  это любой объект, предоставляющий возможность пройти по своим элементам, например список, кортеж и словарь. Itertools позволяет выполнять стандартные операции с итерируемыми объектами, такие как фильтрация, группировка и объединение.
Модуль Itertools предоставляет несколько функций, позволяющих манипулировать итерируемыми объектами. Рассмотрим подробнее наиболее полезные функции itertools.
В данный момент имеется всего четыре функции-итератора, позволяющие комбинировать различные значения, меняя местами их составляющие. К их числу относятся такие методы как:
combinations — эта функция возвращает все возможные комбинации элементов в итерируемом объекте, не повторяя в итераторе ни одной из комбинаций. Если указан опциональный аргумент r, будут возвращены только комбинации длины r.
combinations_with_replacement;
permutations — эта функция возвращает все возможные перестановки итерируемого объекта с уникальным расположением элементов в итераторе.
product — эта функция возвращает декартово произведение итерируемых объектов. Получаемый итератор содержит кортежи, каждый из которых формируется путем отбора по одному элементу из каждого итерируемого объекта. Если указан опциональный аргумент repeat, то входные итерируемые объекты повторяются указанное количество раз.
Для импорта необходимых функции необходимо из itertools их импортировать из модуля, например так:

from itertools import product
если нужно импортировать все, то вместо product пишем *.
for i in product(‘галактика’, repeat = 8):
repeat = 8 — длинна последовательности
‘галактика’ — элементы из которых будут составлены кортежи.

Настя составляет 6-буквенные коды из букв Н, А, С, Т, Я. Каждая допустимая гласная буква может входить в код не более одного раза. Сколько кодов может составить Настя?

from itertools import *
k = 0
for p in product ('НАСТЯ',repeat=6):
    s=''.join(p)
    if s.count('А') <= 1 and s.count('Я') <= 1:
        k+=1
print(k)

Светлана составляет коды из букв своего имени. Код должен состоять из 8 букв, и каждая буква в нём должна встречаться столько же раз, сколько в имени Светлана. Кроме того, одинаковые буквы в коде не должны стоять рядом. Сколько кодов может составить Cветлана?

print('informatikstr.ru')
from itertools import *
words=[]
k = 0
for p in product ('СВЕТЛАНА',repeat=8):
    s =''.join(p)
    if s.count('А') == 2 and s.count('С') == 1 and s.count('В') == 1 and s.count('Е') == 1 and s.count('Т') == 1 and s.count('Л') == 1 and s.count('Н') == 1 and s.find('АА') == -1:
       k += 1
       if s not in words:
           words.append(s)
print(len(words))

Георгий составляет коды из букв своего имени. Код должен состоять из 7 букв, и каждая буква в нём должна встречаться столько же раз, сколько в имени Георгий. Кроме того, одинаковые буквы в коде не должны стоять рядом. Сколько кодов может составить Георгий?

print('informatikstr.ru')
from itertools import *
words=[]
k = 0
for p in product ('ГЕОРГИЙ',repeat=7):
    s =''.join(p)
    if s.count('Г') == 2 and s.count('Е') == 1 and s.count('О') == 1 and s.count('Р') == 1 and s.count('И') == 1 and s.count('Й') == 1 and s.find('ГГ') == -1:
       k += 1
       if s not in words:
           words.append(s)
print(len(words))

Сколько различных трёхзначных чисел, записанных в четверичной системе счисления, в записи которых цифры слева направо в строго убывающем порядке?

print('informatikstr.ru')
count = 0
for x in '123':
    for y in '0123':
        for z in '0123':
            if x > y > z:
                print(x, y, z)
                count += 1
print('количество -',count)

Светлана составляет коды из букв слова РОСОМАХА. Код должен состоять из 8 букв, и каждая буква в нём должна встречаться столько же раз, сколько в заданном слове. Кроме того, в коде не должны стоять рядом две гласные и две согласные буквы. Сколько кодов может составить Светлана?

print('informatikstr.ru')
from itertools import *
words=[]
for p in product ('РОСОМАХА',repeat = 8):
    s =''.join(p)
    if s.count('А') == 2 and s.count('О') == 2 and s.count('Р') == 1 and s.count('С') == 1 and s.count('М') == 1 and s.count('Х') == 1 and s.find('ОА') == -1 and s.find('АО') == -1 and s.find('РС') == -1 and s.find('СР') == -1 and s.find('РМ') == -1 and s.find('МР') == -1 and s.find('РХ') == -1 and s.find('ХР') == -1 and s.find('СМ') == -1 and s.find('МС') == -1 and s.find('МХ') == -1 and s.find('ХМ') == -1 and s.find('ОО') == -1 and s.find('АА') == -1 and s.find('ХС') == -1 and s.find('СХ') == -1:
        if s not in words:
            words.append(s)
print(len(words))

Все четырёхбуквенные слова, в составе которых могут быть только буквы Л, Е, М, У, Р, записаны в алфавитном порядке и пронумерованы, начиная с 1. Ниже приведено начало списка.
1. ЕЕЕЕ
2. ЕЕЕЛ
3. ЕЕЕМ
4. ЕЕЕР
5. ЕЕЕУ
6. ЕЕЛЕ…..
Под каким номером в списке идёт первое слово, которое начинается с буквы Л?

bukvi = 'ЕЛМРУ'
count = 0
for a in bukvi:
    for b in bukvi:
        for c in bukvi:
            for d in bukvi:
                count +=1
                if a == 'Л' and b == 'Е' and c == 'Е' and d == 'Е':
                    print(count)

Даша составляет слова из букв слова АТТЕСТАТ. Код должен состоять из 8 букв, и каждая буква в нём должна встречаться столько же раз, сколько в заданном слове. Кроме того, в коде должны стоять рядом две гласные или две согласные буквы. Сколько различных слов может составить Даша?

summ = 0
words = []
from itertools import product
for p in product ('аттестат', repeat = 8):
    i =''.join(p)
    if (i.count('а')==2 and i.count('т')==4 and i.count('е')==1 and i.count('с') == 1) and (i.count('ае')==1 or i.count('аа')==1 or i.count('тт')>=1 or i.count('еа')==1 or i.count('ст') == 1 or i.count('тс')==1):
        if i not in words:
            words.append(i)
            summ+=1
print(summ)

Вика составляет слова, переставляя буквы в слове ВИКТОРИЯ. Сколько слов, в которых буква О не находится между букв И, может составить Вика?

from itertools import *
words=[]
for p in product ('виктория',repeat=8):
    s =''.join(p)
    if s.count('и') == 2 and s.count('в') == 1 and s.count('к') == 1 and s.count('т') == 1 and s.count('о') == 1 and s.count('р') == 1 and s.count('я') == 1:
        sl =s.split("о")
        if sl[0].count('и') != 1 and sl[1].count('и') != 1:
            if s not in words:
                words.append(s)
print(len(words))

Маша составляет слова из шести букв, в которых есть только буквы из слова ГИПЕРБОЛА, причём на первом и последнем месте не может быть гласной вообще, а на любой другой позиции она не может быть с двух сторон окружена согласными. То есть сочетание БОЛ не может встречаться в слове, а словосочетания АОЛ или БОИ может. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Маша?

from itertools import product
gl = ['и', 'е', 'о', 'а']
sgl = ['г', 'п', 'р', 'б', 'л']
p = product('гипербола', repeat = 6)
count = 0
for i in p:
    l = ''.join(i)
    count+=1
    if l[0] in gl or l[5] in gl:
        count-=1
    if l[0] not in gl and l[5] not in gl:
        if (l[1] in gl and l[2] in sgl) or (l[2] in gl and l[1] in sgl and l[3] in sgl) or (l[3] in gl and l[2] in sgl and l[4] in sgl) or (l[4] in gl and l[3] in sgl) :
            count-=1      
print(count)

Марат составляет 8-буквенные коды из букв, входящих в слов ГАЛАКТИКА. Первая буква кода должна быть согласной, а последняя — гласной. Код НЕ должен содержать ни одной пары соседних букв, которые следуют друг за другом русском алфавите в том же порядке (например, «АБ» или «ЮЯ»). Сколько различных кодов может составить Марат?

from itertools import product
gl=["а","и"]
count = 0
for i in set(product('галактика', repeat = 8)):
    l = ''.join(i)
    if l[0] not in gl and l[7] in gl and l.find('кл')==-1:
        count+=1
print(count)