Задачи с частотным анализом в №24

Задачи с частотным анализом в №24

👋 Финальный тип. Именно он для многих покажет, реально ли есть понимание, или вы просто выучили код. Хоть он и не встречался на ЕГЭ в таком виде, но идея суперважная, не только для подготовки к №24, но и к ЕГЭ в целом, конкретно, например, в некоторых №26 встречается похожая штука!

✅ Повторяющиеся комбинации

✅ Запрещённые комбинации

✅ Ограниченное количество

✅ Сложные шаблоны

✅ Несколько строк

👉 Частотный анализ (сейчас)

Суть типа - поиск символа (группы символов), встречающегося чаще всего в какой-то ситуации. Тут как всегда рассмотрим несколько способов, на теорию забьем, сразу за дело. Возьму задачу №24.30003 с bank-kege.ru

Условие:

Текстовый файл содержит только заглавные буквы латинского алфавита (ABC…Z). Определите символ, который чаще всего встречается в файле сразу после буквы A.

1⃣ Словари

Идея: Будем подсчитывать каждую букву после А с помощью словарей: ключами будут буквы, а значениями - количество вхождений после А. Изначально сделаем пустой словарь, пойдем по индексам строки, начиная с первого (нулевой не может стоять после А). Если предыдущий символ - А, по ключу текущего символа увеличиваем значение в словаре на 1. Чтобы получить ответ, найдем максимум из ключей словаря. Но функция max() базово хочет искать максимум по алфавиту, нам это не подходит, поэтому используем key и получаем значение словаря методом get()

Код:

s = open('24.30003.txt').readline()

d = {}

for i in range(1, len(s)):

if s[i - 1] == 'A':

if s[i] not in d:

d[s[i]] = 0

d[s[i]] += 1

print(max(d, key=d.get))

2⃣ Функции ord() и chr()

Идея: Будем подсчитывать количество вхождений аналогично первому способу, но использовать не словарь, а список. Функция ord() позволяет получить номер символа в таблице Unicode, заглавной букве A соответствует код 65, Z - 90, остальной латинский алфавит по порядку между ними. Создадим список на 26 элементов (столько букв в латинском алфавите), а для каждого символа после А будем смотреть его код, а индекс в списке будет просто на 65 меньше. В конце узнаем под каким индексом лежит наибольшее значение, прибавим обратно 65 и превратим код в символ функцией chr()

Код:

s = open('24.30003.txt').readline()

d = [0] * 26

for i in range(1, len(s)):

if s[i - 1] == 'A':

d[ord(s[i]) - 65] += 1

mx = max(d)

ind = [i for i in range(26) if d[i] == mx][0]

print(chr(ind + 65))

3⃣ Метод count()

Идея: Перебираем все символы латинского алфавита (они лежат в ascii_uppercase из библиотеки string) и считаем количество сочетаний A{символ} методом count(). Если больше максимума, то обновляем его и запоминаем символ. Выводим символ в ответ.

Код:

from string import ascii_uppercase

s = open('24.30003.txt').readline()

mx = 0

symb = ''

for x in ascii_uppercase:

cur_cnt = s.count(f'A{x}')

if cur_cnt > mx:

mx = cur_cnt

symb = x

print(symb)

❗️ ВАЖНО! По сути нам просто фортит тут, что ответ сошелся. В чем же дело? В строке АААА буква А встречается после другой А 3 раза, а метод count() насчитает всего 2 сочетания, так как он работает жадно, то есть каждая следующая подстрока, которую он учитывает, начинается после предыдущей. Если не перепроверить другим способом, то такое решение - риск, а выдумывать свой метод count(), который посчитает все вхождения, смысла нет, проще использовать другой способ.

Сегодня я показал вам, как какой-то способ может не давать гарантии результата 100%. На ЕГЭ победит не тот, кто больше вызубрил, а тот кто понимает, что происходит, как работают те методы, которые вы используете, какие у них есть плюсы и минусы. Последний способ проще двух других, но цена этой простоты - шанс 1/26, что ответ не сойдется, если самой частовстречающейся буквой окажется А.

В домашку вам задачи №24.30004, №24.30005. Давайте спорить, дискутировать, предлагайте свои решения. Если по пути к ЕГЭ, благодаря таким задачам получится позаниматься развитием мозгов, это будет только плюс)

Ну и по традиции голосование: какой способ понравился больше?

🔥 Словари

💯 Функции ord() и chr()

❤️‍🔥 Метод count()

#информатика

#задание24