Question

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

Чему равно значение функции F(6)? В ответе запишите только натуральное число.

Accepted Answer

32

Answer

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

Заполним таблицу значений, начиная с базовых случаев:

| n | F(n) |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | F(2) · F(1) = 2 · 1 = 2 |
| 4 | F(3) · F(2) = 2 · 2 = 4 |
| 5 | F(4) · F(3) = 4 · 2 = 8 |
| 6 | F(5) · F(4) = 8 · 4 = 32 |

Проверим вычисление с помощью программы:

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

print(F(6))
```

Программа выведет 32.

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