Вася изучал сегодня на информатике тему "Рекурсия". После урока на доске осталась такая функция (для условия на языке Pascal — процедура): на языке Python: def f(n): print('*') if n больше 2: f(n - 1) f(n - 2) на языке...
Вася изучал сегодня на информатике тему "Рекурсия". После урока на доске осталась такая функция (для условия на языке 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 звездочек? Помогите ему узнать ответ на этот вопрос.
В качестве ответа укажите одно натуральное число.
Гость
Ответ(ы) на вопрос:
Гостьочевидно что звездочек
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
Не нашли ответ?
Похожие вопросы