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

27баллов!!! Дан рекурсивный алгоритм: procedure F(n: integer); begin writeln('*'); if n > 0 then begin F(n-2); F(n div 2) end end; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
Гость
Ответ(ы) на вопрос:
Гость
Пусть 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
Не нашли ответ?
Ответить на вопрос
Похожие вопросы