Задание 16 ЕГЭ по информатике · 9DAE40
Количество звёздочек при взаимной рекурсииПовышеннаяКЭС 3.7КЭС 3.16
Ниже приведены две рекурсивные функции F и G на языке Python.
Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(18)?
def F(n):
if n > 0:
G(n - 1)
def G(n):
print("*")
if n > 1:
F(n - 3)Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(18)?
Показать ответ
5
Подсказки (3)
- Сколько звёздочек печатает один вызов G? При каком условии после этого вызывается F?
- Для n>2 число звёздочек при вызове F(n) удовлетворяет рекуррентному соотношению f(n)=1+f(n−4).
- Последовательно уменьшайте аргумент F: 18→14→10→6→2. При n=2 функция F вызывает G, которая печатает одну звёздочку и больше рекурсивных вызовов не делает.
Решение
1. Вызов F(n) при n>0 передаёт управление функции G(n − 1). Функция G всегда печатает одну звёздочку. f(n)=1+f(n−4),n>2 2. После вызова F(18) цепочка рекурсивных вызовов имеет аргументы: 18→14→10→6→2 3. При F(2) вызывается G(1), которая печатает звёздочку. Условие n>1 для G(1) не выполняется, поэтому дальнейших вызовов нет. f(2)=1 4. Суммируем по одному напечатанному символу на каждом уровне рекурсии. f(18)=1+f(14)=1+1+f(10)=1+1+1+f(6)=1+1+1+1+f(2)=5
Частые ошибки
- Учитывают только вызов G(1), забывая о звёздочках, напечатанных на предыдущих уровнях.
- Уменьшают аргумент F на 3, хотя сначала F вызывает G с аргументом n − 1, а затем G вызывает F с аргументом n − 3; общий шаг равен 4.
- Считают, что G печатает звёздочку только при условии n>1.
Источник: Открытый банк ФИПИ
Похожие задания
16Ниже приведены две рекурсивные функции F и G на языке Python. def F(n): if n > 0: G(n - 3) def G(n)…Количество звёздочек при взаимной рекурсии · 0D4EB516Ниже приведены две рекурсивные функции F и G на языке Python. def F(n): if n > 0: G(n - 2) def G(n)…Количество звёздочек при взаимной рекурсии · 2778CC16Ниже приведены две рекурсивные функции F и G на языке Python. def F(n): if n > 0: G(n - 1) def G(n)…Количество звёздочек при взаимной рекурсии · 4ADA7816Ниже приведены две рекурсивные функции F и G на языке Python. def F(n): if n > 0: G(n - 2) def G(n)…Количество звёздочек при взаимной рекурсии · A2BE0016Ниже приведены две рекурсивные функции F и G на языке Python. def F(n): if n > 0: G(n - 1) def G(n)…Количество звёздочек при взаимной рекурсии · C0539216Алгоритм вычисления значения функции F(n) , где n – целое число, задан следующими соотношениями: F(n) = 1 при…Значение функции или выражения
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.