Question

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

Answer 1

В приложении дана блок-схема с алгоритмом, вычисляющим значение функции F по рекуррентной схеме.
Ниже приводится запись программы на языке Pascal, содержащая две функции - рекуррентную F (строго в соответствии с алгоритмом) и рекурсивную Fr.
Вывод иллюстрирует работу программы для значения аргумента n=6

function F(n: integer): integer;
{рекуррентная}
var
  i, p: integer;
  fn1, fn2: integer;


begin
  case n of
    1: Result := 1;
    2: Result := 2;
  else
    begin
      fn2 := 1;
      fn1 := 2;
      for i := 3 to n do
      begin
        p := 2 * fn1 + (i - 2) * fn2;
        fn2 := fn1;
        fn1 := p
      end;
      Result := p
    end
  end
end;

function Fr(n: integer): integer;
{рекурсивная - оцените изящество рекурсии!}
begin
  case n of
    1: Result := 1;
    2: Result := 2;
  else Result := 2 * Fr(n - 1) + (n - 2) * Fr(n - 2)
  end
end;

begin
  writeln(F(6), ' ', Fr(6))
end.

Тестовое решение:
142 142

Ответ: значение функции F(6) равно 142.

Answer 2

Для вычисления значения функции \(F(n)\) по заданным соотношениям, используем рекурсивную формулу:

\[F(n) = \begin{cases} 1, & \text{если } n = 1 \\ 2, & \text{если } n = 2 \\ 2 \cdot F(n-1) + (n-2) \cdot F(n-2), & \text{если } n > 2 \end{cases} \]

Давайте вычислим значения функции для \(n = 1, 2, 3, 4, 5, 6\) по заданным соотношениям:

\[ F(1) = 1 \]

\[ F(2) = 2 \]

\[ F(3) = 2 \cdot F(2) + (3-2) \cdot F(1) = 2 \cdot 2 + 1 \cdot 1 = 5 \]

\[ F(4) = 2 \cdot F(3) + (4-2) \cdot F(2) = 2 \cdot 5 + 2 \cdot 2 = 14 \]

\[ F(5) = 2 \cdot F(4) + (5-2) \cdot F(3) = 2 \cdot 14 + 3 \cdot 5 = 37 \]

\[ F(6) = 2 \cdot F(5) + (6-2) \cdot F(4) = 2 \cdot 37 + 4 \cdot 14 = 108 \]

Таким образом, значение функции \(F(6)\) равно 108.