Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Números de Catalan

Genera los números de Catalan desde C(0) hasta C(n).

Lo que aprenderás

  • Construir una sucesión a partir de valores anteriores
  • Usar una recurrencia de suma de productos
  • Evitar el desbordamiento en los resultados intermedios

Problema

Ver original (inglés)

Los números de Catalan 1, 1, 2, 5, 14, 42, … cuentan muchas cosas: las cadenas equilibradas de n pares de paréntesis, los árboles binarios con n nodos y las formas de dividir un polígono convexo en triángulos. Empiezan con C(0) = 1 y cumplen C(k + 1) = C(0)·C(k) + C(1)·C(k − 1) + … + C(k)·C(0).

Implementa catalan_numbers(n).

Entrada

n: el índice del último número de Catalan que se incluye.

Salida

Devuelve la lista [C(0), C(1), …, C(n)], que tiene n + 1 valores. C(35) es el mayor que cabe en un entero de 64 bits con signo, así que cuidado con el desbordamiento en los pasos intermedios.

Restricciones

0 ≤ n ≤ 35

Ejemplos

Ejemplo 1
Entrada:
n = 4

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

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

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

Explicación

C(4) = 1·5 + 1·2 + 2·1 + 5·1 = 14, así que la lista es [1, 1, 2, 5, 14].

Ejemplo 2
Entrada:
n = 0

Salida esperada:
expected = [1]
Entrada:
long long n = 0;

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

Salida esperada:
long[] expected = new long[] {1};

Explicación

Solo se pide C(0) = 1: [1].

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Guarda los valores en una lista a medida que los calculas.

Pista 2

C(k + 1) es una suma sobre i de C(i) × C(k − i).

Pista 3

Cada producto de esa suma es como mucho el valor final, así que con estos límites el método de la suma nunca se desborda.

Complejidad esperada

tiempo O(n^2), espacio extra O(n)

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.