Задание 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) = n + F(n − 1), если n — чётно;
F(n) = 2 × F(n − 2), если n > 1 и при этом n — нечётно.
Чему равно значение функции F(26)?

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

4122

Пояснение

Решение:

Число 26 чётное, поэтому $F(26) = 26 + F(25)$ . Осталось найти $F(25)$ .

Для нечётных $n \gt 1$ правило $F(n) = 2 \cdot F(n-2)$ уменьшает аргумент на 2, оставляя его нечётным, поэтому цепочка идёт только по нечётным числам: $F(25) = 2F(23) = 4F(21) = \dots = 2^{12} \cdot F(1)$ (от 25 до 1 ровно 12 шагов). Значит $F(25) = 2^{12} = 4096$ .

Итого $F(26) = 26 + 4096 = 4122$ .

from functools import lru_cache

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

print(F(26))   # 4122

Ответ: 4122