ЕГЭ Информатика пэжэшка

Рекурсия в PascalABC:
var n : integer;
function F (n : integer): integer;
begin
if (n < 2) then Result := n
else if ((n > 1) and (n mod 2 = 0)) then Result := (F(n - 1) + F(n - 2))
else if ((n > 1) and (n mod 2 <> 0)) then Result := (F(n - 1)*n);
end;

begin
Write (' Введите n = '); ReadLn (n);
WriteLn (' n = ', n , '; F = ', F(n));
end.

Для вычисления значения функции F(n) можно написать рекурсивную функцию на языке программирования. Например, на языке C++:

#include <iostream>
using namespace std;

int F(int n) {
if (n < 2) {
return n;
}
else if (n % 2 == 0) {
return F(n-1) + F(n-2);
}
else {
return F(n-1) * n;
}
}

int main() {
int n = 11;
int result = F(n);
cout << "F(" << n << ") = " << result << endl;
return 0;
}

В результате выполнения программы будет выведено:

F(11) = 144

Для больших нечётных n = 2k + 1:

 F(2k+1) = F(2k) * (2k+1) = (F(2k-1) + F(2k-2)) * n = (F(2k-2) * (2k-1) + F(2k-2)) * (2k-1) =

     = F(2k-2) * (2k) * (2k+1) = (F(n-4) + F(n-5)) * (n-1) * n =

     = F(2k-4) * (2k-2) * (2k) * (2k+1) =

     = F(2k-6) * (2k-4) * (2k-2) * (2k) * (2k+1) =

     = F(2k-8) * (2k-6) * (2k-4) * (2k-2) * (2k) * (2k+1) =

     = ... =

     = F(2) * k! * 2ᵏ⁻¹ * (2k+1) = k! * 2ᵏ⁻¹ * (2k+1)



(F(2) = F(1) + F(0) = 1 + 0 = 1) 

Для чётных n делается всё то же самое, кроме умножения на n.

Так что единственное, что требуется от программы, - умножить факториал на степень двойки и, в зависимости от чётности, на n. Не надо никакой рекурсии и никаких повторяющихся вычислений.

Питон:

 from math import factorial

n = int(input('Введите n: '))

k = n // 2

print((factorial(k)  1) f *= n; // не очень эффективно, но для малых n сойдёт

    return f;

}



int main() {

    cout > n;

    const unsigned k = n >> 1;

    const unsigned l[] = { 1, n };

    cout