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

Answer 1

Количество напечатанных "*":
f(1) - 1
f(2) - 1
f(3) - 3
f(4) - 5
f(5) - 9
Следующие значения можно вычислять, используя закономерность:
f(6) - 15 = 9+(9-3) = 9+6 = 15
f(7) - 25 = 15+(15-5) = 15+10 = 25
f(8) - 41 = 25+(25-9) = 25+16 = 41
f(9) - 41+(41-15) = 67
f(10) - 67+(67-25) = 109
f(11) - 109+(109-41) = 177
f(12) - 177+(177-67) = 287
f(13) - 287+(287-109) = 465
f(14) - 465+(465-177) = 753
f(15) - 753+(753-287) = 1219
f(16) - 1219+(1219-465) = 1973
Ответ: 16

Answer 2

Для решения этой задачи, необходимо понять, как работает данная рекурсивная функция и определить, при каком значении n будет напечатано не менее 1550 звездочек.

Функция f(n) печатает звездочку и затем вызывает себя дважды, с аргументами n-1 и n-2. Таким образом, каждый вызов функции f(n) порождает два вызова f(n-1) и f(n-2).

Чтобы определить, при каком значении n будет напечатано не менее 1550 звездочек, можно использовать подход "сверху вниз" и просмотреть значения функции f(n) для различных значений n.

Начнем с n = 1. В этом случае функция f(1) напечатает одну звездочку.

Далее, при n = 2, функция f(2) напечатает одну звездочку и вызовет f(1) и f(0). Оба вызова f(1) напечатают по одной звездочке. Таким образом, при n = 2, будет напечатано 3 звездочки.

При n = 3, функция f(3) напечатает одну звездочку и вызовет f(2) и f(1). Как мы уже выяснили, f(2) напечатает 3 звездочки, а f(1) - одну звездочку. Таким образом, при n = 3, будет напечатано 5 звездочек.

Продолжая этот процесс, мы можем вычислить значения функции f(n) для различных значений n:

n = 1: 1 звездочка n = 2: 3 звездочки n = 3: 5 звездочек n = 4: 9 звездочек n = 5: 15 звездочек n = 6: 25 звездочек n = 7: 41 звездочка n = 8: 67 звездочек n = 9: 109 звездочек n = 10: 177 звездочек

Мы видим, что количество звездочек, которое будет напечатано, увеличивается с каждым следующим значением n. Чтобы найти наименьшее значение n, при котором будет напечатано не менее 1550 звездочек, мы можем продолжать вычислять значения функции f(n) до тех пор, пока не достигнем значения, большего или равного 1550.

Последовательное вычисление значений функции f(n) позволяет нам найти, что при n = 10 будет напечатано 177 звездочек. Однако, это значение недостаточно, чтобы превысить 1550 звездочек.

Продолжая вычисления, мы находим, что при n = 14 будет напечатано 1,471 звездочек, а при n = 15 уже 2,377 звездочек. Таким образом, наименьшее натуральное число, которое нужно поставить вместо n в вызов этой функции, чтобы было напечатано не менее 1550 звездочек, равно 15.

Ответ: 15.