Все задачи
Средне Решено: 0 Процент решений: 0%

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

Выведите числа Каталана от C(0) до C(n).

Чему вы научитесь

  • Строить последовательность из предыдущих значений
  • Применять рекуррентное соотношение в виде суммы произведений
  • Избегать переполнения в промежуточных результатах

Условие

Числа Каталана 1, 1, 2, 5, 14, 42, … считают очень многое: правильные скобочные последовательности из n пар скобок, двоичные деревья с n вершинами, способы разрезать выпуклый многоугольник на треугольники. Последовательность начинается с C(0) = 1 и подчиняется соотношению C(k + 1) = C(0)·C(k) + C(1)·C(k − 1) + … + C(k)·C(0).

Реализуйте catalan_numbers(n).

Входные данные

n: номер последнего числа Каталана, которое нужно включить.

Выходные данные

Верните список [C(0), C(1), …, C(n)] из n + 1 значений. C(35) - наибольшее из чисел Каталана, которое помещается в знаковое 64-битное целое, поэтому следите за переполнением в промежуточных вычислениях.

Ограничения

0 ≤ n ≤ 35

Примеры

Пример 1
Ввод:
n = 4

Ожидаемый вывод:
expected = [1, 1, 2, 5, 14]
Ввод:
long long n = 4;

Ожидаемый вывод:
std::vector<long long> expected = {1, 1, 2, 5, 14};
Ввод:
long n = 4;

Ожидаемый вывод:
long[] expected = new long[] {1, 1, 2, 5, 14};

Пояснение

C(4) = 1·5 + 1·2 + 2·1 + 5·1 = 14, поэтому список равен [1, 1, 2, 5, 14].

Пример 2
Ввод:
n = 0

Ожидаемый вывод:
expected = [1]
Ввод:
long long n = 0;

Ожидаемый вывод:
std::vector<long long> expected = {1};
Ввод:
long n = 0;

Ожидаемый вывод:
long[] expected = new long[] {1};

Пояснение

Нужно только C(0) = 1: [1].

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Сохраняйте значения в список по мере вычисления.

Подсказка 2

C(k + 1) - это сумма по i произведений C(i) × C(k − i).

Подсказка 3

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

Ожидаемая сложность

время O(n^2), доп. память O(n)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

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