Дана рекурсивная функция: , если ; иначе . Определите верные утверждения о вычислении этой функции.
Показать ответ и разборСкрыть ответ и разбор
Верный ответ
- Aвычисление f(5) требует 7 вызовов функции f, включая первый
- Df(6) возвращает 7
- Fпри вычислении f(6) функция вызывается с аргументом 2 ровно три раза
Разбор
Базовые значения: f(0)=0, f(1)=1, f(2)=2. Далее: f(3)=f(2)+f(0)=2, f(4)=f(3)+f(1)=3, f(5)=f(4)+f(2)=5, f(6)=f(5)+f(3)=7, f(7)=f(6)+f(4)=10. Значит, «f(6) возвращает 7» верно, а «f(7) возвращает 11» неверно. Число вызовов K(n) для n>2 равно 1+K(n-1)+K(n-3), а K(0)=K(1)=K(2)=1: K(3)=3, K(4)=5, K(5)=7. Поэтому для f(5) нужно 7 вызовов (верно), а для f(4) их 5, не 4 (неверно). Самая длинная цепочка вложенных вызовов идёт через n-1: f(6), f(5), f(4), f(3), f(2), то есть глубина 5, а не 6. Аргумент 2 при вычислении f(6): f(6) вызывает f(5) и f(3); f(5) вызывает f(4) и f(2); f(4) вызывает f(3) и f(1); оба вызова f(3) (из f(6) и из f(4)) порождают по одному f(2). Итого f(2) вызывается трижды (из f(5) и из двух f(3)), утверждение верно. Верные: «f(6) возвращает 7», «вычисление f(5) требует 7 вызовов функции f, включая первый», «при вычислении f(6) функция вызывается с аргументом 2 ровно три раза».