Алгоритмы и программирование: теория для ЕГЭ
📚 Ключевые понятия
Алгоритм
Конечная последовательность точных инструкций для решения задачи
Переменная
Именованная область памяти для хранения данных, значение которой может изменяться
Цикл
Конструкция для многократного выполнения набора инструкций
Условие
Конструкция для выполнения различных действий в зависимости от истинности условия
Функция
Подпрограмма, которая возвращает значение и может принимать параметры
Массив
Структура данных для хранения набора элементов одного типа
🧩 Основные алгоритмические конструкции
Линейный алгоритм
Последовательное выполнение команд без ветвлений и циклов
a = 5
b = 10
c = a + b
print(c)Ветвление (if-else)
Выполнение разных действий в зависимости от условия
if x > 0:
print("Положительное")
elif x < 0:
print("Отрицательное")
else:
print("Ноль")Циклы
Цикл for
Для известного количества повторений
for i in range(5):
print(i)Цикл while
Пока условие истинно
i = 0
while i < 5:
print(i)
i += 1🗃️ Структуры данных
Массивы (списки в Python)
Упорядоченная коллекция элементов
# Создание массива
arr = [1, 2, 3, 4, 5]
# Обращение к элементами
print(arr[0]) # Первый элемент
print(arr[-1]) # Последний элемент
# Изменение элемента
arr[2] = 10
# Длина массива
n = len(arr)Строки
Последовательность символов
s = "Hello, World!"
# Обращение к символам
print(s[0]) # 'H'
print(s[7:12]) # 'World'
# Длина строки
n = len(s)
# Методы строк
s_upper = s.upper()
s_lower = s.lower()Словари
Коллекция пар "ключ-значение"
# Создание словаря
student = {"name": "Иван", "age": 17, "grade": 11}
# Обращение к значениям
print(student["name"]) # "Иван"
# Добавление элемента
student["school"] = "Лицей №1"
# Проверка наличия ключа
if "age" in student:
print(student["age"])🔍 Основные алгоритмы
Линейный поиск
Поиск элемента в массиве перебором всех элементов
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1Сортировка пузырьком
Попарное сравнение и обмен соседних элементов
def bubble_sort(arr):
n = len(arr)
for i in range(n-1):
for j in range(n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]Бинарный поиск
Поиск в отсортированном массиве путем деления пополам
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: Анализ алгоритма
Задание: Что выведет программа?
s = 0
for i in range(1, 6):
s += i
print(s)Решение:
Программа вычисляет сумму чисел от 1 до 5: 1+2+3+4+5 = 15
Ответ: 15
Пример 2: Работа с массивом
Задание: Дан массив A = [3, 7, 2, 9, 1]. Что будет содержаться в A после выполнения программы?
for i in range(len(A)):
if A[i] % 2 == 0:
A[i] = A[i] * 2Решение:
Программа удваивает четные элементы массива: 2*2=4
Ответ: [3, 7, 4, 9, 1]
Пример 3: Рекурсия
Задание: Что вычисляет следующая функция?
def f(n):
if n == 0:
return 1
else:
return n * f(n-1)Решение:
Функция вычисляет факториал числа n: n! = n × (n-1) × ... × 1
Ответ: Факториал числа n
Пример 4: Алгоритмическая задача
Задание: Напишите функцию, которая проверяет, является ли строка палиндромом.
Решение:
def is_palindrome(s):
# Приводим к нижнему регистру и удаляем пробелы
s = s.lower().replace(" ", "")
# Сравниваем строку с ее обратной версией
return s == s[::-1]
# Пример использования
print(is_palindrome("А роза упала на лапу Азора")) # True
print(is_palindrome("Hello")) # False