Question

Даны две взаимно рекурсивные функции:

```pascal
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).

Accepted Answer

29

Answer

Идея решения: вычислить значения обеих функций для аргументов от 1 до 5, используя рекуррентные соотношения и базовые случаи.

Сначала определим базовые значения (при $n \leq 2$):
- $F(1) = 1$, $F(2) = 2$
- $G(1) = 1$, $G(2) = 2$

Вычислим значения для $n = 3$:
- $F(3) = F(2) + G(2) + F(1) = 2 + 2 + 1 = 5$
- $G(3) = G(2) + F(2) + G(1) = 2 + 2 + 1 = 5$

Вычислим значения для $n = 4$:
- $F(4) = F(3) + G(3) + F(2) = 5 + 5 + 2 = 12$
- $G(4) = G(3) + F(3) + G(2) = 5 + 5 + 2 = 12$

Вычислим значение для $n = 5$:
- $F(5) = F(4) + G(4) + F(3) = 12 + 12 + 5 = 29$

Таблица значений:

| $n$ | $F(n)$ | $G(n)$ |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 5 | 5 |
| 4 | 12 | 12 |
| 5 | 29 | 29 |

Задание №16Алгоритмы и исполнителиЕГЭ по информатике