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

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

530

Пояснение

Решение:

Аргумент 32 чётный, поэтому $F(32) = 2 \cdot 31 + F(31) + 2 = 64 + F(31)$ .

Дальше 31 нечётно, а нечётная ветка уменьшает аргумент сразу на 2. Значит вся оставшаяся цепочка идёт только по нечётным числам, и формула для чётных $n$ больше не понадобится. Упростим её:

$F(n) = 2(n + 1) + F(n - 2) - 5 = 2n - 3 + F(n - 2), \quad n \text{ — нечётное}, \; n \gt 2.$

База — $F(1) = 1$ . Поднимаемся шагами по 2:

$n$	$F(n)$
1	1
3	4
5	11
7	22
9	37
11	56
13	79
15	106
17	137
19	172
21	211
23	254
25	301
27	352
29	407
31	466

Например, $F(3) = 2 \cdot 3 - 3 + F(1) = 3 + 1 = 4$ , $F(5) = 7 + 4 = 11$ , и так далее до $F(31) = 466$ .

Наконец $F(32) = 64 + F(31) = 64 + 466 = 530$ .

import sys
sys.setrecursionlimit(10000)

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

print(F(32))   # 530

Ответ: 530