Задание 16
Задание 16 (демо-2023). Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n × F(n − 1), если n > 1.
Чему равно значение выражения F(2023) / F(2020)?
Программы решения задания на языках PascalABC.NET и Python приведены ниже.
|
PascalABC.NET |
|
## function F(n: BigInteger): BigInteger:= n<=1 ? 1 : n*F(n-1);
print(F(2023) div F(2020)); |
|
Python |
|
import sys sys.setrecursionlimit (3000) def F(n): if n == 1: return 1 else: return n * F(n-1) print(F(2023)//F(2020)) |
Из условия задачи видно, что заданная функция представляет собой функцию факториала числа n. Исходя из определения факториала, понятно, что задачу можно свести к выводу на экран произведения 2021*2022*2023. Однако мы рассмотрим особенности именно программного решения данного задания на языках PascalABC.NET и Python.
Если на языке Python написать функцию факториала и просто посчитать выражение F(2023)//F(2020), то мы столкнёмся с исключением RecursionError – ошибка переполнения стека рекурсии: была превышена глубина рекурсии. Чтобы увеличить глубину стека воспользуемся модулем sys и функцией setrecursionlimit(k), она устанавливает максимальную глубину стека рекурсии на значение k. Так как максимальное число в функции F равно 2023 и при каждом шаге рекурсии функция вызывает себя только один раз, то глубины рекурсии k=3000 хватит для решения задания. После этого программа работает корректно.
Перейдём к решению на языке PascalABC.NET. Нами уже был рассмотрен тип данных BigInteger, который позволяет работать практически с неограниченно большими числами. Объявляем функцию F, принимающую и возвращающую значения типа BigInteger. Для краткого написания функции используем тернарный оператор со следующим условием: если значение n меньше либо равно 1, то функция возвращает 1, иначе возвращает значение n*F(n). Выводим на экран функцией Print() значение F(2023) div F(2020) и видим, что никаких ошибок не возникает.