Числа Каталана

Рассмотрим реализацию алгоритма вычисления чисел Каталана на языке Julia.

Введение

В этом примере мы изучим реализацию алгоритма для вычисления чисел Каталана — последовательности натуральных чисел, имеющих важное значение в комбинаторике и других областях математики. Мы рассмотрим, как работает функция вычисления чисел Каталана, а также как она применяется к диапазону значений и к большим числам.

Что такое числа Каталана?

Числа Каталана — это последовательность чисел, которая часто встречается в задачах комбинаторики. Например, они используются для подсчёта количества правильных скобочных последовательностей, числа путей на решётке, числа способов разбиения многоугольника на треугольники и т. д.

Формула для вычисления n-го числа Каталана выглядит так:

где — биномиальный коэффициент.

В коде используется именно эта формула.

# Определяем функцию для вычисления числа Каталана
# n::Integer означает, что аргумент должен быть целым числом
# binomial(2n, n) вычисляет биномиальный коэффициент
# ÷ обозначает целочисленное деление
catalannum(n::Integer) = binomial(2n, n) ÷ (n + 1)

catalannum (generic function with 1 method)

Вычисление чисел Каталана для диапазона от 1 до 15

Функция catalannum.(1:15) применяет функцию catalannum к каждому элементу диапазона от 1 до 15. Точка после имени функции означает векторизацию — применение функции к каждому элементу коллекции.

Результатом будет массив чисел Каталана от 1 до 15.

# Применяем функцию к диапазону от 1 до 15
catalannum.(1:15)

15-element Vector{Int64}:
       1
       2
       5
      14
      42
     132
     429
    1430
    4862
   16796
   58786
  208012
  742900
 2674440
 9694845

Вычисление 100-го числа Каталана

Для вычисления больших чисел Каталана используется функция big(100), которая преобразует число 100 в тип BigInt. Это позволяет работать с числами, превышающими стандартный размер целочисленных типов, чтобы избежать переполнения.

Результатом будет 100-е число Каталана, представленное в виде большого целого числа.

# Вычисляем 100-е число Каталана, используя BigInt
catalannum(big(100))

896519947090131496687170070074100632420837521538745909320

Заключение

Мы рассмотрели реализацию алгоритма вычисления чисел Каталана на языке Julia. Была создана функция catalannum, которая использует биномиальные коэффициенты для вычисления чисел Каталана. Мы применили её к диапазону от 1 до 15 и вычислили 100-е число Каталана с использованием BigInt. Это позволяет эффективно работать как с небольшими, так и с большими значениями чисел Каталана. Такие вычисления полезны в комбинаторике, анализе алгоритмов и других областях математики.

Пример разработан с использованием материалов Rosetta Code