Тема 8 разбор. Кодирование данных, комбинаторика, системы счисления
![]()
|
Ещё пример задания:Р-08. Вася составляет 4-буквенные коды из букв У, Л, Е, Й. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Й и не может содержать сочетания ЕУ. Сколько различных кодов может составить Вася? Решение: проще всего сначала найти общее количество возможных слов, а затем вычесть из него количество слов, в которых есть сочетание ЕУ первой буквой не может быть Й, поэтому осталось только 3 возможных первых буквы предположим, что первую букву выбрали, тогда вторую выбираем из оставшихся трёх при выборе третьей буквы у нас только 2 варианта, а последняя буква – та, которая осталась последней невыбранной:
в итоге общее количество возможных слов равно 3 3 2 1 = 18 теперь определим, сколько слов содержат сочетание ЕУ; нужно рассмотреть все возможные позиции, где может стоять пара ЕУ пусть слово начинается с ЕУ, тогда следующую букву можно выбрать двумя способами, а последнюю – только одним, так что количество вариантов равно 2:
пусть пара ЕУ – это вторая и третья буквы; тогда на первом месте может стоять только буква Л (но не Й), а на последнем – Й, получаем еще один вариант:
сдвиг пары ЕУ в конец слова даёт ещё одну комбинацию
таким образом, из 18 слов четыре (2 + 1 + 1) содержат ЕУ Ответ: 14. Решение (с помощью программы, С.С. Поляков): для построения множества всевозможных слов можно использовать функцию 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) Ответ: 14. Решение (с помощью программы, Б.С. Михлин): Можно использовать перебор всех вариантов во вложенном цикле. Когда слово построено, проверяем, подходит ли оно по условию. 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) Ответ: 14. Ещё пример задания:Р-07. Вася составляет 3-буквенные слова, в которых есть только буквы В, Е, С, Н , А, причём буква А используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася? Решение (способ 1): буква А может стоять на одном из трёх мест: А**, *А*, **А, где * обозначает любой из пяти символов в каждом случае в остальных двух позициях может быть любая из пяти букв для шаблона А** получаем (перемножая количество вариантов для каждой позиции) 1 · 5 · 5 = 25 слов для шаблона *А* тоже получим 25 слов, но нужно учесть, что все слова, в который первая буква А мы уже подсчитали, поэтому считаем только слова, где на первом место стоит какая-то другая буква (В, Е, С или Н) отсюда находим, что шаблон *А* добавляет 4 · 1 · 5 = 20 новых слов рассматривая шаблон **А, не учитываем уже подсчитанные слова, в которых буква А есть на первом или втором местах, количество новых слов – 4 · 4 · 1 = 16 всего получается 25 + 20 + 16 = 61 слово Ответ: 61. Решение (способ 2): количество слов с буквой А можно вычислить как разность между количеством всех возможных слов и количеством слов, в которых нет буквы А количество всех слов 5 · 5 · 5 = 53 = 125 (на любой из 3-х позиций может стоять любая из 5 букв) количество слов, в которых нет буквы А равно 4 · 4 · 4 = 43 = 64 (на любой из 3-х позиций может стоять любая из 4 букв, кроме А) получается 125 – 64 = 61 слово, в котором есть буква А (она или несколько) Ответ: 61. Решение (с помощью программы, С.С. Поляков): для построения множества всевозможных слов можно использовать функцию 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) Ответ: 61. Решение (с помощью программы, Б.С. Михлин): можно использовать «метод грубой силы» – перебор всех вариантов: 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) Ответ: 61. |