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

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

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

Р-08. Вася составляет 4-буквенные коды из букв У, Л, Е, Й. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Й и не может содержать сочетания ЕУ. Сколько различных кодов может составить Вася?

Решение:

1. 
   проще всего сначала найти общее количество возможных слов, а затем вычесть из него количество слов, в которых есть сочетание ЕУ
   
2. 
   первой буквой не может быть Й, поэтому осталось только 3 возможных первых буквы
   
3. 
   предположим, что первую букву выбрали, тогда вторую выбираем из оставшихся трёх
   
4. 
   при выборе третьей буквы у нас только 2 варианта, а последняя буква – та, которая осталась последней невыбранной:
   

   3

   3

   2

   1

5. 
   в итоге общее количество возможных слов равно 3  3  2  1 = 18
   
6. 
   теперь определим, сколько слов содержат сочетание ЕУ; нужно рассмотреть все возможные позиции, где может стоять пара ЕУ
   
7. 
   пусть слово начинается с ЕУ, тогда следующую букву можно выбрать двумя способами, а последнюю – только одним, так что количество вариантов равно 2:
   

   1(Е)

   1(У)

   2

   1

8. 
   пусть пара ЕУ – это вторая и третья буквы; тогда на первом месте может стоять только буква Л (но не Й), а на последнем – Й, получаем еще один вариант:
   

   1(Л)

   1(Е)

   1(У)

   1(Й)

9. 
   сдвиг пары ЕУ в конец слова даёт ещё одну комбинацию
   

   1(Л)

   1(Й)

   1(Е)

   1(У)

10. 
    таким образом, из 18 слов четыре (2 + 1 + 1) содержат ЕУ
    
11. 
    Ответ: 14.
    

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

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

from itertools import product

p = product('УЛЕЙ',repeat=4)

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[0] != 'Й') and (x.find('ЕУ')==-1):

n += 1

print(n)

2. 
   Ответ: 14.
   

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

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

n=0

s='улей'

for a in s[:3]: # s без 'й'

for b in s:

for c in s:

for d in s:

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

for x in s:

if st.count(x)!=1:

break

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

if st.count('еу')==0: # 'еу' - русские буквы

n+=1

print(n)

2. 
   Ответ: 14.
   

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

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

Решение (способ 1):

1. 
   буква А может стоять на одном из трёх мест: А**, *А*, **А, где * обозначает любой из пяти символов
   
2. 
   в каждом случае в остальных двух позициях может быть любая из пяти букв
   
3. 
   для шаблона А** получаем (перемножая количество вариантов для каждой позиции)
   

1 · 5 · 5 = 25 слов

4. 
   для шаблона *А* тоже получим 25 слов, но нужно учесть, что все слова, в который первая буква А мы уже подсчитали, поэтому считаем только слова, где на первом место стоит какая-то другая буква (В, Е, С или Н)
   
5. 
   отсюда находим, что шаблон *А* добавляет 4 · 1 · 5 = 20 новых слов
   
6. 
   рассматривая шаблон **А, не учитываем уже подсчитанные слова, в которых буква А есть на первом или втором местах, количество новых слов – 4 · 4 · 1 = 16
   
7. 
   всего получается 25 + 20 + 16 = 61 слово
   
8. 
   Ответ: 61.
   

Решение (способ 2):

1. 
   количество слов с буквой А можно вычислить как разность между количеством всех возможных слов и количеством слов, в которых нет буквы А
   
2. 
   количество всех слов 5 · 5 · 5 = 5³ = 125 (на любой из 3-х позиций может стоять любая из 5 букв)
   
3. 
   количество слов, в которых нет буквы А равно 4 · 4 · 4 = 4³ = 64 (на любой из 3-х позиций может стоять любая из 4 букв, кроме А)
   
4. 
   получается 125 – 64 = 61 слово, в котором есть буква А (она или несколько)
   
5. 
   Ответ: 61.
   

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

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

from itertools import product

p = product('ВЕСНА',repeat=3)

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

n = 0

for x in s:

if (x.count('А') >= 1):

n += 1

print(n)

2. 
   Ответ: 61.
   

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

1. 
   можно использовать «метод грубой силы» – перебор всех вариантов:
   

n=0

s='весна'

for a in s:

for b in s:

for c in s:

if (a+b+c).count('а')>=1: # буква 'а' (русская) должна

# встречаться хотя бы один раз

n+=1

print(n)

2. 
   Ответ: 61.