Question

Дан рекурсивный алгоритм: 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

Требуется найти 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}

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