Question

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

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

Accepted Answer

4122

Answer

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

Проанализируем определение функции. Для нечётных n значения образуют степени двойки: F(1) = 1 = $2^0$, F(3) = 2 · F(1) = $2^1$, F(5) = 2 · F(3) = $2^2$, и так далее. Следовательно, F(2k − 1) = $2^{k-1}$ для k ≥ 1.

Построим таблицу значений:

| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| F(n) | 1 | 3 | 2 | 7 | 4 | 11 | 8 | 19 | 16 | 29 |

| n | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
|---|---|---|---|---|---|---|---|---|---|---|
| F(n) | 32 | 53 | 64 | 79 | 128 | 147 | 256 | 275 | 512 | 531 |

| n | 21 | 22 | 23 | 24 | 25 | 26 |
|---|---|---|---|---|---|---|
| F(n) | 1024 | 1555 | 2048 | 2579 | 4096 | 4122 |

Вычисления:
- F(25) = 2 · F(23) = 2 · 2048 = 4096
- F(26) = 26 + F(25) = 26 + 4096 = 4122

Реализация на Python:

```python
def F(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return n + F(n - 1)
    if n % 2 != 0 and n > 1:
        return 2 * F(n - 2)

print(F(26))
```

Реализация на Паскале:

```pascal
var n: longint;

function F(n: longint): longint;
begin
    if n = 1 then
        F := 1
    else if (n mod 2) = 0 then
        F := n + F(n - 1)
    else if ((n mod 2) = 1) and (n > 1) then
        F := 2 * F(n - 2);
end;

begin
    n := F(26);
    writeln(n);
end.
```

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