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

Дан рекурсивный алгоритм F.

procedure F(n: integer);
begin
  writeln (‘*’);
  if $$n > 0$$ then begin
    F($$n-3$$);
    F($$n \mathbin{\mathrm{div}} 2$$);
  end
end.

Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова $$F(7)$$?

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

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

$$S(n)=1+S(n-3)+S(n \div 2)$$ при $$n>0$$.

Для значений $$n \le 0$$ рекурсивные вызовы не выполняются, поэтому:

$$S(n)=1$$.

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

• $$S(1)=1+S(-2)+S(0)=1+1+1=3$$
• $$S(2)=1+S(-1)+S(1)=1+1+3=5$$
• $$S(3)=1+S(0)+S(1)=1+1+3=5$$
• $$S(4)=1+S(1)+S(2)=1+3+5=9$$
• $$S(5)=1+S(2)+S(2)=1+5+5=11$$
• $$S(6)=1+S(3)+S(3)=1+5+5=11$$
• $$S(7)=1+S(4)+S(3)=1+9+5=15$$

Значит, при вызове $$F(7)$$ будет напечатано 15 звёздочек.

Ответ

15