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

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

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

Р-04. Сколько слов длины 5, начинающихся с гласной буквы, можно составить из букв Е, Г, Э? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Решение:

1. 
   первая буква слова может быть выбрана двумя способами (Е или Э), остальные – тремя
   
2. 
   общее число различных слов равно 2*3*3*3*3 = 162
   
3. 
   ответ: 162.
   

Решение (через формулы, А.Н. Носкин):

1. 
   Дано слово длиной 5 символов типа *****, где красная звездочка – гласная буква (Е или Э), а черная буква любая из трёх заданных.
   
2. 
   Общая формула количества вариантов:
   

N = M^L, где М – мощность алфавита, а L – длина кода.

3. 
   Так как положение одной из букв строго регламентировано (знак умножения в зависимых событиях), то формула всех вариантов примет вид: N = M₁^L1 ∙ M₂^L2,
   
4. 
   Тогда M₁ = 2 (алфавит гласных букв), а L₁ = 1 (только 1 позиция в слове).
   

M₂ = 3 (алфавит всех букв), а L₂ = 4 (оставшиеся 4 позиции в слове).

5. 
   В итоге получаем: N = 2¹ ∙ 3⁴ = 2 ∙ 81 = 162.
   
6. 
   ответ: 162.
   

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

1. 
   для построения множества всевозможных слов можно использовать функцию 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)

2. 
   Ответ: 162.
   

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

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

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)

6. 
   Ответ: 162.
   

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

Р-03. Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:

1. КККК

2. КККЛ

3. КККР

4. КККТ

……

Запишите слово, которое стоит на 67-м месте от начала списка.

Решение:

1. 
   самый простой вариант решения этой задачи – использование систем счисления; действительно, здесь расстановка слов в алфавитном порядке равносильна расстановке по возрастанию чисел, записанных в четверичной системе счисления (основание системы счисления равно количеству используемых букв)
   
2. 
   выполним замену К0, Л1, Р2, Т3; поскольку нумерация слов начинается с единицы, а первое число КККК0000 равно 0, под номером 67 будет стоять число 66, которое нужно перевести в четверичную систему: 66 = 1002₄
   
3. 
   Выполнив обратную замену (цифр на буквы), получаем слово ЛККР.
   
4. 
   Ответ: ЛККР.
   

Решение (с помощью программы, А.Н. Носкин):

1. 
   на компьютерном ЕГЭ можно использовать программу (язык 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="" )

2. 
   Ответ: ЛККР.
   

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

1. 
   программа на языке Python использует модуль itertools:
   

from itertools import product

print(*list(product('КЛРТ',repeat=4))[67-1])

2. 
   Ответ: ЛККР.
   

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

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

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

8. 
   другой вариант (с «флажком» для входа из вложенного цикла) :
   

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

9. 
   Ответ: ЛККР.