Вася изучал сейчас на информатике тему "Рекурсия". После урока на дощечке
Вася изучал сейчас на информатике тему "Рекурсия". После урока на дощечке осталась такая функция (для условия на языке Pascal процедура):
на языке Python:
def f(n):
print('*')
if n gt; 2:
f(n - 1)
f(n - 2)
на языке Pascal:
procedure f(n: longint);
begin
writeln('*');
if n gt; 2 then begin
f(n - 1);
f(n - 2);
end;
end;
на языке C++:
int f(int n)
cout lt;lt; '*' lt;lt; endl;
if (n gt; 2)
f(n - 1);
f(n - 2);
Вася задумался над таким вопросом а какое меньшее натуральное число необходимо поставить вместо n в вызов этой функции, чтобы было написано не меньше 1500 звездочек? Помогите ему выяснить ответ на этот вопрос.
В качестве ответа укажите одно натуральное число.
Так как f(n) всегда выводит 1 звёздочку, а если если n gt; 2 - то вызывает f(n - 1) и f(n - 2), то
*(n) = 1 при n lt;= 2
*(n) = 1 + *(n - 1) + *(n - 2) при n gt; 2.
*(1) = *(2) = 1
*(3) = 1 + *(2) + *(1) = 1 + 1 + 1 = 3
*(4) = 1 + *(3) + *(2) = 1 + 3 + 1 = 5
*(5) = 1 + 5 + 3 = 9
*(6) = 1 + 9 + 5 = 15
*(7) = 1 + 15 + 9 = 25
*(8) = 1 + 25 + 15 = 41
*(9) = 1 + 41 + 25 = 67
*(10) = 1 + 67 + 41 = 109
*(11) = 1 + 109 + 67 = 177
*(12) = 1 + 177 + 109 = 287
*(13) = 1 + 287 + 177 = 465
*(14) = 1 + 465 + 287 = 753
*(15) = 1 + 753 + 465 = 1219
*(16) = 1 + 1219 + 753 = 1973 gt;= 1500
Ответ: 16.
Можно было заметить, что *(n) = 2F(n) - 1, где F(n) - число Фибоначчи, либо просто исполнять программку для различных n.
-
Вопросы ответы
Статьи
Информатика
Статьи
Химия.
Русский язык.
Геометрия.
Физика.
Русский язык.
Химия.
Математика.
География.
Литература.
Разные вопросы.