Задание №16 — Рекурсия

#69492Задание №16ФИПИ

Рекурсия

Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями:
F(n) = 1 при n < 3;
F(n) = F(n − 1) + F(n − 2), если n > 2 и при этом n нечётно;
F(n) = $\sum_{i = 1}^{n - 1} F ( i ) ,$ еcли n > 2 и при этом n чётно.
Чему равно значение функции F(24)?

Правильный ответ

887040

Пояснение

Решение:

База: $F(0) = F(1) = F(2) = 1$ . Для нечётных $n \gt 2$ значение считается как у чисел Фибоначчи, а для чётных $n \gt 2$ нужно сложить все предыдущие значения, начиная с $F(1)$ (нулевой член в сумму не входит).

Удобно вести таблицу и накапливать сумму $F(1) + F(2) + \dots$ :

$F(3) = F(2) + F(1) = 2$ ; $F(4) = F(1) + F(2) + F(3) = 1 + 1 + 2 = 4$ ; $F(5) = F(4) + F(3) = 6$ ; $F(6) = 1 + 1 + 2 + 4 + 6 = 14$ и так далее.

Заметим полезное упрощение: для чётного $n \gt 2$ сумма всех предыдущих равна $F(n-1) + \bigl(F(1) + \dots + F(n-2)\bigr) = F(n-1) + 2F(n-2)$ , потому что $n-2$ тоже чётно и $F(n-2)$ само является суммой $F(1) + \dots + F(n-3)$ . Это позволяет считать таблицу за один проход.

n	F(n)
1	1
2	1
3	2
4	4
5	6
6	14
7	20
8	48
9	68
10	164
11	232
12	560
13	792
14	1912
15	2704
16	6528
17	9232
18	22288
19	31520
20	76096
21	107616
22	259808
23	367424
24	887040

F = [0] * 25
F[0] = F[1] = F[2] = 1
for n in range(3, 25):
    if n % 2 == 1:
        F[n] = F[n - 1] + F[n - 2]
    else:
        F[n] = sum(F[1:n])

print(F[24])   # 887040

Ответ: 887040