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

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 в вызов этой функции, чтобы было напечатано не меньше 5000 звездочек? Помогите ему узнать ответ на этот вопрос.
В качестве ответа укажите одно натуральное число.

Comments

18

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]])<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)

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

Ответ 18

Comments

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

---

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

---

Вас не смущает, что в тексте задания написан код для подсчета? Или знаменитая женская логика в действии?

---

Этот код не считает звездочки а выводит.

---

Еще раз повторяю, ваш ответ был удален изза отсутствия решения, объяснения как именно решали. Ответ должен содержать решение, если его можно написать, это указано в правилах, которые вы принимали при регистрации