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

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

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

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

Решение:

1. 
   буква С может стоять на одном из пяти мест: С****, *С***, **С**, ***С* и ****С, где * обозначает любой из оставшихся трёх символов
   
2. 
   в каждом случае в остальных четырёх позициях может быть любая из трёх букв Л, О, Н, поэтому при заданном расположении буквы С имеем 3⁴ = 81 вариант
   
3. 
   всего вариантов 5 · 81 = 405.
   
4. 
   Ответ: 405.
   

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

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

from itertools import product

p = product('СЛОН',repeat=5)

n = 0

for x in p:

if x.count('С') == 1:

n += 1

print(n)

2. 
   Ответ: 405.
   

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

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

n=0

s='слон'

for a in s:

for b in s:

for c in s:

for d in s:

for e in s:

if (a+b+c+d+e).count('с')==1: # буква 'c' (русская)

# должна встречаться один раз

n+=1

print(n)

2. 
   Ответ: 405.
   

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

Р-05. Сколько существует различных символьных последовательностей длины 5 в четырёхбуквенном алфавите {A, C, G, T}, которые содержат ровно две буквы A?

Решение (вариант 1, перебор):

1. 
   рассмотрим различные варианты слов из 5 букв, которые содержат две буквы А и начинаются с А:
   

АА*** А*А** А**А* А***А

Здесь звёздочка обозначает любой символ из набора {C, G, T}, то есть один из трёх символов.

2. 
   итак, в каждом шаблоне есть 3 позиции, каждую из которых можно заполнить тремя способами, поэтому общее число комбинаций (для каждого шаблона!) равно 3³ = 27
   
3. 
   всего 4 шаблона, они дают 4 · 27 = 108 комбинаций
   
4. 
   теперь рассматриваем шаблоны, где первая по счёту буква А стоит на второй позиции, их всего три:
   

*АА** *А*А* *А**А

они дают 3 · 27 = 81 комбинацию

5. 
   два шаблона, где первая по счёту буква А стоит на третьей позиции:
   

**АА* **А*А

они дают 2 · 27 = 54 комбинации

6. 
   и один шаблон, где сочетание АА стоит в конце
   

***АА

они дают 27 комбинаций

7. 
   всего получаем (4 + 3 + 2 + 1) · 27 = 270 комбинаций
   
8. 
   ответ: 270.
   

Решение (вариант 2, использование формул комбинаторики):

1. 
   в последовательности из 5 символов нужно использовать ровно две буквы А и три символа, не совпадающих с А, которые обозначим звездочкой
   
2. 
   сначала найдём количество перестановок из двух букв А и трёх звёздочек
   
3. 
   используем формулу для вычисления числа перестановок с повторениями; для двух разных символов она выглядит так:
   

Здесь – количество букв А, – количество звёздочек и восклицательный знак обозначает факториал натурального числа, то есть произведение всех натуральных чисел от 1 до :

4. 
   в нашем случае и , так что получаем
   

5. 
   теперь разберёмся со звёздочками: вместо каждой из них может стоять любой из трёх символов (кроме А), то есть на каждую из 10 перестановок мы имеем 3³ = 27 вариантов распределения остальных символов на месте звёздочек
   
6. 
   таким образом, получаем всего 10 · 27 = 270 вариантов.
   
7. 
   ответ: 270.
   

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

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

from itertools import product

p = product('ACGT',repeat=5)

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

n = 0

for x in s:

if (x.count('A') == 2):

n += 1

print(n)

2. 
   Ответ: 270.
   

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

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

n=0

s='acgt'

for a in s:

for b in s:

for c in s:

for d in s:

for e in s:

if (a+b+c+d+e).count('a')==2: # буква 'a' (латинская)

# должна встречаться два раза

n+=1

print(n)

4. 
   Ответ: 270.