Тема 8 разбор. Кодирование данных, комбинаторика, системы счисления
![]()
|
Ещё пример задания:Р-04. Сколько слов длины 5, начинающихся с гласной буквы, можно составить из букв Е, Г, Э? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка. Решение: первая буква слова может быть выбрана двумя способами (Е или Э), остальные – тремя общее число различных слов равно 2*3*3*3*3 = 162 ответ: 162. Решение (через формулы, А.Н. Носкин): Дано слово длиной 5 символов типа *****, где красная звездочка – гласная буква (Е или Э), а черная буква любая из трёх заданных. Общая формула количества вариантов: N = ML, где М – мощность алфавита, а L – длина кода. Так как положение одной из букв строго регламентировано (знак умножения в зависимых событиях), то формула всех вариантов примет вид: N = M1L1 ∙ M2L2, Тогда M1 = 2 (алфавит гласных букв), а L1 = 1 (только 1 позиция в слове). M2 = 3 (алфавит всех букв), а L2 = 4 (оставшиеся 4 позиции в слове). В итоге получаем: N = 21 ∙ 34 = 2 ∙ 81 = 162. ответ: 162. Решение (с помощью программы, С.С. Поляков): для построения множества всевозможных слов можно использовать функцию 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[0] == 'Е') or (x[0] == 'Э'): n += 1 print(n) Ответ: 162. Решение (с помощью программы, Б.С. Михлин): можно использовать «метод грубой силы» – перебор всех вариантов: n=0 s='егэ' for a in 'еэ': # первая буква должна быть гласной for b in s: for c in s: for d in s: for e in s: n+=1 print(n) Ответ: 162. Ещё пример задания:Р-03. Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка: 1. КККК 2. КККЛ 3. КККР 4. КККТ …… Запишите слово, которое стоит на 67-м месте от начала списка. Решение: самый простой вариант решения этой задачи – использование систем счисления; действительно, здесь расстановка слов в алфавитном порядке равносильна расстановке по возрастанию чисел, записанных в четверичной системе счисления (основание системы счисления равно количеству используемых букв) выполним замену К0, Л1, Р2, Т3; поскольку нумерация слов начинается с единицы, а первое число КККК0000 равно 0, под номером 67 будет стоять число 66, которое нужно перевести в четверичную систему: 66 = 10024 Выполнив обратную замену (цифр на буквы), получаем слово ЛККР. Ответ: ЛККР. Решение (с помощью программы, А.Н. Носкин): на компьютерном ЕГЭ можно использовать программу (язык Python): a = ["К", "Л", "Р", "Т"] # буквы К, Л, Р, Т записаны в алфавитном # порядке s = "" # строка для формирования ответа x = 66 # числовой код слова: 67-1 = 66 while x > 0: # перевод в 4-ю систему счисления s += str(x%4) x //= 4 s = s[::-1] # реверс строки ответа for x in s: # формирование СЛОВА i = int(x) print( a[i], end="" ) Ответ: ЛККР. Решение (с помощью программы, С.С. Поляков): программа на языке Python использует модуль itertools: from itertools import product print(*list(product('КЛРТ',repeat=4))[67-1]) Ответ: ЛККР. Решение (с помощью программы, Б.С. Михлин): можно использовать «метод грубой силы» – перебор всех вариантов: n=0 s='клрт' for a in s: for b in s: for c in s: for d in s: n+=1 if n==67: print(a+b+c+d) exit() # выход из Python другой вариант (с «флажком» для входа из вложенного цикла) : n=0 s='клрт' fl=False # флажок сброшен for a in s: if fl: break for b in s: if fl: break for c in s: if fl: break for d in s: n+=1 if n==67: print(a+b+c+d) fl=True # флажок установлен для выхода break Ответ: ЛККР. |