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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 12.01.2024

Просмотров: 375

Скачиваний: 2

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

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

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


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

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

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

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

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

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

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

  • Алфавит английского языка по написанию совпадает с латинским алфавитом и состоит из 26 букв.

  • принципы работы с числами, записанными в позиционных системах счисления

  • если слово состоит из L букв, причем есть n1 вариантов выбора первой буквы, n2 вариантов выбора второй буквы и т.д., то число возможных слов вычисляется как произведение

N = n1 · n2 · … · nL

  • если слово состоит из L букв, причем каждая буква может быть выбрана n способами, то число возможных слов вычисляется как N = nL

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

N = n1 · n2 · … · nL.

Если n1 = n2 = … = nL = n, то N = nL.

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

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


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

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


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

  1. буква К может стоять на одном из трёх мест, остальные две буквы выбираются из оставшихся четырёх: Ш, О, Л или А

  2. пусть К – первая буква, тогда оставшиеся две буквы можно выбрать 42 = 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 )

  1. функция rec принимает три параметра: уже построенную часть слова word, заданную длину слов k и алфавит Alpha

  2. если длина слова word равна k, слово полностью построено; проверяем его функцией valid, которая возвращает True, если слово подходящее;

  3. если слово удовлетворяет требованиям, увеличиваем глобальную переменную count (счётчик подходящих слов)

  4. если слово ещё не достроено (его длина меньше k) в цикле добавляем в конец слова по очереди все буквы из алфавита и вызываем процедуру rec рекурсивно

  5. основная программа выглядит так:

count = 0

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

print( count )

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

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

def valid( word ):

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

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

  1. Ответ: 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)

  1. Ответ: 48.

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

from itertools import product

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

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

print(len(p))

  1. Ответ: 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)

  1. Ответ: 48.

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


Р-10. Маша составляет шестибуквенные слова перестановкой букв слова КАПКАН. При этом она избегает слов с двумя подряд одинаковыми буквами. Сколько различных кодов может составить Маша?

Решение:

  1. если не учитывать, что в слове есть одинаковые буквы, общее количество перестановок 6 букв равно 6! = 720

  2. так как перестановка пары одинаковых букв не даёт нового слова, каждая пара уменьшает количество уникальных слов в 2 раза; а у нас 2 пары (повторяются К и А), поэтому количество уникальных слов – в 4 раза меньше, оно равно 720/4 = 180

  3. теперь из 180 нужно вычесть количество слов, где встречаются пары КК и АА;

  4. сначала найдём количество слов, в которых встречаются обе пары, и КК, и АА; обозначим X=КК, Y=АА, таким образом, нужно найти количество слов из 4-х разных «букв» (Н, П, Х, Y), это количество равно 4! = 24

  5. теперь подсчитаем слова, в которых есть X=КК, но нет АА; получаем набор из 5 «букв» (А, A, Н, П, Х), количество уникальных слов равно 5!/2 = 60 (учитывая, что перестановка букв А не меняет слово); кроме того, среди них есть еще 24 слова, в которых есть обе пары, то есть имеем 60 – 24 = 36 слов, где есть КК, но нет АА

  6. аналогично получаем, что есть 36 слов, где есть АА, но нет КК

  7. количество нужных нам слов равно 180 – 24 – 36 – 36 = 84.

  8. Ответ: 84.

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

  1. Использование функции permutations (перестановки) модуля itertools и генератора множества.

def ok(x):

for i in range(5):

if x[i]==x[i+1]: # соседние буквы д.б. разными

return False

else:

return True
from itertools import permutations

s = 'капкан'

# множество удаляет повторяющиеся перестановки

# (из-за двух 'а' и двух 'к' в s)

m = { x for x in permutations(s) if ok(x) }

print(len(m))

  1. Можно обойтись и без функции (Д. Баянов):

from itertools import permutations

s = 'капкан'

m = { x for x in permutations(s)

if x[0] != x[1] and x[1] != x[2] and x[2] != x[3] and

x[3] != x[4] and x[4] != x[5] }

print(len(m))

  1. Ответ: 84.

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


Р-09. Маша составляет 5-буквенные коды из букв В, У, А, Л, Ь. Каждую букву нужно использовать ровно 1 раз, при этом код буква Ь не может стоять на первом месте и перед гласной. Сколько различных кодов может составить Маша?


Решение:

  1. проще всего сначала найти общее количество возможных слов, а затем вычесть из него количество «запрещённых» слов – тех, которые начинаются на букву Ь или содержат комбинации ЬУ и ЬА

  2. сначала найдём общее количество слов, не накладывая никаких ограничений; при этом есть 5 способов выбрать первую букву, 4 способа выбрать вторую и т.д., так что общее число вариантов равно 5! = 5  4  3  2  1 = 120

  3. первой буквой не может быть Ь, это исключает 1  4  3  2  1 = 24 варианта

  4. теперь определим, сколько слов содержит запрещённую комбинацию символов ЬУ; эта комбинация может располагаться на одной из 4-х позиций:

ЬУ***, *ЬУ**, **ЬУ*, ***ЬУ

первый случай уже исключён (слово не может начинаться с буквы Ь), для каждого из остальных случаев количество вариантов распределения остальных букв равно 3  2  1 = 6 варианта, то есть запрет сочетания ЬУ исключает 3  3  2  1 = 18 кодов

  1. аналогично запрет сочетания ЬА исключает ещё 18 кодов

  2. таким образом, из 120 слов запрещёнными являются 24 варианта с первой буквой Ь, 18 варианта, содержащие ЬУ в середине слова, и 18 вариантов, содержащие ЬА в середине слова

  3. остаётся 120 – 24 – 18 – 18 = 60 кодов

  4. Ответ: 60.

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

  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.count('В')==1) and (x.count('У')==1) and

(x.count('А')==1) and (x.count('Л')==1) and

(x.count('Ь')==1)) and

(x[0] != 'Ь') and (x.find('ЬУ')==-1 and

x.find('ЬА')==-1):

n += 1

print(n)

  1. Ответ: 60.

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

  1. Можно использовать перебор всех вариантов во вложенном цикле. Когда слово построено, проверяем, подходит ли оно по условию.

n=0

s='вуаль'

for a in s[:4]: # s без 'ь'

for b in s:

for c in s:

for d in s:

for e in s:

st=a+b+c+d+e # полученный 5-буквенный код

for x in s:

if st.count(x)!=1:

break

else: # все символы встретились ровно один раз

Смотрите также файлы