Как из кирпичей строят здание, так из базовых структур собирают любой алгоритм. Разберём эти структуры.
Чему ты научишься. различать три базовые алгоритмические структуры — следование, ветвление, цикл — и понимать, что такое рекурсия.
Три базовые структуры и рекурсия
Любой алгоритм строится из трёх алгоритмических структур:
АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ: ПОСЛЕДОВАТЕЛЬНАЯ шаги друг за другом [1]→[2]→[3] ВЕТВЯЩАЯСЯ выбор по условию <усл?> да/нет → разные шаги ЦИКЛИЧЕСКАЯ повтор, пока верно усл. ↺ тело цикла
Особый приём — рекурсия: алгоритм (функция) вызывает сам себя для решения такой же, но меньшей подзадачи (например, факториал n! = n · (n−1)!). Рекурсия обязательно должна иметь условие остановки.
Контрольный вопрос. Структура, в которой действие выбирается в зависимости от условия, называется…
Подсказка: Да/нет.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Структура, в которой шаги выполняются один за другим по порядку, без выбора и без повторов, называется ______. Впиши слово.
Подсказка: Самая простая из трёх — просто по порядку.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Из скольких базовых алгоритмических структур собирается любой алгоритм?
Подсказка: Их перечисляет схема в начале урока.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Что ОБЯЗАТЕЛЬНО должно быть у рекурсии, чтобы она не работала бесконечно?
Подсказка: Иначе функция будет вызывать сама себя без конца.
Онлайн-проверка ответа появится позже
Контрольный вопрос. n! = n · (n−1)! — пример вычисления, где функция вызывает саму себя для меньшей подзадачи. Это называется ______. Впиши слово.
Подсказка: Функция здесь ссылается сама на себя в правой части равенства.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Структура, в которой действия повторяются, пока верно условие, называется…
Подсказка: Повтор.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Приём, когда функция вызывает сама себя для меньшей подзадачи, — это…
Подсказка: Например, факториал.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Алгоритм звучит так: «Пока в корзине есть яблоки — бери одно и клади в пакет». Какая это структура?
Подсказка: Слово «Пока» означает повтор действия, пока условие верно.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Алгоритм факториала звучит так: «если n=0, вернуть 1; иначе вернуть n, умноженное на факториал(n−1)». Какие ДВЕ структуры одновременно использованы здесь?
Подсказка: Есть проверка условия («если n=0») и функция вызывает сама себя.
Онлайн-проверка ответа появится позже
Задание. Опиши словесно (без кода) алгоритм проверки, является ли число чётным, используя ветвящуюся структуру (если/иначе).
1) Опиши этот алгоритм минимум в 3 шагах.
2) Измени его так, чтобы он проверял чётность для СПИСКА из 5 чисел подряд, используя циклическую структуру — опиши, что повторяется и при каком условии цикл останавливается.
3) Объясни, почему для этой задачи (проверка чётности одного числа) НЕ нужна рекурсия.Подсказка: Ветвление — выбор по условию (чётное/нечётное); цикл — повтор для каждого из 5 чисел; рекурсия нужна, когда задача сводится к себе же меньшего размера.
Онлайн-проверка ответа появится позже
Итог. Любой алгоритм собирается из трёх структур: последовательной (шаги друг за другом), ветвящейся (выбор по условию) и циклической (повтор, пока верно условие). Особый приём — рекурсия, когда функция вызывает сама себя для меньшей подзадачи и обязательно имеет условие остановки.
Что дальше
Эти структуры записывают на языке программирования. О записи алгоритмов следующий урок.
