Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como implementar a fórmula dos Números de Catalan usando recursão?

+1 voto
64 visitas
perguntada Abr 3 em Ciência da Computação por LucasNaves (11 pontos)  

Implementar a seguinte fórmula de maneira recursiva:

A imagem será apresentada aqui.

A questão foi retirada do livro "Introduction to Recursive Programming", Manuel Rubio Sánches, 2017(exercício 8.5).

Compartilhe

1 Resposta

+1 voto
respondida Abr 3 por LucasNaves (11 pontos)  

Números de Catalan são derivados da matemática combinatória, e representam uma sequência de números naturais presente em vários problemas de contagem (Wikipédia).

A fórmula C(n) para representar o n-ésimo número da sequência pode assumir várias formas além da citada na pergunta:

A imagem será apresentada aqui.

Um tipo de problema que pode ser resolvido utilizando essa sequência é o da contagem do número de árvores binárias com n + 1 folhas. No topo de cada árvore estaria o vértice da raiz, e em cada próximo nível estariam outros vértices binários, ou seja, eles seriam capazes da dar origem a dois novos vértices ou a nenhum. Os vértices que não geram outros seriam as folhas (Projeto Delfos). Para n = 3, teríamos o número de árvores binárias com 3 + 1 folhas:

A imagem será apresentada aqui.

Utilizando a linguagem Phyton podemos utilizar o seguinte código:

def C(n): # Vamos determinar essa fórmula recursivamente
    if n == 0: # C(n) = 1 se n = 0,
        return 1
    if n >= 1: # Σ(i=0;n-1)C(i)*C(n-1-i)se n maior ou igual a 1
        soma = 0
        for i in range (n): # forma de impregar o somatório
            soma += C(i) * C(n-1-i) 
    return soma

if __name__ == "__main__":
    for i in range(11):
        print(C(i))

Os números de Catalan para n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 são, respectivamente:

  • 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796
comentou Jun 17 por Felipe Carneiro (26 pontos)  
Lucas, muito boa implementação!
Ao invés de utilizar uma recursão, utilizei um loop para implementar os números de Catalan. Segue a implementação:

def C(n):
  soma = 1.0
  for k in range(2,n+1):
     soma = soma *(n+k)/k
  return soma
...