Задание 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 ) ,$ если n > 2 и при этом n чётно.
Чему равно значение функции F(39)?

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

41518080

Пояснение

Решение:

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

Первые значения: $F(3) = F(2) - F(1) = 0$ , $F(4) = F(1) + F(2) + F(3) = 2$ , $F(5) = F(4) - F(3) = 2$ , $F(6) = 1 + 1 + 0 + 2 + 2 = 6$ , $F(7) = 6 - 2 = 4$ , $F(8) = 16$ . Видно, что напрямую «в лоб» рекурсию писать не стоит: чётная ветвь заново пересчитывает всю историю, поэтому либо заполняем массив снизу вверх, либо кэшируем результаты.

Продолжая таблицу до $n = 39$ , получаем $F(39) = 41518080$ .

F = [0] * 40
F[0] = F[1] = F[2] = 1
for n in range(3, 40):
    if n % 2 == 1:
        F[n] = F[n - 1] - F[n - 2]
    else:
        F[n] = sum(F[1:n])
print(F[39])   # 41518080

Ответ: 41518080