n번째 카탈루냐 숫자를 위한 파이썬 프로그램

이 기사에서는 n번째 카탈루냐 숫자를 계산하는 방법에 대해 알아봅니다.

카탈루냐 숫자 재귀 공식 -

$$C_{0}=1\:and\:C_{n+1}=\displaystyle\sum\limits_{i=0}^n C_{i}C_{n-i} for \:n\geq0;$$

n =0, 1, 2, 3, ...에 대한 처음 몇 개의 카탈루냐어 숫자는 1, 1, 2, 5, 14, 42, 132,429,................................ ....

카탈루냐 숫자는 재귀 및 동적 프로그래밍을 통해 얻을 수 있습니다. 그럼 구현을 살펴보겠습니다.

접근법 1:재귀 방법

예

# A recursive solution
def catalan(n):
   #negative value
   if n <=1 :
      return 1
   # Catalan(n) = catalan(i)*catalan(n-i-1)
   res = 0
   for i in range(n):
      res += catalan(i) * catalan(n-i-1)
   return res
# main
for i in range(6):
   print (catalan(i))

출력

1
1
2
5
14
42

모든 변수와 재귀 호출의 범위는 다음과 같습니다.

접근법 2:동적 프로그래밍 방법

예

# using dynamic programming
def catalan(n):
   if (n == 0 or n == 1):
      return 1
   # divide table
   catalan = [0 for i in range(n + 1)]
   # Initialization
   catalan[0] = 1
   catalan[1] = 1
   # recursion
   for i in range(2, n + 1):
      catalan[i] = 0
      for j in range(i):
         catalan[i] = catalan[i] + catalan[j] * catalan[i-j-1]
   return catalan[n]
# main
for i in range (6):
   print (catalan(i),end=" ")

출력

1
1
2
5
14
42

모든 변수와 재귀 호출의 범위는 다음과 같습니다.

결론

이 글에서는 n번째 카탈루냐 숫자를 생성하는 방법에 대해 배웠습니다.