Задание 26: обработка данных большого объёма

Работаем с тысячами чисел: сортируем, ищем минимумы и максимумы среди подмножеств, применяем жадные приёмы выбора.

Задание 26 почти всегда сводится к сортировке и аккуратному выбору элементов «с краёв» отсортированного списка.

Что проверяет задание 26

Задание 26 — высокий уровень, 1 балл. К ЕГЭ прилагается файл с большим количеством чисел (тысячи и десятки тысяч). Вопросы строятся вокруг порядка: «минимальное число, большее среднего», «второй по величине элемент», «сколько билетов можно купить на заданную сумму, если брать самые дешёвые», «k-й по порядку элемент». Ключ к решению — сортировка и работа с краями отсортированного списка.

Теория: сортировка решает почти всё

После сортировки по возрастанию первый элемент — минимум, последний — максимум, k-й по счёту легко взять по индексу. Многие «жадные» задачи («набрать как можно больше предметов в пределах суммы») решаются так: отсортировать по цене и брать самые дешёвые, пока хватает бюджета.

Метод решения

1. Прочитать все числа в список.
2. При необходимости отфильтровать подмножество (например, больше среднего).
3. Отсортировать.
4. Взять нужные элементы с краёв или пройти жадно.

Разбор примера

Дано 10000 чисел (имитируем генератором с фиксированным seed, чтобы результат был воспроизводим). Нужно: среднее, количество чисел больше среднего, минимальное и второе по величине среди них.

Решение на Python

import random
random.seed(42)                       # фиксируем — на экзамене числа берут из файла
data = [random.randint(1, 1000) for _ in range(10000)]

avg = sum(data) / len(data)           # среднее по всем
big = sorted(x for x in data if x > avg)   # подмножество, отсортированное

print("Среднее:", round(avg, 2))
print("Чисел больше среднего:", len(big))
print("Минимальное из них:", big[0])
print("Второе по величине из них:", big[-2])

Вывод:

Среднее: 502.17
Чисел больше среднего: 5032
Минимальное из них: 503
Второе по величине из них: 1000

Отсортировав подмножество, минимум берём как big[0], второй по величине — как big[-2]. На экзамене data заменяется чтением файла; всё остальное идентично.

Жадный приём: максимум покупок в бюджете

Классический сюжет: дан список цен и бюджет; сколько максимум товаров можно купить? Сортируем по возрастанию и берём, пока хватает денег.

prices = [50, 20, 30, 80, 10, 60, 25]
budget = 100

bought = 0
spent = 0
for p in sorted(prices):              # от самого дешёвого
    if spent + p <= budget:
        spent += p
        bought += 1
    else:
        break                         # дальше только дороже — смысла нет
print("Куплено товаров:", bought, "потрачено:", spent)

Вывод:

Куплено товаров: 4 потрачено: 85

Купили 10+20+25+30 = 85, четыре товара; следующий (50) уже не влезает в 100. Жадность здесь оптимальна: чтобы взять максимум предметов, всегда выгодно брать самые дешёвые.

Сортировка по нескольким ключам и «обратный» порядок

Иногда сортировать нужно не по самому числу, а по производному признаку: по сумме цифр, по последней цифре, по убыванию. В Python это параметр key и reverse=True. Пример: отсортировать числа по сумме цифр (по возрастанию), а при равной сумме — по самому числу.

def digit_sum(n):
    return sum(int(c) for c in str(n))

data = [42, 19, 23, 50, 14, 32, 5]
data_sorted = sorted(data, key=lambda x: (digit_sum(x), x))
print("По сумме цифр:", data_sorted)
print("Сумма цифр каждого:", [digit_sum(x) for x in data_sorted])

# Три самых больших — по убыванию
top3 = sorted(data, reverse=True)[:3]
print("Три наибольших:", top3)

Вывод:

По сумме цифр: [5, 14, 23, 32, 50, 42, 19]
Сумма цифр каждого: [5, 5, 5, 5, 5, 6, 10]
Три наибольших: [50, 42, 32]

Ключ-кортеж (digit_sum(x), x) задаёт сортировку сначала по первому полю, потом по второму — частый приём, когда есть основной и «разрешающий ничьи» критерий. Параметр reverse=True переворачивает порядок без отдельной функции.

Производительность

Сортировка десятков тысяч чисел в Python мгновенна (встроенный sorted — O(n log n)). Не пишите свою сортировку пузырьком — она может не уложиться по времени и точно не нужна. Если нужны только несколько крайних элементов (топ-3, топ-5), можно даже не сортировать весь список — модуль heapq с функциями nlargest/nsmallest сделает это ещё быстрее на очень больших данных.

import heapq

data = [42, 19, 23, 50, 14, 32, 5, 88, 7, 61]
print("3 наибольших:", heapq.nlargest(3, data))
print("3 наименьших:", heapq.nsmallest(3, data))

Вывод:

3 наибольших: [88, 61, 50]
3 наименьших: [5, 7, 14]

Типичные ошибки

• Ищут второй максимум перебором с ошибками. Проще отсортировать и взять a[-2].
• Жадность не от того края. «Максимум предметов» — берут дешёвые; «максимум стоимости в штуках» — другой критерий, читайте условие.
• Берут среднее по подмножеству вместо всех. Как и в задании 17 — следите, по чему считается среднее.
• Свой медленный алгоритм сортировки. Используйте встроенный sorted.

Итог

• Сортировка — главный инструмент задания 26: минимум, максимум, k-й элемент берутся по индексам.
• Жадный приём «максимум предметов в бюджете» — сортировка по цене и набор самых дешёвых.
• Используйте встроенный sorted (O(n log n)); свои сортировки не нужны.