Как решать задачи на Python для подготовки к ЕГЭ

Раздел: Образование -> Подготовка к экзаменам

Разбор типовой задачи ЕГЭ: поиск пар с произведением, кратным 26

Как найти количество пар чисел, произведение которых делится на 26, за линейное время?

Эффективное решение использует подсчет остатков по модулю 2 и 13, так как 26 = 2 * 13. Произведение двух чисел кратно 26, если:

одно из чисел кратно 26, или
одно число кратно 2, а другое кратно 13.

Будем последовательно обрабатывать числа, сохраняя количество встреченных чисел каждого типа: кратных 2, кратных 13, кратных 26. При поступлении нового числа x:

def count_pairs(data):
    cnt2 = 0
    cnt13 = 0
    cnt26 = 0
    total = 0
    for x in data:
        if x % 26 == 0:
            total += cnt2 + cnt13 + cnt26   # любое предыдущее подходит
            cnt26 += 1
        elif x % 13 == 0:
            total += cnt2                   # только кратные 2
            cnt13 += 1
        elif x % 2 == 0:
            total += cnt13                  # только кратные 13
            cnt2 += 1
        # числа, не кратные 2 и 13, не влияют на пары
    return total

# Пример использования:
n = int(input())
arr = [int(input()) for _ in range(n)]
print(count_pairs(arr))

яндекс задания python (задания от яндекса по python)

Пояснение: сначала проверяется кратность 26, затем 13, затем 2. Это исключает двойной учет для чисел, кратных 26 (они проходят только в первом условии). После подсчета пар обновляются счетчики для будущих чисел.

Типичные ошибки: неверный порядок проверки условий (например, сначала проверка на кратность 2, потом на 13) приводит к двойному учету; забывают обновлять счетчики; не учитывают, что число, кратное 26, подходит для любой пары, а не только с кратными 2 или 13; при больших N двойной цикл недопустим.

Вариант 1: простой перебор (O(n^2))

Когда количество чисел невелико (до 1000), можно применить двойной цикл. Это наглядно и не требует дополнительных вычислений.

n = int(input())
data = [int(input()) for _ in range(n)]
count = 0
for i in range(n):
    for j in range(i+1, n):
        if (data[i] * data[j]) % 26 == 0:
            count += 1
print(count)

Python разработчик тестовые задания (примеры тестовых заданий python)

Проблемы: при n > 10000 программа работает слишком долго; легко ошибиться с границами внутреннего цикла (забыть i+1) и учитывать пары с одинаковыми индексами или дублировать их.

Вариант 2: использование словаря для остатков

Можно обобщить подход на любое число k. Для каждого числа вычисляется остаток r от деления на k, затем ищутся все остатки s, такие что (r * s) % k == 0. Количество ранее встреченных чисел с остатком s добавляется к ответу.

from collections import defaultdict

def count_pairs_dict(data):
    k = 26
    remainders = defaultdict(int)
    total = 0
    for x in data:
        r = x % k
        for s in range(k):
            if (r * s) % k == 0:
                total += remainders[s]
        remainders[r] += 1
    return total

Недостаток: сложность O(N*k). Для k=26 это приемлемо, но при больших k (например, 1000) становится неэффективным. Ошибка: можно случайно учесть пару с самим собой, если не обновлять счетчик после подсчета пар. В коде обновление происходит после цикла, поэтому self-пара не засчитывается.

- Python тестовое (тестовое задание python)

- задачи огэ python (задачи огэ по python)

- задачи python 9 класс (задачи по python для 9 класса)

Дополнительные примеры задач ЕГЭ с решениями

Задача на строки: проверка возможности перестановки букв в палиндром

Условие: дана строка из строчных латинских букв. Проверить, можно ли переставить буквы так, чтобы получить палиндром (строка, читающаяся одинаково слева и справа).

Решение: в палиндроме может быть не более одного символа с нечетным количеством вхождений.

Пример

def can_be_palindrome(s):
    odd = 0
    for ch in set(s):
        if s.count(ch) % 2 == 1:
            odd += 1
    return odd <= 1

print(can_be_palindrome("aabb"))  # True
print(can_be_palindrome("abc"))   # False

True
False

Пояснение: set(s) дает уникальные символы, для каждого подсчитывается количество вхождений. Если нечетных счетчиков больше одного, палиндром невозможен.

Задача на файлы: количество пар с четной суммой

Условие: в файле input.txt сначала записано число N, затем N целых чисел. Найти количество пар (i < j), сумма которых четна.

Пример

with open('input.txt', 'r') as f:
    n = int(f.readline())
    data = [int(f.readline()) for _ in range(n)]

count = 0
for i in range(n):
    for j in range(i+1, n):
        if (data[i] + data[j]) % 2 == 0:
            count += 1
print(count)

Пример: файл содержит числа 1,2,3,4. Результат: 2 (пары (1,3) и (2,4)).

Пояснение: сумма четна, если оба числа четны или оба нечетны. Можно оптимизировать, подсчитав количество четных (even) и нечетных (odd) чисел и вычислив C(even,2) + C(odd,2). Но в учебных целях показан перебор.

Задача на рекурсию: числа Фибоначчи с мемоизацией

Условие: вычислить N-ое число Фибоначчи (где F(0)=0, F(1)=1).

Пример

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

print(fib(10))  # 55

Пояснение: мемоизация сохраняет уже вычисленные значения, что превращает экспоненциальный перебор в линейный. Рекурсивный вызов с параметром memo передает словарь между рекурсиями, избегая глобальной переменной.

Задачи ЕГЭ по Python - comments

егэ python задачи (python)