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

Answer 2

сейчас бы удалять чужое решение, также посчитанное с помощью компа, и вставлять свое, которое ничуть не лучше... дибилизм чистой воды.

Answer 3

если бы вы выложили код которым это посчитали - тогда без проблем, или любое другое обоснование кроме голого ответа