Question

Вася изучал сегодня на информатике тему "рекурсия". после урока на доске осталась такая функция (для условия на языке pascal — процедура): на языке python: def f(n): print('*') if n > 2: f(n - 1) f(n - 2) на языке pascal: procedure f(n: longint); begin writeln('*'); if n > 2 then begin f(n - 1); f(n - 2); end; end; на языке c++: int f(int n){ cout < < '*' < < endl; if (n > 2){ f(n - 1); f(n - 2); } } вася задумался над таким вопросом — а какое наименьшее натуральное число нужно поставить вместо n в вызов этой функции, чтобы было напечатано не меньше 5000 звездочек? ему узнать ответ на этот вопрос. в качестве ответа укажите одно натуральное число.

Answer 1

Очевидно что звездочек
f(1) = 1
f(2) = 1
f(3) = 1 + f(2) + f(1)

f(n) = 1 + f(n-1) + f(n-2)

Посчитаем на хаскеле f(n) при n=[1,2..20]
--Код haskell
f(1) = 1
f(2) = 1
f(n) = 1 + f(n-1) + f(n-2)
main = print(show [(n, f(n)) | n <- [1,2..20]])

Вывод
(1,1),(2,1),(3,3),(4,5),(5,9),(6,15),(7,25),(8,41),(9,67),(10,109),(11,177),(12,287),(13,465),(14,753),(15,1219),(16,1973),(17,3193),(18,5167),(19,8361),(20,13529)

значит при f(18) = 5167  - т0 что надо

ответ 18