Задание 3 Вариант 3 Самостоятельная работа 6 ГДЗ Рабочая тетрадь Босова 11 класс (Информатика)

procedure F(n: integer);
begin
writein (‘*’);
if n > 0 then
begin
F(n-2);
F (n div 2);
F(n div 2);
end
end.
Ответ: 34

Обозначим через $$F(n)$$ количество символов *, которые будут напечатаны при вызове процедуры $$F(n)$$.

По условию каждый вызов печатает одну звёздочку, а если $$n > 0$$, то дополнительно выполняются три рекурсивных вызова:

$$F(n)=1+F(n-2)+2\cdot F\left(\left\lfloor \frac{n}{2}\right\rfloor\right)$$

Вычислим последовательно:

$$F(1)=1+F(-1)+2F(0)$$

Так как при $$n \le 0$$ рекурсия не продолжается, получаем:

$$F(0)=1,\quad F(-1)=1$$

Тогда

$$F(1)=1+1+2\cdot 1=4$$

$$F(2)=1+F(0)+2F(1)=1+1+2\cdot 4=10$$

$$F(3)=1+F(1)+2F(1)=1+4+2\cdot 4=13$$

$$F(4)=1+F(2)+2F(2)=1+10+2\cdot 10=31$$

$$F(5)=1+F(3)+2F(2)=1+13+2\cdot 10=34$$

Ответ

34