27баллов!!! Дан рекурсивный алгоритм: procedure F(n: integer); begin writeln('*'); if n >...

Question

27баллов!!!

Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*');
if n > 0 then begin
F(n-2);
F(n div 2)
end
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?

Answer 1

Пусть K(n) - количество звездочек, напечатанных при вызове F(n)
Тогда
K(n) = 1 { writeln('*') } + K(n-2) {вызов F(n-2) -> печатается еще K(n-2) звездочек} + K(n div 2) {F(n div 2)} при n > 0
и K(n) = 1 при n <= 0<br>
Требуется найти K(7)

K(7) = 1 + K(5) + K(3)
K(5) = 1 + K(3) + K(2)
K(3) = 1 + K(1) + K(1)
K(2) = 1 + K(0) + K(1)
K(1) = 1 + K(-1) + K(0)
K(0) = K(-1) = 1 {0, -1 <= 0}<br>
K(1) = 1 + 1 + 1 = 3
K(2) = 1 + 1 + 3 = 5
K(3) = 1 + 3 + 3 = 7
K(5) = 1 + 7 + 5 = 13
K(7) = 1 + 13 + 7 = 21

Ответ: 21