Сообщество

Алгоритмы для ЕГЭ по информатике

Знание алгоритмов — ключ к решению заданий 24-27. Разберём основные алгоритмы.

Алгоритмы сортировки

Сортировка пузырьком (Bubble Sort)

Идея: сравниваем соседние элементы и меняем местами, если нужно

Сложность: O(n^2)

Код: Выделить всё

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

Сортировка выбором (Selection Sort)

Идея: находим минимум и ставим на первое место, повторяем

Сложность: O(n^2)

Код: Выделить всё

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Быстрая сортировка (Quick Sort)

Идея: выбираем опорный элемент, делим массив на две части

Сложность: O(n log n) в среднем

Код: Выделить всё

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

Алгоритмы поиска

Линейный поиск

Идея: перебираем все элементы по порядку

Сложность: O(n)

Код: Выделить всё

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

Бинарный поиск

Идея: делим отсортированный массив пополам

Сложность: O(log n)

Требование: массив должен быть отсортирован!

Код: Выделить всё

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Рекурсия

Рекурсия — вызов функцией самой себя

Элементы рекурсии:
1. Базовый случай — условие остановки
2. Рекурсивный случай — вызов с изменённым параметром

Пример: факториал

Код: Выделить всё

def factorial(n):
    if n <= 1:  # базовый случай
        return 1
    return n * factorial(n - 1)  # рекурсивный случай

Пример: числа Фибоначчи

Код: Выделить всё

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Работа с массивами

Поиск максимума/минимума:

Код: Выделить всё

def find_max(arr):
    max_val = arr[0]
    for x in arr:
        if x > max_val:
            max_val = x
    return max_val

Подсчёт элементов:

Код: Выделить всё

def count_positive(arr):
    count = 0
    for x in arr:
        if x > 0:
            count += 1
    return count

Сумма элементов:

Код: Выделить всё

def sum_array(arr):
    total = 0
    for x in arr:
        total += x
    return total

Сложность алгоритмов

O(1) — константная (доступ по индексу)
O(log n) — логарифмическая (бинарный поиск)
O(n) — линейная (один проход)
O(n log n) — быстрая сортировка
O(n^2) — квадратичная (два вложенных цикла)

Советы для ЕГЭ

- Знайте базовые алгоритмы наизусть
- Понимайте сложность алгоритмов
- Умейте выбирать эффективный алгоритм
- Тестируйте код на примерах

Алгоритмы — язык программирования!

Дополнительные рекомендации

Для максимального результата:

1. Начните подготовку заранее — минимум за 6 месяцев до экзамена
2. Составьте чёткий план изучения всех тем кодификатора
3. Регулярно решайте задания из открытого банка ФИПИ
4. Анализируйте каждую ошибку — ведите журнал ошибок
5. Решайте пробные варианты в условиях, приближённых к экзамену
6. Не забывайте про отдых — переутомление снижает эффективность
7. Используйте разные источники информации

Что делать за неделю до экзамена:

- Лёгкое повторение основных тем
- Один пробный вариант в начале недели
- Просмотр формул и ключевых понятий
- Полноценный сон и отдых
- Никакого нового материала

В день экзамена:

- Хороший завтрак без экспериментов
- Приехать за 30-40 минут до начала
- Взять паспорт, ручки, воду
- Сохранять спокойствие и уверенность

Во время экзамена:

- Внимательно читать каждое задание
- Следить за временем
- Начинать с простых заданий
- Оставить время на проверку
- Не оставлять пустых ответов

Полезные ресурсы для подготовки

Официальные источники:
- fipi.ru — демоверсии, кодификаторы, открытый банк заданий
- ege.edu.ru — официальный портал ЕГЭ

Для практики:
- Решу ЕГЭ — тренажёр с автоматической проверкой
- Незнайка — тесты и разборы
- YouTube-каналы преподавателей

Для теории:
- Учебники из федерального перечня
- Справочники по предметам
- Онлайн-курсы от ведущих вузов

Желаем успехов на экзамене! Вы справитесь!

Сообщество

Алгоритмы для ЕГЭ по информатике: сортировка и поиск

Алгоритмы для ЕГЭ по информатике: сортировка и поиск