Question

Алгоритм вычисления функции F(n) задан следующими соотношениями: F(n) = 1 при n<2 F(n) = 2·F(n–1), если n чётно и n>1 F(n) = 4·n + F(n–2), если n нечётно и n>1. Чему равно значение функции F(45)?

Answer 1

F(45) = 4*45 + F(43)

F(45) = 4*45 + 4*43 + F(41)

...

F(45) = 4*(45 + 43 + 41 + 39 + 37 + 35 + 33 + 31 + 29 + 27 + 25 + 23 + 21 + 19 + 17 + 15+ 13 + 11 + 9 + 7 + 5 + 3) + 1

F(45) = 4*528 + 1

F(45) = 2113

Answer 2

Для вычисления значения функции F(45) сначала нужно определить, является ли число 45 четным или нечетным, и затем применить соответствующее правило.

Поскольку 45 - это нечетное число (нечетное, потому что 45 не делится нацело на 2), мы будем использовать второе правило:

F(n) = 4·n + F(n–2)

Теперь мы можем рекурсивно вычислить значение F(45). Начнем с базового случая:

F(0) = 1 F(1) = 1

Теперь вычислим значение F(45) с использованием второго правила:

F(45) = 4 * 45 + F(43)

Далее, мы продолжим рекурсивно вычислять F(43) и другие значения, пока не достигнем базового случая:

F(43) = 4 * 43 + F(41) F(41) = 4 * 41 + F(39) ... F(3) = 4 * 3 + F(1) F(1) = 1

Теперь мы можем начать обратно и вычислить все значения F(n):

F(1) = 1 F(3) = 4 * 3 + F(1) = 12 + 1 = 13 F(5) = 4 * 5 + F(3) = 20 + 13 = 33 ... F(45) = 4 * 45 + F(43) = 180 + (4 * 43 + F(41)) = 180 + (172 + (4 * 41 + F(39))) = ... = 102534

Итак, значение функции F(45) равно 102534.