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

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

9841

Пояснение

Решение:

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

$F(1) = 1$ , $F(3) = 1 + 3 \cdot 1 = 4$ , $F(5) = 1 + 3 \cdot 4 = 13$ , $F(7) = 1 + 3 \cdot 13 = 40$ , $F(9) = 121$ , $F(11) = 364$ , $F(13) = 1093$ , $F(15) = 3280$ , $F(17) = 1 + 3 \cdot 3280 = 9841$ .

Тот же результат виден и по формуле: раскрывая скобки, получаем сумму геометрической прогрессии $F(17) = 3^{8} + 3^{7} + \dots + 3 + 1 = \frac{3^{9} - 1}{2} = \frac{19683 - 1}{2} = 9841.$

from functools import lru_cache

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

print(F(17))   # 9841

Ответ: 9841