Question

Функция F(n), где n — натуральное число, определяется следующим образом:
- F(n) = n при n ≤ 2
- F(n) = 3 · F(n − 1) − F(n − 2) при n > 2

Найдите значение F(6).

Accepted Answer

89

Answer

Идея решения: вычислить значения функции последовательно, используя рекуррентное соотношение.

Заполним таблицу значений:

| n | F(n) |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 · 2 − 1 = 5 |
| 4 | 3 · 5 − 2 = 13 |
| 5 | 3 · 13 − 5 = 34 |
| 6 | 3 · 34 − 13 = 89 |

Вычисления:
- F(1) = 1 (база)
- F(2) = 2 (база)
- F(3) = 3 · F(2) − F(1) = 3 · 2 − 1 = 5
- F(4) = 3 · F(3) − F(2) = 3 · 5 − 2 = 13
- F(5) = 3 · F(4) − F(3) = 3 · 13 − 5 = 34
- F(6) = 3 · F(5) − F(4) = 3 · 34 − 13 = 102 − 13 = 89

Проверка через программу:

```python
def F(n):
    if n <= 2:
        return n
    return 3 * F(n - 1) - F(n - 2)

print(F(6))
```

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