Вася изучал сегодня ** информатике тему "Рекурсия". После урока ** доске осталась такая...

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;<br> if (n > 2){
f(n - 1);
f(n - 2);
}
}
Вася задумался над таким вопросом — а какое наименьшее натуральное число нужно поставить вместо n в вызов этой функции, чтобы было напечатано не меньше 2017 звездочек? Помогите ему узнать ответ на этот вопрос.
В качестве ответа укажите одно натуральное число.

Answer 1

Ищем закономерность.
f(1) = f(2) = 1 звездочка
f(n) = 1 + f(n-1) + f(n-2) звездочек, n > 2

Составляем программку для подсчета
--haskell
main :: IO ()
f(1) = 1
f(2) = 1
f(n) = 1 + f(n-1) + f(n-2)
main = print([(x, f(x)) | x <- [1, 2 .. 20]])<br>
И получаем такой вывод
[(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)]

(16,1973),(17,3193) - т.е. 16 мало, а 17 уже достаточно
Ответ 17