Задание 7 Параграф 9 ГДЗ Босова 11 класс (Информатика)

Задача

Алгоритм вычисления значения функции $$F(n)$$, где $$n$$ — натуральное число, задан следующими соотношениями:
$$F(n)=2 \text{ при } n\le 0;$$
$$F(n)=F(n-2)+F(n-1)+F(n\mathbin{\mathrm{div}}2) \text{ при } n>0.$$
Требуется выяснить, чему равно значение функции $$F(10)$$.

Подробный ответ

Вычислим значения функции по рекуррентной формуле:

$$F(n)=2 \text{ при } n \le 0,$$

$$F(n)=F(n-2)+F(n-1)+F(n \, div \, 2) \text{ при } n>0.$$

Найдём несколько первых значений:

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

$$F(2)=F(0)+F(1)+F(1)=2+6+6=14,$$

$$F(3)=F(1)+F(2)+F(1)=6+14+6=26.$$

Далее последовательно вычисляем значения до $$F(10)$$. Удобнее всего это сделать с помощью программы:

program Z_9_7;
function F(m: integer): integer;
begin
  if m <= 0 then F := 2
  else F := F(m — 2) + F(m — 1) + F(m div 2)
end;
var
  n: integer;
begin
  read(n);
  Write(F(n))
end.

По вычислению получаем:

$$F(10)=1486.$$