Тема 8 разбор. Кодирование данных, комбинаторика, системы счисления
![]()
|
Ещё пример задания:Р-06. Вася составляет 5-буквенные слова, в которых есть только буквы С, Л, О, Н, причём буква С используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася? Решение: буква С может стоять на одном из пяти мест: С****, *С***, **С**, ***С* и ****С, где * обозначает любой из оставшихся трёх символов в каждом случае в остальных четырёх позициях может быть любая из трёх букв Л, О, Н, поэтому при заданном расположении буквы С имеем 34 = 81 вариант всего вариантов 5 · 81 = 405. Ответ: 405. Решение (с помощью программы, С.С. Поляков): для построения множества всевозможных слов можно использовать функцию product из модуля itertools; затем остаётся выбрать и пересчитать подходящие слова: from itertools import product p = product('СЛОН',repeat=5) n = 0 for x in p: if x.count('С') == 1: n += 1 print(n) Ответ: 405. Решение (с помощью программы, Б.С. Михлин): можно использовать «метод грубой силы» – перебор всех вариантов: 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) Ответ: 405. Ещё пример задания:Р-05. Сколько существует различных символьных последовательностей длины 5 в четырёхбуквенном алфавите {A, C, G, T}, которые содержат ровно две буквы A? Решение (вариант 1, перебор): рассмотрим различные варианты слов из 5 букв, которые содержат две буквы А и начинаются с А: АА*** А*А** А**А* А***А Здесь звёздочка обозначает любой символ из набора {C, G, T}, то есть один из трёх символов. итак, в каждом шаблоне есть 3 позиции, каждую из которых можно заполнить тремя способами, поэтому общее число комбинаций (для каждого шаблона!) равно 33 = 27 всего 4 шаблона, они дают 4 · 27 = 108 комбинаций теперь рассматриваем шаблоны, где первая по счёту буква А стоит на второй позиции, их всего три: *АА** *А*А* *А**А они дают 3 · 27 = 81 комбинацию два шаблона, где первая по счёту буква А стоит на третьей позиции: **АА* **А*А они дают 2 · 27 = 54 комбинации и один шаблон, где сочетание АА стоит в конце ***АА они дают 27 комбинаций всего получаем (4 + 3 + 2 + 1) · 27 = 270 комбинаций ответ: 270. Решение (вариант 2, использование формул комбинаторики): в последовательности из 5 символов нужно использовать ровно две буквы А и три символа, не совпадающих с А, которые обозначим звездочкой сначала найдём количество перестановок из двух букв А и трёх звёздочек используем формулу для вычисления числа перестановок с повторениями; для двух разных символов она выглядит так: ![]() Здесь ![]() ![]() ![]() ![]() в нашем случае ![]() ![]() ![]() теперь разберёмся со звёздочками: вместо каждой из них может стоять любой из трёх символов (кроме А), то есть на каждую из 10 перестановок мы имеем 33 = 27 вариантов распределения остальных символов на месте звёздочек таким образом, получаем всего 10 · 27 = 270 вариантов. ответ: 270. Решение (с помощью программы, С.С. Поляков): для построения множества всевозможных слов можно использовать функцию 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) Ответ: 270. Решение (с помощью программы, Б.С. Михлин): можно использовать «метод грубой силы» – перебор всех вариантов: 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) Ответ: 270. |