Todos os desafios
Médio 0 resolvidos 0% de aceitação

Números de Catalan

Liste os números de Catalan de C(0) a C(n).

O que você vai aprender

  • Construir uma sequência a partir de valores anteriores
  • Usar uma recorrência de soma de produtos
  • Evitar overflow nos resultados intermediários

Problema

Ver original (inglês)

Os números de Catalan 1, 1, 2, 5, 14, 42, … contam muitas coisas: sequências balanceadas de n pares de parênteses, árvores binárias com n nós e maneiras de dividir um polígono convexo em triângulos. Eles começam com C(0) = 1 e satisfazem C(k + 1) = C(0)·C(k) + C(1)·C(k − 1) + … + C(k)·C(0).

Implemente catalan_numbers(n).

Entrada

n: o índice do último número de Catalan a incluir.

Saída

Retorne a lista [C(0), C(1), …, C(n)], que tem n + 1 valores. C(35) é o maior que cabe em um inteiro de 64 bits com sinal, então cuidado com overflow nos passos intermediários.

Restrições

0 ≤ n ≤ 35

Exemplos

Exemplo 1
Entrada:
n = 4

Saída esperada:
expected = [1, 1, 2, 5, 14]
Entrada:
long long n = 4;

Saída esperada:
std::vector<long long> expected = {1, 1, 2, 5, 14};
Entrada:
long n = 4;

Saída esperada:
long[] expected = new long[] {1, 1, 2, 5, 14};

Explicação

C(4) = 1·5 + 1·2 + 2·1 + 5·1 = 14, então a lista é [1, 1, 2, 5, 14].

Exemplo 2
Entrada:
n = 0

Saída esperada:
expected = [1]
Entrada:
long long n = 0;

Saída esperada:
std::vector<long long> expected = {1};
Entrada:
long n = 0;

Saída esperada:
long[] expected = new long[] {1};

Explicação

Só C(0) = 1 é pedido: [1].

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Guarde os valores em uma lista à medida que os calcula.

Dica 2

C(k + 1) é uma soma, para cada i, de C(i) × C(k − i).

Dica 3

Cada produto dessa soma é no máximo o valor final, então, dentro dos limites, esse método nunca estoura.

Complexidade esperada

tempo O(n^2), espaço extra O(n)

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.