Задание 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 = 1;
F(n) = 1 при n = 2;
$F ( n ) = 2 + F \left(n - 1\right) ,$ если n > 2 и при этом если n чётно;
$F ( n ) = 3 \cdot n + F \left(n - 2\right) ,$ если n > 2 и при этом n нечётно.
Чему равно значение функции F(43)?

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

1450

Пояснение

Решение:

Число 43 нечётное, поэтому работает правило $F(n) = 3n + F(n-2)$ : аргумент уменьшается на 2 и остаётся нечётным. Значит вся цепочка идёт только по нечётным числам, вплоть до $F(1) = 1$ , а правило для чётных $n$ не используется.

$F(43) = 3 \cdot 43 + F(41) = 3 \cdot 43 + 3 \cdot 41 + F(39) = \dots = 3 \cdot (43 + 41 + \dots + 3) + F(1).$

В сумме $3 + 5 + \dots + 43$ ровно 21 слагаемое, её значение равно $\frac{(3 + 43) \cdot 21}{2} = 23 \cdot 21 = 483$ .

Итого $F(43) = 3 \cdot 483 + 1 = 1449 + 1 = 1450$ .

from functools import lru_cache

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

print(F(43))   # 1450

Ответ: 1450