Решение комбинаторных задач на примере задания №8 из ЕГЭ по информатике на языке Python

Решение комбинаторных задач на примере задания №8 из ЕГЭ по информатикеⁱ

ПРОИЗВЕДЕНИЕ

1. Сколько слов длины 4, начинающихся с согласной буквы, можно составить из букв Л, Е, Т, О? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка. (128)

k=0

for a in 'ЛТ':

for b in 'ЛЕТО':

for c in 'ЛЕТО':

for d in 'ЛЕТО':

s=a+b+c+d

k+=1

print(k)

Модуль itertools – сборник различных операторов, которые позволяют строить разные последовательности.

Функция product (*iterables, repeat =1) – берем на вход список итерируемых объектов и задаем количество повторений

from itertools import product

for x in product ( 'ЛТ','ЛЕТО','ЛЕТО','ЛЕТО' ):

print(x) (будет кортеж, плохо!!! Надо строчку)

функция .join – склеивает в строку получившийся кортеж

from itertools import product

k=0

for x in product ( 'ЛТ','ЛЕТО','ЛЕТО','ЛЕТО' ):

s=''.join (x)

k+=1

print(k)

from itertools import product

k=0

for x in product ( 'ЛЕТО', repeat=4):

s=''.join(x)

if s[0] in 'ЛТ':

k+=1

print(k)

1. Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв К, У, М, А? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка. (256)

from itertools import product

k=0

for x in product('ЛМ', 'КУМА', 'КУМА','КУМА','УА'):

s=''.join(x)

k+=1

print(k)

1. Алексей составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Алексей использует 5-буквенные слова, в которых есть только буквы A, B, C, X, причём буква X может появиться на последнем месте или не появиться вовсе. Сколько различных кодовых слов может использовать Алексей? (324)

from itertools import product

k=0

for x in product ('ABC','ABC','ABC','ABC','ABCX'):

s=''.join(x)

k+=1

print (k)

1. Иван составляет 5-буквенные слова из букв А, Б, В, Г, Д, Э, Ю, Я. Первой и последней буквами этого слова могут быть только буквы Э, Ю или Я, на остальных позициях эти буквы не встречаются. Сколько различных кодовых слов может составить Иван? (576)

from itertools import product

k=0

for x in product('ЭЮЯ','АБВГ','АБВГ','АБВГ','ЭЮЯ'):

s=''.join(x)

k+=1

print(k)

1. Вася составляет 6-буквенные слова, в которых есть только буквы К, Р, О, Т, причём буква О используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася? (1458)

Функция s.count('s1') считает количество вхождений подстроки s1 в строку s

from itertools import product

k=0

for x in product ('КРОТ', repeat =6):

s = ''.join(x)

if s.count('О')==1:

k+=1

print(k)

1. Вася составляет 6-буквенные слова, в которых есть только буквы К, А, Н, Т, причём буква К используется в каждом слове ровно 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася? (1215)

from itertools import product

k=0

for x in product ('КАНТ', repeat = 6):

s=''.join(x)

if s.count('К')==2:

k+=1

print (k)

1. Маша составляет 6-буквенные слова из букв З, Е, Р, К, А, Л, О, содержащие одну букву К и три буквы А. Каждая из других допустимых букв встречается в слове любое количество раз или не встречается совсем. Сколько различных слов может составить Маша? (1500)

from itertools import product

k=0

for x in product ('ЗЕРКАЛО', repeat = 6):

s=''.join(x)

if s.count('К')==1 and s.count('А')==3:

k+=1

print(k)

1. Леся составляет слова из букв А, Н, И, М, Е. Слово может иметь длину от 4 до 6 букв. Сколько слов может составить Леся? (19375)

from itertools import product

k=0

for x in product ('АНИМЕ', repeat = 4):

s=''.join(x)

k+=1

for x in product ('АНИМЕ', repeat = 5):

s=''.join(x)

k+=1

for x in product ('АНИМЕ', repeat = 6):

s=''.join(x)

k+=1

print(k)

1. Вася составляет 4-буквенные слова, в которых есть только буквы Л, Е, Т, О, причём буква Е используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем.
   Сколько существует таких слов, которые может написать Вася? (175)

1. Вася составляет 3-буквенные слова, в которых есть только буквы К, Р, А, Н, причём буква А используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася? ()

from itertools import product

k=0

for x in product ('КРАН', repeat = 3):

s=''.join(x)

if s.count (‘A’)=1

k+=1

print(k)

1. Вася составляет 3-буквенные слова, в которых есть только буквы К, А, Т, Е, Р, причём буква Р используется в каждом слове хотя бы 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася? (13)

from itertools import product

k=0

for x in product ('КАТЕР', repeat = 3):

s=''.join(x)

if s.count ('Р')=2:

k+=1

print(k)

1. Василий составляет 4 буквенные коды из букв Б, Е, Р, К, Л, И, Й. Каждую букву можно использовать любое количество раз, при этом код не может начинаться с буквы Й и должен содержать хотя бы одну гласную. (1558)

S[0] – обращение к первому символу строки

S[-1] – обращение к последнему символу строки

‘E’ in S – Е находится в S

from itertools import product

k=0

for x in product ('БЕРКЛИЙ', repeat = 4):

s=''.join(x)

##if s[0] != 'Й' and (s.count ('Е')=1 or s.count ('И')=1): ИЛИ

if s[0] != 'Й' and ('Е' in s or 'И' in s):

k+=1

print(k)

1. Ученица составляет пятибуквенные слова из букв Ж, И, Р, А, Ф. При этом в каждом слове одна буква Ж, слово не может начинаться на букву Ф и заканчиваться буквой Р. Какое количество слов может составить ученица? (816)

from itertools import product

k=0

for x in product ('ЖИРАФ', repeat = 5):

s=''.join(x)

if s[0] != 'Ф' and s[-1] != 'Р' and s.count('Ж')==1:

k+=1

print(k)

ПЕРЕСТАНОВКИ

В перестановка буквы не должны повторяться, а значит функция product не подходит.

Permutations (iterable, r = None) - перестановка длинной r из iterable, по умолчанию длина совпадает с исходной длиной. (Перестановки не уникальны!!!!)

Чтобы удалить повторения, нужно сначала преобразовать к множеству (set), а затем преобразовать в список list.

1. Вася составляет 5-буквенные коды из букв К, А, Л, И, Й. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Й и не может содержать сочетания ИА. Сколько различных кодов может составить Вася? (78)

from itertools import*

k=0

for x in permutations ('КАЛИЙ'):

s =''.join(x)

if s[0]!='Й' and 'ИА' not in s:

k+=1

print(k)

1. Петя составляет 5-буквенные слова из букв К, О, Л, У, Н. Каждую букву нужно использовать ровно 1 раз, при этом код при этом нельзя ставить подряд две гласные или две согласные. Сколько различных кодов может составить Петя?(12)

.replace – заменяет в строке одну подстроку на другую.

from itertools import*

k=0

for x in permutations ('КОЛУН'):

s =''.join(x)

s = s.replace('Л','К').replace('Н','К').replace('У','О')

if 'КК' not in s and 'ОО' not in s:

k+=1

print(k)

1. Маша составляет 7-буквенные коды из букв П, Е, С, К, А, Р, Ь. Каждую букву нужно использовать ровно 1 раз, при этом код буква Ь не может стоять на первом месте, а также перед буквами Е, А и Р. Сколько различных кодов может составить Маша? (2520)

from itertools import*

k=0

for x in permutations ('ПЕСКАРЬ'):

s =''.join(x)

if s[0]!='Ь' and 'ЬЕ' not in s and 'ЬА' not in s and 'ЬР' not in s:

k+=1

print(k)

1. Петя составляет семибуквенные слова перестановкой букв слова АССАСИН. Сколько всего различных слов может составить Петя? (420)

Множество в python - "контейнер", содержащий не повторяющиеся элементы в случайном порядке.

Множества удобно использовать для удаления повторяющихся элементов:

words = ['hello', 'daddy', 'hello', 'mum']

set(words)

{'hello', 'daddy', 'mum'}

from itertools import*

k=0

for x in set(permutations ('АССАСИН')):

s =''.join(x)

k+=1

print(k)

1. Сколько существует чисел, восьмеричная запись которых содержит 6 цифр, причём все цифры различны и никакие две чётные и две нечётные цифры не стоят рядом? (1008)

from itertools import*

k=0

for x in permutations ('01234567',6):

s =''.join(x)

if s[0]!='0':

s = s.replace('2','0').replace('4','0').replace('6','0')\

.replace('3','1').replace('5', '1').replace('7','1')

if '00' not in s and '11' not in s:

k+=1

print(k)

1. Евгения составляет 4-значные числа в 8-ичной системе счисления. 
   Числа должны начинаться с чётной цифры, и цифры в них располагаются в невозрастающем порядке. Сколько различных чисел может составить Евгения? (129)

from itertools import*

k=0

for x in product('01234567',repeat = 4):

s =''.join(x)

if s[0] in '246' and s[0]=s[1]=s[2]=s[3]:

k+=1

print (k)

ПОДСЧЕТ СЛОВ

1. Все 5-бук­вен­ные слова, со­став­лен­ные из букв А, К, Р, У, за­пи­са­ны в ал­фа­вит­ном по­ряд­ке. Вот на­ча­ло спис­ка:
   1. ААААА
   2. ААААК
   3. ААААР
   4. ААААУ
   5. АААКА
   ……
   За­пи­ши­те слово, ко­то­рое стоит на 150-м месте от на­ча­ла спис­ка. (АРККК)

from itertools import*

k=0

for x in product(sorted('АКРУ'), repeat = 5):

s=''.join(x)

k+=1

if k==150:

print (k,s)

1. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……
Укажите номер слова УАУАУ. (183)

from itertools import*

k=0

for x in product(sorted('АОУ'), repeat = 5):

s=''.join(x)

k+=1

if s=='УАУАУ':

print (k,s)

1. Все шестибуквенные слова, составленные из букв МАНГУСТ, записаны в алфавитном порядке и пронумерованы.

Вот начало списка:

1. АААААА

2. АААААГ

3. АААААМ

4. АААААН

5. АААААС

6. АААААТ

7. АААААУ ...

Под каким номером в списке стоит последнее слово, которое не начинается с буквы У, содержит только две буквы М и не более одной буквы Г? (100810)

from itertools import*

k=0

last=0

for x in product(sorted('МАНГУСТ'), repeat = 6):

s=''.join(x)

k+=1

if s[0]!='У' and s.count('М')==2 and s.count('Г')

last=k

print (last)

1. Все пятибуквенные слова, составленные из букв К, О, М, П, Ь, Ю, Т, Е, Р, записаны в алфавитном порядке и пронумерованы.

Вот начало списка:

1. ЕЕЕЕЕ

2. ЕЕЕЕК

3. ЕЕЕЕМ

4. ЕЕЕЕО

5. ЕЕЕЕП

6. ЕЕЕЕР

7. ЕЕЕЕТ

8. ЕЕЕЕЬ

Сколько слов с нечетным номером, которые не начинаются с буквы Ь и содержит ровно две буква К? (2420)

from itertools import*

k=0

h=0

for x in product(sorted('КОМПЬЮТЕР'), repeat = 5):

s=''.join(x)

k+=1

if k%2!=0 and s[0]!='Ь' and s.count('К')==2:

h+=1

print (h)

i^ За основу взяты материалы с сайта КЕГЭ