Раздел «Компьютерное мышление» в спецификации НЦТ

Алгоритмы: функции, рекурсия, строки, файлы, сортировка, графы

Главное по теме

Функция объявляется def имя(параметры): и возвращает результат через return. Вызов: имя(аргументы).
Рекурсия: функция вызывает сама себя. Нужны условие остановки (база) и шаг, который к ней приближает.
Факториал: n! = n * (n-1)!, 0! = 1. 4! = 24, 5! = 120. Числа Фибоначчи: 1, 1, 2, 3, 5, 8, 13.
Строки: индексация с 0, срез s[a:b] берёт символы с a до b - 1. len(s), s.upper(), s.lower(), s.replace(), s.split(), s.find().
Файл: with open(имя, режим) as f. Режимы: r (чтение), w (запись с очисткой), a (дописывание). f.read(), f.readline(), f.write().
Сортировка пузырьком: сравниваем соседей и меняем местами, если порядок неверный. Сложность порядка n².
Бинарный поиск работает только в отсортированном списке и делит диапазон пополам: для 1000 элементов хватит не более 10 проверок, ведь 2¹⁰ = 1024.
Граф: вершины и рёбра. Степень вершины - число рёбер. Сумма степеней = удвоенному числу рёбер. Дерево из n вершин имеет n - 1 ребро.
Обход графа: в ширину (BFS, очередь), в глубину (DFS, стек или рекурсия). Хранение: матрица смежности или списки смежности.

Задания с разбором

1.Что выведет программа? s = "школа" print(s[1], len(s))

1Индексы начинаются с 0: ш=0, к=1, о=2.
2s[1] это буква «к».
3len(s) считает все буквы: их 5.

Ответ: к 5

2.Что выведет программа? def add(a, b): return a + b print(add(4, 3) * 2)

1Функция возвращает сумму аргументов: add(4, 3) = 7.
2Результат умножаем на 2.
37 · 2 = 14.

Ответ: 14

3.Что вернёт f(4)? def f(n): if n == 0: return 0 return n + f(n - 1)

1Раскрываем цепочку: f(4) = 4 + f(3) = 4 + 3 + f(2) = 4 + 3 + 2 + f(1).
2f(1) = 1 + f(0), а f(0) = 0: на этом рекурсия останавливается.
3Складываем: 4 + 3 + 2 + 1 + 0 = 10. Без условия n == 0 функция вызывала бы себя бесконечно.

Ответ: 10

Где теряют баллы

Python: строки и списки
Ловушка: Индексы считают с 1; срез s[1:3] считают включающим s[3].
Как решать: Индексы с 0, отрицательные с конца: s[-1] последний. Срез [a:b] берёт от a до b − 1. len() длина.
Функции и рекурсия
Ловушка: В рекурсии забывают базовый случай или считают вызовы на один меньше.
Как решать: Раскрой вызовы сверху вниз до базового случая, потом собери значения снизу вверх.
Алгоритмы: сортировка, поиск, графы
Ловушка: Двоичный поиск применяют к неотсортированному списку; кратчайший путь в графе считают по числу рёбер, а не по весам.
Как решать: Двоичный поиск: список отсортирован, каждый шаг делит пополам, до log₂n шагов. Кратчайший путь: сравни суммы весов всех вариантов.

Объяснение простыми словами

Представь, что ты часто готовишь одно и то же блюдо. Каждый раз писать весь рецепт заново неудобно, проще сказать «приготовь борщ» и всем всё понятно. В программировании так работают функции. Функция - это кусок кода с именем, который можно вызвать сколько угодно раз. В Python её объявляют так: def square(x): return x * x. После этого square(5) вернёт 25. Слово return отдаёт результат наружу. Параметр x это имя внутри определения, а число 5 при вызове это аргумент.

Переменные, которые ты создаёшь внутри функции, локальные: снаружи их не видно, и после завершения функции они исчезают. Это защищает от путаницы, ведь имя x в двух функциях это два разных x. Хорошая функция делает одно дело, имеет понятное имя и возвращает результат, а не печатает его. На ЕНТ часто встречается функция с условием: def f(a, b): если a больше b, то return a, иначе return b. Это максимум из двух чисел.

Дальше в Biik: продолжение объяснения, видеоразбор и проверка из 8 заданий по этой теме.

Доучи тему до конца в Biik

План на каждый день, видеоразборы, проверка из 8 заданий после каждой темы, пробник ЕНТ раз в месяц и ИИ-репетитор, который отвечает на вопросы. 3 дня бесплатно, без карты.

Начать бесплатно Пройти диагностику

Диагностика покажет, сколько баллов тебе не хватает до гранта и где именно. 30 заданий после короткой бесплатной регистрации.

Термины

Функция: Именованный блок кода, который можно вызывать много раз и который может возвращать результат.
Параметр и аргумент: Параметр - имя в определении функции, аргумент - значение, передаваемое при вызове.
return: Команда, которая завершает функцию и возвращает значение.
Локальная переменная: Переменная, существующая только внутри функции.
Рекурсия: Приём, когда функция вызывает сама себя для решения меньшей задачи.
Базовый случай: Простейший случай рекурсии, где функция уже не вызывает себя.
Факториал: Произведение всех натуральных чисел от 1 до n; 0! = 1.
Числа Фибоначчи: Последовательность 1, 1, 2, 3, 5, 8, ..., где каждое число равно сумме двух предыдущих.
Строка: Последовательность символов; элементы нумеруются с нуля.
Срез: Выборка части строки или списка: s[a:b] даёт элементы с индексами от a до b - 1.
Метод строки: Функция, вызываемая у строки: upper(), lower(), replace(), split(), find().
split и join: split разбивает строку на список по разделителю, join собирает список в строку.
Режим открытия файла: r чтение, w запись с очисткой, a дозапись.
with open: Конструкция, которая открывает файл и сама закрывает его после работы.
Сортировка: Упорядочивание элементов по возрастанию или убыванию.
Сортировка пузырьком: Метод, который многократно сравнивает соседние элементы и меняет их местами.
Сортировка выбором: Метод, который находит минимум и ставит его на нужное место, потом повторяет для остатка.
Бинарный поиск: Поиск в отсортированном списке с делением диапазона пополам.
Граф: Набор вершин, соединённых рёбрами.
Степень вершины: Число рёбер, которые подходят к вершине.
Матрица смежности: Таблица, где единица на пересечении i и j означает ребро между вершинами.
Обход в ширину и в глубину: Два способа обойти граф: BFS по уровням с очередью, DFS вглубь с возвратом.
Дерево: Связный граф без циклов; у n вершин ровно n - 1 ребро.

Все темы: Информатика