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

Информатика (Рекурсивные алгоритмы)

1 2 3 4 5 6 7 8 9 10

Вопрос 11

Ниже записаны две рекурсивные функции, F и G:

function F(n: integer): integer;

begin

if (n > 2) then F := F(n - 1) + G(n - 1) + F(n-2)

else

F := n;

end;

function G(n: integer): integer;

begin

if (n > 2) then G := G(n - 1) + F(n - 1) + G(n-2)

else

G := n;

end;

Чему будет равно значение, вычисленное при выполнении вызова F(5)?

Заметили ошибку в тексте?
Выделите её и нажмите Ctrl + Enter

Промоделируем работу программы: F(5) = F(4) + G(4) + F(3).

F(4) = F(3) + G(3) + F(2)

F(3) = F(2) + G(2) + F(1)

F(2) = 2

F(1) = 1

G(4) = G(3) + F(3) + G(2)

G(3) = G(2) + F(2) + G(1)

G(2) = 2

G(1) = 1

Теперь можно подсчитать G(3) и F(3): G(3) = 1 + 2 + 2 = 5; F(3) = 2 + 2 + 1 = 5.

Найдём значение G(4) и F(4): G(4) = 5 + 5 + 2 = 12; F(4) = 5 + 5 + 2 = 12.

Таким образом, F(5) = 12 + 12 + 5 = 29.