Python: словари и множества: разбор для ЕГЭ

Зачем нужны словари и множества на ЕГЭ по информатике

При решении задач второй части ЕГЭ обычные списки часто приводят к превышению времени работы программы или громоздкому коду. В этой статье мы по шагам разберем структуры данных dict и set, чтобы ты научился писать эффективные алгоритмы и гарантированно сохранил драгоценные минуты на экзамене.

На ЕГЭ по информатике скорость выполнения кода имеет решающее значение в номерах 17, 24, 26 и 27. Когда объем входного файла составляет сотни тысяч строк, поиск элемента внутри обычного списка занимает линейное время O(N). Если такой поиск вызывается внутри цикла, программа может зависнуть на несколько минут, лишив тебя возможности быстро проверить ответ.

Словари (dict) и множества (set) в языке Python построены на основе хеш-таблиц. Это означает, что проверка наличия элемента, добавление новой записи или получение значения по ключу происходят в среднем за константное время O(1), то есть практически мгновенно. Понимание этих структур позволяет с легкостью решать задачи на подсчет частоты символов, фильтрацию дубликатов и группировку пар данных.

В онлайн-школе «Просто Урок» мы учим видеть внутреннюю логику структур данных, чтобы не зубрить синтаксис, а применять его на автомате в любой нестандартной формулировке.

Множества (set): уникальность и мгновенный поиск элементов

Множество в Python — это изменяемая неупорядоченная коллекция, которая содержит исключительно уникальные элементы. Главная суперсила множеств — удаление дубликатов в одну строчку и моментальная проверка условия x in s. Создать пустое множество можно только с помощью вызова set(), так как пустые фигурные скобки {} создадут словарь.

# Создание множеств и базовые операции
\( numbers = [1, 2, 2, 3, 4, 4, 5] \)
\( unique_nums = set(numbers) # {1, 2, 3, 4, 5} \)
unique_nums.add(6) # добавление одного элемента
print(3 in unique_nums) # True (выполняется за O(1))

Для эффективного решения задач ЕГЭ полезно знать операции над несколькими множествами. Они соответствуют логическим операциям и кругам Эйлера:

\( a = {1, 2, 3, 4} \)
\( b = {3, 4, 5, 6} \)
print(a & b) # Пересечение: {3, 4} (элементы есть и в a, и в b)
print(a | b) # Объединение: {1, 2, 3, 4, 5, 6}
print(a - b) # Разность: {1, 2} (элементы есть в a, но отсутствуют в b)

Сравним основные структуры данных, которые применяются на экзамене:

Структура	Уникальность	Порядок элементов	Сложность поиска (in)
Список (list)	Допускает дубли	Строго по индексам	O(N) — медленно
Множество (set)	Только уникальные	Не гарантируется	O(1) — мгновенно
Словарь (dict)	Ключи уникальны	Сохраняет порядок добавления	O(1) по ключу

Словари (dict): связка «ключ-значение» и частотный анализ

Словарь представляет собой отображение, где каждому уникальному ключу соответствует определенное значение. Ключом может быть любой неизменяемый тип данных: число, строка или кортеж (tuple). Словари незаменимы в задачах, где нужно посчитать, сколько раз встретилось каждое число или символ, а также для хранения парных соответствий.

# Базовая работа со словарем
\( stats = {} \)
word = "ЕГЭ ИНФОРМАТИКА"
for char in word:
\(     stats[char] = stats.get(char, 0) + 1 \)
print(stats['Е']) # Выведет количество букв 'Е'

Для тренировки быстрого написания таких конструкций загляни в личный кабинет Просто Урок — там собраны интерактивные задачи для отработки синтаксиса без лишней теории.

Подводные камни и частые ошибки выпускников

Первая распространенная ошибка — попытка положить изменяемый объект в качестве ключа словаря или элемента множества. Например, попытка добавить список set_data.add([1, 2]) приведет к ошибке TypeError: unhashable type: 'list'. Чтобы исправить это, замени список на неизменяемый кортеж: set_data.add((1, 2)).

Вторая ловушка связана с изменением коллекции прямо во время итерации по ней. Если ты попытаешься удалить или добавить элементы в словарь внутри цикла for, Python выбросит исключение.

Также помни, что множества нельзя индексировать. Запись s[0] вызовет ошибку, так как у элементов множества нет фиксированных позиций. Если тебе нужен первый или наименьший элемент, используй функции min(s), max(s) или преврати множество в отсортированный список с помощью sorted(s).

Разбор типовой экзаменационной задачи

Рассмотрим популярный прототип задачи 24 (обработка символьных строк): в текстовом файле записана последовательность заглавных латинских букв. Необходимо определить символ, который чаще всего встречается сразу после буквы 'A'. Если таких символов несколько, вывести тот, который стоит раньше по алфавиту.

Алгоритм решения по шагам:

Шаг 1. Открываем файл и считываем всю строку: s = open('24.txt').readline()
Шаг 2. Создаем пустой словарь для подсчета символов: count = {}
Шаг 3. В цикле от 0 до len(s) - 2 проверяем: если s[i] == 'A', берем символ s[i + 1]
Шаг 4. Увеличиваем счетчик для s[i + 1]: count[s[i + 1]] = count.get(s[i + 1], 0) + 1
Шаг 5. Находим максимальную частоту: max_freq = max(count.values())
Шаг 6. Находим подходящие буквы и выбираем первую по алфавиту через min()

Программный код на Python выглядит компактно и понятно:

with open('24.txt') as f:
\(     s = f.readline() \)

\( freq = {} \)
\( for i in range(len(s) - 1): \)
    if s[i] == 'A':
\(         next_char = s[i + 1] \)
\(         freq[next_char] = freq.get(next_char, 0) + 1 \)

\( max_val = max(freq.values()) \)
\( best_chars = [char for char, val in freq.items() if val == max_val] \)
print(min(best_chars), max_val)

Благодаря словарю подсчет частот выполняется за один проход по файлу. Если ты хочешь отработать подобные алгоритмы на актуальных файлах из базы ФИПИ, открой практический тренажер в системе Просто Урок.

Что запомнить: шпаргалка и следующий шаг

Подведем итог всему, что необходимо уверенно применять на экзамене:

1. set() — гарантирует уникальность и дает мгновенный поиск O(1).
2. dict — хранит пары «ключ-значение», идеален для частотного анализа.
3. dict.get(k, 0) — защищает от ошибки KeyError при подсчете.
4. Ключами могут быть только неизменяемые типы: int, float, str, tuple.
5. Нельзя менять размер коллекции прямо во время итерации по ней.

Теория дает максимальный результат только тогда, когда сразу подкрепляется решением реальных номеров. Переходи в бесплатный личный кабинет Просто Урок и реши 5 тематических заданий прямо сейчас, чтобы надежно закрепить работу со словарями и множествами перед экзаменом.