Ниже на пяти языках программирования записаны рекурсивные функции F и G.
| Бейсик | Python |
|---|---|
FUNCTION F(n) IF n > 2 THEN F = F(n-1)+G(n-1)+F(n-2) ELSE F = n END IF END FUNCTION FUNCTION G(n) IF n > 2 THEN G = G(n-1)+F(n-1)+G(n-2) ELSE G = 3-n END IF END FUNCTION
| def F(n): if n > 2: return F(n-1)+G(n-1)+F(n-2) else: return n def G(n): if n > 2: return G(n-1)+F(n-1)+G(n-2) else: return 3-n
|
| Алгоритмический язык | Паскаль |
алг цел F(цел n) нач если n > 2 то знач := F(n-1)+G(n-1)+F(n-2) иначе знач := n все кон алг цел G(цел n) нач если n > 2 то знач := G(n-1)+F(n-1)+G(n-2) иначе знач := 3-n все кон | 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 := 3-n; end; |
| Си | |
int F(int n){ if (n > 2) return F(n-1)+G(n-1)+F(n-2); else return n; } int G(int n){ if (n > 2) return G(n-1)+F(n-1)+G(n-2); else return 3-n; }
| |
Чему будет равно значение, вычисленное при выполнении вызова F(5)?
Промоделируем работу программы: 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) = 1
G(1) = 2
Теперь можно подсчитать G(3) и F(3): G(3) = 1 + 2 + 2 = 5; F(3) = 2 + 1 + 1 = 4.
Найдём значение G(4) и F(4): G(4) = 5 + 4 + 1 = 10; F(4) = 4 + 5 + 2 = 11.
Таким образом, F(5) = 11 + 10 + 4 = 25.
Ответ: 25.