Глава о том, как одну и ту же задачу решают разными алгоритмами и почему это не всё равно. Плюс рекурсия — приём, где алгоритм вызывает сам себя и обязан уметь остановиться.
Что нужно знать
- Сортировка обменом («пузырьком») сравнивает СОСЕДНИЕ элементы и меняет их местами, если порядок нарушен.
- За один проход наибольший элемент оказывается в конце; всего нужно не более n − 1 прохода.
- Сортировка выбором находит наименьший элемент в неотсортированной части и ставит его на очередное место.
- В отсортированном массиве работает двоичный поиск: он делит область поиска пополам и находит элемент примерно за $\log_2 n$ шагов.
- Вспомогательный алгоритм оформляют подпрограммой и вызывают из основного столько раз, сколько нужно.
- Рекурсия — вызов алгоритма самим собой; она обязана содержать условие выхода, иначе вызовы не кончатся.
- Каждый незавершённый рекурсивный вызов занимает память, поэтому глубина рекурсии не бесконечна.
Где чаще всего ошибаются
- Пишут рекурсию без условия выхода — программа падает по переполнению стека, а не зависает.
- Применяют двоичный поиск к неотсортированному массиву и получают «не найдено» для существующего элемента.
- В сортировке обменом сравнивают элемент с первым, а не с соседним.
- Считают, что перестановка элементов возможна без третьей переменной для хранения.
Проверить себя
По этой же главе есть проверочная работа из 11 заданий на 25 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Информатика · 11 класс · Босова, 2023 · Алгоритмы и элементы программирования