Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

หมายเลขคาตาลันที่ N ในโปรแกรม Python


ในบทความนี้ เราจะเรียนรู้เกี่ยวกับการคำนวณหมายเลขคาตาลันที่ n

หมายเลขคาตาลัน เป็นลำดับของจำนวนธรรมชาติที่กำหนดโดยสูตรแบบเรียกซ้ำ -

$$c_{0} =1\;และ\; c_{n+1} =\displaystyle\sum\limits_{i=0}^nc_{i} c_{n-i}\; สำหรับ n\geq 0;$$

ตัวเลขคาตาลันสองสามตัวแรกสำหรับ 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

ขอบเขตของตัวแปรทั้งหมดและการเรียกซ้ำแสดงอยู่ด้านล่าง

หมายเลขคาตาลันที่ N ในโปรแกรม Python

วิธีที่ 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 ในโปรแกรม Python

บทสรุป

ในบทความนี้ เราได้เรียนรู้เกี่ยวกับวิธีการสร้างหมายเลขคาตาลันที่ n