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

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

884

Пояснение

Решение:

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

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

В сумме $3 + 5 + \dots + 41$ ровно 20 слагаемых, она равна $\frac{(3 + 41) \cdot 20}{2} = 22 \cdot 20 = 440$ , поэтому $F(41) = 2 \cdot 440 + 1 = 881$ .

Тогда $F(42) = 3 + 881 = 884$ .

from functools import lru_cache

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

print(F(42))   # 884

Ответ: 884