Рекурсия — информатика 10 класс: рекурсивные функции и алгоритмы — тренажёр
Тренировка по теме «Рекурсия — информатика 10 класс: рекурсивные функции и алгоритмы»: задачи с меняющимися числами, мгновенная проверка, подсказка и подробный разбор к каждой. Ниже — шпаргалка по теме, разобранные примеры и ответы на частые вопросы.
Тренировка
0/81 Функция F определена правилом: F(1) = 2, при n больше 1 — F(n) = F(n - 1) + 3. Сколько вызовов произойдёт при вычислении F(7)? Считай от 7 вниз до базового значения.
Выбери ответ и нажми «Проверить». Подсказка рядом — пользоваться не стыдно.
Разбор примеров из тренажёра
9 задач из пула этого тренажёра с полной логикой решения: условие, подсказка, как решать и ответ. В самом тренажёре числа в каждой задаче обновляются от раунда к раунду — принцип решения остаётся тем же.
Пример 1. Функция F определена правилом: F(1) = 2, при n больше 1 — F(n) = F(n - 1) + 3. Сколько вызовов произойдёт при вычислении F(11)? Считай от 11 вниз до базового значения.
Подсказка. Считай числа от a до единицы.
Как решать. Цепочка вызовов идёт от 11 до 1: 11 вызовов, и стек вырастает до глубины 11.
Ответ: 11
Пример 2. Рекурсивный обход диска нашёл 3 подпапок, в каждой по 10 файлов. Сколько файлов увидит функция при полном обходе?
Подсказка. Умножь подпапки на файлы.
Как решать. 3 подпапок по 10 файлов в каждой: 3 · 10. Рекурсия спускается в каждую подпапку и суммирует результат.
Ответ: 30
Пример 3. Как называется стопка незакрытых вызовов функции в памяти программы? Запиши два слова.
Как решать. Стек вызовов хранит кадры: параметры и адрес возврата каждого незакрытого вызова; переполнение стека роняет программу при слишком глубокой рекурсии.
Ответ: стек вызовов
Пример 4. Функция F определена правилом: F(1) = 2, при n больше 1 — F(n) = F(n - 1) + 3. Сколько вызовов произойдёт при вычислении F(6)? Считай от 6 вниз до базового значения.
Подсказка. Считай числа от a до единицы.
Как решать. Цепочка вызовов идёт от 6 до 1: 6 вызовов, и стек вырастает до глубины 6.
Ответ: 6
Пример 5. Рекурсивный обход диска нашёл 7 подпапок, в каждой по 12 файлов. Сколько файлов увидит функция при полном обходе?
Подсказка. Умножь подпапки на файлы.
Как решать. 7 подпапок по 12 файлов в каждой: 7 · 12. Рекурсия спускается в каждую подпапку и суммирует результат.
Ответ: 84
Пример 6. Функция F определена правилом: F(1) = 2, при n больше 1 — F(n) = F(n - 1) + 3. Сколько вызовов произойдёт при вычислении F(9)? Считай от 9 вниз до базового значения.
Подсказка. Считай числа от a до единицы.
Как решать. Цепочка вызовов идёт от 9 до 1: 9 вызовов, и стек вырастает до глубины 9.
Ответ: 9
Пример 7. Рекурсивный обход диска нашёл 5 подпапок, в каждой по 7 файлов. Сколько файлов увидит функция при полном обходе?
Подсказка. Умножь подпапки на файлы.
Как решать. 5 подпапок по 7 файлов в каждой: 5 · 7. Рекурсия спускается в каждую подпапку и суммирует результат.
Ответ: 35
Пример 8. Функция F определена правилом: F(1) = 2, при n больше 1 — F(n) = F(n - 1) + 3. Сколько вызовов произойдёт при вычислении F(12)? Считай от 12 вниз до базового значения.
Подсказка. Считай числа от a до единицы.
Как решать. Цепочка вызовов идёт от 12 до 1: 12 вызовов, и стек вырастает до глубины 12.
Ответ: 12
Пример 9. Рекурсивный обход диска нашёл 8 подпапок, в каждой по 11 файлов. Сколько файлов увидит функция при полном обходе?
Подсказка. Умножь подпапки на файлы.
Как решать. 8 подпапок по 11 файлов в каждой: 8 · 11. Рекурсия спускается в каждую подпапку и суммирует результат.
Ответ: 88
Вопросы для повторения темы
Контрольные вопросы по «Рекурсия — информатика 10 класс: рекурсивные функции и алгоритмы» с верными ответами и пояснениями — проверь себя до запуска тренажёра.
Вопрос 1. Рекурсивная функция уменьшает аргумент на 2 за вызов, базовый случай — аргумент 0. Сколько всего вызовов случится при старте с аргумента 10, считая стартовый?
Ответ: 6
Пояснение. Цепочка: 10, 8, 6, 4, 2, 0 — шесть вызовов, последний попадает в базовый случай.
Вопрос 2. Для какой задачи рекурсия подходит естественнее всего?
Ответ: обход папок с вложенными подпапками
Пояснение. Вложенность папок повторяет саму себя — структура задачи рекурсивна. Остальные задачи линейны, и цикл справляется проще.
Вопрос 3. Сумму цифр числа можно посчитать рекурсивно, отделяя по одной цифре.
Ответ: Верно
Пояснение. Базовый случай — однозначное число, шаг — последняя цифра плюс сумма цифр числа без неё.
Вопрос 4. Что верно про стек вызовов?
Ответ: каждый незакрытый вызов занимает в нём место; при слишком большой глубине происходит переполнение; кадр освобождается при возврате из функции
Пояснение. Стек — стопка кадров: вызов кладёт кадр, возврат снимает. Вечное хранение ответов — это уже запоминание, а не стек.
Вопрос 5. Расставь шаги рекурсивного решения по порядку.
Ответ: проверить базовый случай → выполнить рекурсивный шаг с меньшей задачей → получить ответ меньшей задачи → собрать итоговый ответ
Пояснение. Сначала проверка базы, затем шаг с вызовом, затем ответ от меньшей задачи и сборка итога.
Вопрос 6. Сопоставь термин и определение.
Пояснение. Терминология урока: две части любой рекурсии, память под вызовы и классический пример.
Вопрос 7. Разложи задачи: где рекурсия уместна, а где хватит цикла.
Пояснение. Ветвление и вложенность — территория рекурсии; линейные проходы по числам делает цикл без затрат на стек.
Настройте ритм перед экзаменом: задание дня по информатике — новое каждый день.