10303. Сколько деревьев?

 

Сколько разных бинарных деревьев можно составить из n вершин?

 

Вход. Каждая строка содержит одно число i (1 £ i £ 1000) – количество вершин.

 

Выход. Для каждого числа i вывести количество разных бинарных деревьев, которое можно составить из i вершин.

 

Пример входа

Пример выхода

 
1
2

3

 
1
2

5

 

 

РЕШЕНИЕ

числа Каталана

 

Анализ алгоритма

Определение. Числами Каталана cn (n = 0, 1, 2, …) называются числа вида

cn =

Первыми числами последовательности будут 1, 1, 2, 5, 14, 42, 132, 429, 1430, … . Числа Каталана являются решением рекуррентного уравнения

с0 = 1,

сn = c0cn-1 + c1cn-2 + c2cn-3 + ... + cn-1c0 при n > 0

 

Корень бинарного дерева содержит одну вершину. Если левое поддерево содержит k вершин (0 £ k £ n – 1), то правое поддерево содержит (n – k – 1) вершин. Обозначим через f(n) количество бинарных деревьев с n вершинами. Тогда

f(n) = f(0) * f(n – 1) + f(1) * f(n – 2) + … + f(n – 1) * f(0),

то есть f(n) = cn.

 

Пример

Пусть n = 3. Существует 5 разных бинарных деревьев с 3 вершинами:

 

 

 

 

 

 

 

 

 


Реализация алгоритма

Для заданного значения n достаточно вычислить

cn =  = = .

 

while(scanf("%d",&n) == 1)

{

 

Занесем в ячейки массива m множители (n + 2), (n + 3), …, (2n) так что m[i] = n + i + 2.

 

  for(i = 0; i < n - 1; i++) m[i] = n + i + 2;

 

Далее будем делить (сокращать) числитель дроби на i = 2, 3, …, n. Для того чтобы разделить числитель дроби на z, следует перебирать множители (n + 2), (n + 3), … и как только наибольший общий делитель числа z и текущего множителя будет больше единицы, то делить их обоих на этот общий делитель. Продолжать до тех пор пока z не станет равным 1. Поскольку значение cn целочисленное, то произведение (n + 2), (n + 3), …, (2n) делится нацело на (2 * 3 * … * n).

 

  for(i = 2; i <= n; i++)

  {

    for(z = i, j = 0; z > 1; j++)

    if ((temp = gcd(z,m[j])) > 1)

      z /= temp, m[j] /= temp;

  }

 

Функция gcd вычисления наибольшего общего делителя имеет вид:

 

int gcd(int a, int b)

{

  return (!a) ? b : gcd(b % a, a);

}

 

Значение cn равно произведению m[0] * m[1] * … * m[n – 2]. Вычислим его.

 

  memset(res,0,sizeof(res)); res[0] = 1;

  for(i = 0; i < n - 1; i++)

   if (m[i] > 1) mult(res,m[i],res);

 

Результат умножения – длинное число, поэтому следует выполнять длинное умножение при помощи функции mult.

 

void mult(int *a, int m, int *res)

{

  int carry = 0, i;

  for(i = 0; i < MAX; i++)

  {

    carry = a[i] * m + carry;

    res[i] = carry % 10;

    carry /= 10;

  }

}

 

Выведем результат – длинное число, содержащееся в массиве res[1001].

 

  for(i = MAX - 1; !res[i]; i--);

  for(; i >= 0; i--) printf("%d",res[i]);

  printf("\n");

}