PythonプログラムのN番目のカタラン数

この記事では、n番目のカタラン数の計算について学習します。

カタラン数 再帰式-

$$ c_ {0} =1\;および\; c_ {n + 1} =\ displaystyle \ sum \ Limits_ {i =0} ^ nc_ {i} c_ {n-i} \; n \geq0の場合;$$

n =0、1、2、3、…の最初のいくつかのカタラン数は、1、1、2、5、14、42、132、429、.....です。 ...

カタラン数は、再帰と動的計画法の両方で取得できます。

では、それらの実装を見てみましょう。

アプローチ1：再帰方法​​

例

アプローチ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番目のカタラン数を生成する方法について学びました