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

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

© К. Поляков, 2009-2021

8 (базовый уровень, время – 4 мин)

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

Что проверяется:

Знание о методах измерения количества информации (?)

1.6.1. Формализация понятия алгоритма (?)

1.1.4. Читать и отлаживать программы на языке программирования (?)

Что нужно знать:

• 
  В русском языке 33 буквы: 10 гласных букв (а, у, о, ы, и, э, я, ю, ё, е), 21 согласная буква (б, в, г, д, ж, з, й, к, л, м, н, п, р, с, т, ф, х, ц, ч, ш, щ) и два знака (ь, ъ).
  
• 
  Алфавит английского языка по написанию совпадает с латинским алфавитом и состоит из 26 букв.
  
• 
  принципы работы с числами, записанными в позиционных системах счисления
  
• 
  если слово состоит из L букв, причем есть n₁ вариантов выбора первой буквы, n₂ вариантов выбора второй буквы и т.д., то число возможных слов вычисляется как произведение
  

N = n₁ · n₂ · … · n_L

• 
  если слово состоит из L букв, причем каждая буква может быть выбрана n способами, то число возможных слов вычисляется как N = n^L
  
• 
  если в программе L вложенных циклов и внешний цикл выполняется n₁ раз, следующий (вложенный) n₂ раз и т.д., то команды самого внутреннего цикла будут выполняться N раз, где
  

N = n₁ · n₂ · … · n_L.

Если n₁ = n₂ = … = n_L = n, то N = n^L.

• 
  при увеличении n или L значение N сильно возрастает, что приводит к существенному увеличению времени выполнения программы.
  

Пример задания:

Р-11 (демо-2021). Игорь составляет таблицу кодовых слов для передачи сообщений, каждому

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

Решение (теоретическое):

1. 
   буква К может стоять на одном из трёх мест, остальные две буквы выбираются из оставшихся четырёх: Ш, О, Л или А
   
2. 
   пусть К – первая буква, тогда оставшиеся две буквы можно выбрать 4² = 16 способами
   
3. 
   так как К может стоять на одной из трёх позиций, общее количество подходящих слов –
   3  16 = 48
   
4. 
   Ответ: 48.
   

Решение (с помощью программы):

1. 
   для проверки решения (при наличии времени) можно использовать рекурсивный перебор (см. учебник К.Ю. Поляков, Е.А. Еремин. Информатика: базовый и углублённый уровни. М.: БИНОМ. Лаборатория знаний, 2019): перебрать всевозможные слова длиной 3 и посчитать те из них, в которых только одна буква К
   
2. 
   шаблон рекурсивной функции, выполняющей перебор, на языке Python может выглядеть так:
   

def rec( word, k, Alpha ):

global count

if len(word) == k:

if valid(word): count += 1

return

for c in Alpha:

rec( word+c, k, Alpha )

3. 
   функция rec принимает три параметра: уже построенную часть слова word, заданную длину слов k и алфавит Alpha
   
4. 
   если длина слова word равна k, слово полностью построено; проверяем его функцией valid, которая возвращает True, если слово подходящее;
   
5. 
   если слово удовлетворяет требованиям, увеличиваем глобальную переменную count (счётчик подходящих слов)
   
6. 
   если слово ещё не достроено (его длина меньше k) в цикле добавляем в конец слова по очереди все буквы из алфавита и вызываем процедуру rec рекурсивно
   
7. 
   основная программа выглядит так:
   

count = 0

rec( "", 3, "ШКОЛА" )

print( count )

в начальный момент первый аргумент – пустая строка (ещё ни одна буква не выбрана)

8. 
   функция valid в данной задаче должна проверять, верно ли, что слово содержит ровно одну букву К:
   

def valid( word ):

return word.count('К') == 1

конечно, в другой задаче функцию valid нужно изменить в соответствии с условием

9. 
   Ответ: 48.
   

Решение (с помощью программы c функцией):

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

def valid( word ):

return word.count('К') == 1
def rec( word, k, Alpha ):

if len(word) == k:

if valid(word): return 1

return 0

count = 0

for c in Alpha:

count += rec( word+c, k, Alpha )

return count
print( rec( "", 3, "ШКОЛА" ) )

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

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

from itertools import product

p = product('ШКОЛА', repeat=3)

n = 0

for x in p:

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

n += 1

print(n)

2. 
   Ответ: 48.
   
3. 
   (Б.С. Михлин) Более компактная запись программы с генератором списка
   

from itertools import product

p=[x for x in product('ШКОЛА',repeat=3)

if x.count('К')==1 ]

print(len(p))

4. 
   Ответ: 48.
   

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

1. 
   Решение перебором всех возможных комбинаций символов (a, b, c) и подсчет среди них комбинаций, где 'к' встречается только один раз.
   

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)

2. 
   Ответ: 48.