Задание 16

Вычисление рекуррентных выражений · 26 заданий

Задание №16
№16
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n × F(n − 1), если n…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n × F(n − 1), если n…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n + F(n − 1), если n…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = 1 при n = 2; F (n) =…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = 1 при n = 2; F (n) =…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = 2 при n = 2; F(n) = n…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями: F(n) = 1 при n < 3; F(n) = F(n − 1) +…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n · F (n - 1), если n…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n² + F (n - 1), если…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями: F(n) = 1, если n <= 1; F(n) = 3 + F (n…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = 2 при n = 2; F(n) = n…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n + 2 · F (n - 1), ес…
Рекурсия

Задание №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