Тема 8 разбор. Кодирование данных, комбинаторика, системы счисления

• Название: Кодирование данных, комбинаторика, системы счисления
• Анкор: Тема 8 разбор
• Дата: 08.04.2023
• Размер: 327 Kb.
• Имя файла: ege8 (1).doc
• Тип: Документы; #1047035
• страница: 2 из 10

Пример задания:

Р-10. Маша составляет шестибуквенные слова перестановкой букв слова КАПКАН. При этом она избегает слов с двумя подряд одинаковыми буквами. Сколько различных кодов может составить Маша?

Решение:

1. 
   если не учитывать, что в слове есть одинаковые буквы, общее количество перестановок 6 букв равно 6! = 720
   
2. 
   так как перестановка пары одинаковых букв не даёт нового слова, каждая пара уменьшает количество уникальных слов в 2 раза; а у нас 2 пары (повторяются К и А), поэтому количество уникальных слов – в 4 раза меньше, оно равно 720/4 = 180
   
3. 
   теперь из 180 нужно вычесть количество слов, где встречаются пары КК и АА;
   
4. 
   сначала найдём количество слов, в которых встречаются обе пары, и КК, и АА; обозначим X=КК, Y=АА, таким образом, нужно найти количество слов из 4-х разных «букв» (Н, П, Х, Y), это количество равно 4! = 24
   
5. 
   теперь подсчитаем слова, в которых есть X=КК, но нет АА; получаем набор из 5 «букв» (А, A, Н, П, Х), количество уникальных слов равно 5!/2 = 60 (учитывая, что перестановка букв А не меняет слово); кроме того, среди них есть еще 24 слова, в которых есть обе пары, то есть имеем 60 – 24 = 36 слов, где есть КК, но нет АА
   
6. 
   аналогично получаем, что есть 36 слов, где есть АА, но нет КК
   
7. 
   количество нужных нам слов равно 180 – 24 – 36 – 36 = 84.
   
8. 
   Ответ: 84.
   

Решение (с помощью программы, Б.С. Михлин):

1. 
   Использование функции permutations (перестановки) модуля itertools и генератора множества.
   

def ok(x):

for i in range(5):

if x[i]==x[i+1]: # соседние буквы д.б. разными

return False

else:

return True
from itertools import permutations

s = 'капкан'

# множество удаляет повторяющиеся перестановки

# (из-за двух 'а' и двух 'к' в s)

m = { x for x in permutations(s) if ok(x) }

print(len(m))

2. 
   Можно обойтись и без функции (Д. Баянов):
   

from itertools import permutations

s = 'капкан'

m = { x for x in permutations(s)

if x[0] != x[1] and x[1] != x[2] and x[2] != x[3] and

x[3] != x[4] and x[4] != x[5] }

print(len(m))

3. 
   Ответ: 84.
   

Ещё пример задания:

Р-09. Маша составляет 5-буквенные коды из букв В, У, А, Л, Ь. Каждую букву нужно использовать ровно 1 раз, при этом код буква Ь не может стоять на первом месте и перед гласной. Сколько различных кодов может составить Маша?

Решение:

1. 
   проще всего сначала найти общее количество возможных слов, а затем вычесть из него количество «запрещённых» слов – тех, которые начинаются на букву Ь или содержат комбинации ЬУ и ЬА
   
2. 
   сначала найдём общее количество слов, не накладывая никаких ограничений; при этом есть 5 способов выбрать первую букву, 4 способа выбрать вторую и т.д., так что общее число вариантов равно 5! = 5  4  3  2  1 = 120
   
3. 
   первой буквой не может быть Ь, это исключает 1  4  3  2  1 = 24 варианта
   
4. 
   теперь определим, сколько слов содержит запрещённую комбинацию символов ЬУ; эта комбинация может располагаться на одной из 4-х позиций:
   

ЬУ***, *ЬУ**, **ЬУ*, ***ЬУ

первый случай уже исключён (слово не может начинаться с буквы Ь), для каждого из остальных случаев количество вариантов распределения остальных букв равно 3  2  1 = 6 варианта, то есть запрет сочетания ЬУ исключает 3  3  2  1 = 18 кодов

5. 
   аналогично запрет сочетания ЬА исключает ещё 18 кодов
   
6. 
   таким образом, из 120 слов запрещёнными являются 24 варианта с первой буквой Ь, 18 варианта, содержащие ЬУ в середине слова, и 18 вариантов, содержащие ЬА в середине слова
   
7. 
   остаётся 120 – 24 – 18 – 18 = 60 кодов
   
8. 
   Ответ: 60.
   

Решение (с помощью программы, С.С. Поляков):

1. 
   для построения множества всевозможных слов можно использовать функцию product из модуля itertools; затем остаётся выбрать и пересчитать подходящие слова:
   

from itertools import product

p = product('ВУАЛЬ',repeat=5)

s = map(lambda x: ''.join(x), p)

n = 0

for x in s:

if ((x.count('В')==1) and (x.count('У')==1) and

(x.count('А')==1) and (x.count('Л')==1) and

(x.count('Ь')==1)) and

(x[0] != 'Ь') and (x.find('ЬУ')==-1 and

x.find('ЬА')==-1):

n += 1

print(n)

2. 
   Ответ: 60.
   

Решение (с помощью программы, Б.С. Михлин):

4. 
   Можно использовать перебор всех вариантов во вложенном цикле. Когда слово построено, проверяем, подходит ли оно по условию.
   

n=0

s='вуаль'

for a in s[:4]: # s без 'ь'

for b in s:

for c in s:

for d in s:

for e in s:

st=a+b+c+d+e # полученный 5-буквенный код

for x in s:

if st.count(x)!=1:

break

else: # все символы встретились ровно один раз

if st.count('ьу')==0 and st.count('ьа')==0:

n+=1

print(n)

5. 
   Ответ: 60.