12 мин чтенияPythonстрокиспискифайлышаблоныКЕГЭ
Программирование: Python-шаблоны для КЕГЭ
Чтение файлов, строки, списки, срезы, сортировка, перебор, генераторы и стандартные приёмы для задач на компьютере.
Открываем тему…
Ввод данных и файлы
В заданиях КЕГЭ данные чаще всего даются файлом .txt или .xlsx. Откройте файл, прочитайте строки, преобразуйте в числа и работайте со списком. Для больших файлов не используйте квадратичные алгоритмы.
ПримерЧтение чисел из файла
Прочитайте все числа из файла data.txt, записанные по одному в строке.
Решение
with open('data.txt') as file:
a = [int(line) for line in file]
print(len(a), min(a), max(a))
Для первой строки с количеством: n = int(file.readline()), далее остальные числа.
Строки и срезы
- s[i:j:k] — срез; s[::-1] — разворот; s.count(sub), s.find(sub), s.replace(a, b).
- Для поиска самой длинной цепочки одинаковых символов удобно заменять и сравнивать: пока в строке встречается подстрока из k символов — увеличивайте k.
- Строки в Python неизменяемые: для множества правок собирайте список и объединяйте через ''.join().
- Регулярные выражения (модуль re) решают поиск по шаблону: re.findall(r'[A-Z]{3}\d+', s).
ПримерСамая длинная подцепочка
В файле одна строка из букв A, B, C. Найдите длину наибольшей цепочки подряд идущих A.
Решение
s = open('data.txt').readline().strip()
best = cur = 0
for ch in s:
if ch == 'A':
cur += 1
best = max(best, cur)
else:
cur = 0
print(best)
Списки, сортировка и сочетания
- sorted(a, key=lambda x: (x[1], -x[0])) — сортировка по нескольким ключам.
- from itertools import permutations, combinations, product — перебор вариантов.
- from collections import Counter — подсчёт частот: Counter(a).most_common(3).
- Двойные суммы по массиву заменяйте префиксными суммами: pref[i] = pref[i−1] + a[i].
ПримерПеребор пар
Дан список из 10⁵ чисел. Найдите количество пар (i < j), у которых сумма делится на 14, без вложенного цикла.
Решение
Считаем остатки по модулю 14:
from collections import Counter
c = Counter(x % 14 for x in a)
total = 0
for r in range(14):
s = (14 - r) % 14
if r < s:
total += c[r] * c[s]
elif r == s:
total += c[r] * (c[r] - 1) // 2
print(total)
Числа и делители
- Простота: перебор делителей до int(n ** 0.5) + 1.
- НОД: math.gcd(a, b); НОК: a // gcd(a, b) * b.
- Системы счисления: int('1011', 2), bin(n)[2:], oct(n), hex(n); для произвольного основания пишите функцию.
- Для вещественных вычислений сравнивайте с допуском: abs(a − b) < 1e-9.
ПримерРешето Эратосфена
Сколько существует простых чисел, не превышающих 10⁶?
Решение
Перебор делителей для каждого числа слишком медленный; решето за O(n log log n) вычёркивает кратные каждого простого.
N = 10**6
sieve = [True] * (N + 1)
sieve[0] = sieve[1] = False
for i in range(2, int(N ** 0.5) + 1):
if sieve[i]:
for j in range(i * i, N + 1, i):
sieve[j] = False
print(sum(sieve)) # 78498
Массив sieve позволяет потом мгновенно проверять простоту любого числа до N.
ПримерЧисла по маске: регулярные выражения
Маска числа: «?» — ровно одна цифра, «*» — любая последовательность цифр (возможно, пустая). Как найти в диапазоне до 10⁷ числа вида 1?2*5, кратные 123?
Решение
Переводим маску в регулярное выражение: «?» → \d, «*» → \d*. Перебираем только кратные 123, чтобы не проверять все 10⁷ чисел:
import re
for n in range(123, 10**7 + 1, 123):
if re.fullmatch(r'1\d2\d*5', str(n)):
print(n)
Для двух звёздочек и других символов маски шаблон строится так же; не забывайте, что «*» допускает и пустую последовательность.