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

[Galls190791]

Люди, помогите пожалуйста написать программу вычисления чисел Каталана на Паскале.
Я учуюсь на 1 курсе и мне не понятна даже сама формула, кто может объяснить как она работает???

Comments

Как сказала мне википедия, формула для чисел Каталана следующая:


1) n = 0
C[n] = C[0] = 1

2) n = 1, i = 0 -> 0
C[n] = C[1] = C[0] * C[0] = 1 * 1 = 1

3) n = 2, i = 0 -> 1
C[n] = C[2] = C[0] * C[1] + C[1] * C[0] = 1 * 1 + 1 * 1 = 1 + 1 = 2

4) n = 3, i = 0 -> 2
C[n] = C[3] = C[0] * C[2] + C[1] * C[1] + C[2] * C[0] = 1 * 2 + 1 * 1 + 2 * 1 = 2 + 1 + 2 = 5

и т.д.

Программа, навкидку, получилась такая. Она может содержать баги, я их не старался ловить.
Хотя вроде дает нужный результат.

Старался соответствовать формуле, что бы было понятнее - поэтому ни разу не оптимальное решение.
#include
using namespace std;
int katalans_number(int n);

int main()
{
// Цикл перебирает числа Каталана от 0 до 9
for(int i = 0; i < 10; i++)
{
// Собственное, выводит i-ое число
cout << i << " number = " << katalans_number(i) << endl;
}
return 0;
}

// Рекурсивная функция вычисления числа Каталана n
int katalans_number(int n)
{
// Постарался максимально соответствовать форумуле

// Если n = 0, то нулевое число Каталана - это 1
if (n == 0)
return 1;
// Если n не равно 0, то
else
{
int tmp = 0; // Временная переменная, в которую будем накапливать сумму
// Цикл суммирования
for(int i = 0; i <= n - 1; i++)
{
// К уже накопленной сумме добавляем произведение двух чисел каталана
tmp += katalans_number(i) * katalans_number(n - 1 - i);
}
return tmp;
}
}

[Galls190791]

так формула же в Википедии по другому написана

[Galls190791]

Ой блин, что то я не туда посмотрел, все правильно.....

Многоуважаемый  deepman написал следующий вариант.
Под PascalABC.NET (pascalabc.net/) работает.

Спрашивает n и для него выводит число Каталона соответсвующее.

Program Catalan;
Var 
  n:integer;
  res:integer;

Function Calculate(n:integer):integer;
  Var 
    count:integer;
    i:integer;
  Begin{Calculate}
    if n = 0
    then
      Begin
        Calculate:=1;
      End
    Else
      Begin
      count:=0;
      for i:= 0 to n-1 do
        Begin
         count:= count + Calculate(i)*Calculate(n-1-i);
        End;
      Calculate:= count;
      End
   End;
   
Begin
  Write('Input number: ');
  ReadLn(n);
  res:= Calculate(n);
  Write('Catalan number: ');
  WriteLn(res);
End.