ในบทความนี้ เราจะเรียนรู้เกี่ยวกับการคำนวณหมายเลขคาตาลันที่ 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
ขอบเขตของตัวแปรทั้งหมดและการเรียกซ้ำแสดงอยู่ด้านล่าง
วิธีที่ 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
