Question

Функция $F(n)$ для целого неотрицательного числа $n$ определена следующим образом:

- $F(n) = 0$ при $n \leq 1$;
- $F(n) = F(n-1) + 3n^2$ если $n > 1$ и $n$ нечётно;
- $F(n) = \frac{n}{2} + F(n-1) + 2$ если $n > 1$ и $n$ чётно.

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

Accepted Answer

62820

Answer

Идея решения: вычислить функцию рекурсивно, следуя определению, либо заполнить таблицу значений от $n = 0$ до $n = 49$.

Реализуем рекурсивное вычисление на Python:

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

print(F(49))
```

Проследим вычисление для небольших значений:

| $n$ | Условие | $F(n)$ |
|---|---|---|
| 0 | $n \leq 1$ | 0 |
| 1 | $n \leq 1$ | 0 |
| 2 | чётно | $2 // 2 + F(1) + 2 = 1 + 0 + 2 = 3$ |
| 3 | нечётно | $F(2) + 3 \cdot 3^2 = 3 + 27 = 30$ |
| 4 | чётно | $4 // 2 + F(3) + 2 = 2 + 30 + 2 = 34$ |
| 5 | нечётно | $F(4) + 3 \cdot 5^2 = 34 + 75 = 109$ |

Продолжая вычисления до $n = 49$, получаем результат.

Альтернативно, можно использовать мемоизацию для ускорения:

```python
from functools import lru_cache

@lru_cache(None)
def F(n):
    if n <= 1:
        return 0
    if n % 2 == 1:
        return F(n - 1) + 3 * n * n
    return n // 2 + F(n - 1) + 2

print(F(49))
```

Программа выводит: **62820**

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