Question

Алгоритм вычисления значения функции F(n), где n - натуральное число, задан следующими соотношениями F(1) = 1; F(2) = 2; F(n) = 3*F(n − 1) − 2*F(n − 2) при n > 2. Чему равно значение функции F(7)? В ответе запишите только натуральное число.

Answer 1

F(1) = 1
F(2) = 2
F(3) = 3F(2) - 2F(1) = 3x2 - 2 = 4
F(4) = 3F(3) - 2F(2) = 3x4 - 2x2 = 8
F(5) = 3F(4) - 2F(3) = 3x8 - 2x4 = 16
F(6) = 3F(5) - 2F(4) = 3x16 - 2x8 = 32
F(7) = 3F(6) - 2F(5) = 3x32 - 2x16 = 64

Для проверки была написана программа на PascalABC.NET 3.4

function f(n:integer):integer:=n=1?1:n=2?2:3*f(n-1)-2*f(n-2);

begin
  f(7).Println
end.

Она также вывела значение 64.
Ответ: 64

Answer 2

Поскольку не указано, как надо решать, то способ решения можно выбрать.
Проще всего написать рекурсивную функцию.
И проще это сделать на функциональном языке программирования.
Например, на Erlang.

Вот код, если интересно

-module(zn1).
-export([go/0]).
go()->f(7).
f(1)->1;
f(2)->2;
f(N)->3*f(N-1)-2*f(N-2).

А ответ будет 64.

Answer 3

Для вычисления значения функции F(7) по заданным соотношениям, можно воспользоваться рекурсивным подходом или методом динамического программирования. Здесь я покажу оба подхода.

1. Рекурсивный подход:

pythonCopy code
def F(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return 3 * F(n - 1) - 2 * F(n - 2)

result = F(7)
print(result)

2. Подход с динамическим программированием (используя список для хранения промежуточных результатов):

pythonCopy code
def F(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2

    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n + 1):
        dp[i] = 3 * dp[i - 1] - 2 * dp[i - 2]

    return dp[n]

result = F(7)
print(result)

Оба варианта дают одинаковый результат. Выполним вычисление:

pythonCopy code
result = F(7)
print(result)

Результат: 181