โปรแกรม C สำหรับหมายเลขคาตาลันที่ n

รับ interger n; ภารกิจคือค้นหาหมายเลขคาตาลันในตำแหน่งที่ n นั้น ดังนั้นก่อนทำโปรแกรมเราต้องรู้ว่าหมายเลขคาตาลันคืออะไร?

ตัวเลข Catlan เป็นลำดับของจำนวนธรรมชาติที่เกิดขึ้นในรูปแบบของปัญหาการนับจำนวนต่างๆ

หมายเลขคาตาลัน C0, C1, C2,… Cn ถูกขับเคลื่อนโดยสูตร -

$$c_{n}=\frac{1}{n+1}\binom{2n}{n} =\frac{2n!}{(n+1)!n!}$$

ตัวเลขคาตาลันสองสามตัวสำหรับทุก n =0, 1, 2, 3, … คือ 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

ดังนั้น หากเราป้อน n =3 เราควรได้ 5 เป็นผลลัพธ์จากโปรแกรม

การใช้งานหมายเลขคาตาลันบางส่วน −

• การนับจำนวนต้นไม้การค้นหาไบนารีที่เป็นไปได้ด้วยปุ่ม n
• การหาจำนวนนิพจน์ที่มีวงเล็บ n คู่ที่ตรงกันอย่างถูกต้อง เช่นเดียวกับ n =3 นิพจน์วงเล็บที่เป็นไปได้คือ ((())), ()(()), ()()(), (())(), (()())
• ค้นหาวิธีเชื่อมต่อจุดต่างๆ บนคอร์ดที่ไม่ปะติดปะต่อแบบวงกลม และอื่นๆ อีกมากมาย

ตัวอย่าง

อินพุต:n =6Output:132Input:n =8Output:1430

แนวทางที่เราจะใช้ในการแก้ปัญหาที่กำหนด −

• การรับและป้อนข้อมูล n.
• ตรวจสอบว่า n <=1 แล้ว ให้คืนค่า 1
• วนรอบจาก i=0 ถึง i
• สำหรับทุกผลลัพธ์ของ i Set =ผลลัพธ์ + (catalan(i)*catalan(n-i-1))
• ส่งคืนและพิมพ์ผลลัพธ์

อัลกอริทึม

เริ่มขั้นตอนที่ 1 -> ในฟังก์ชัน unsigned long int catalan (unsigned int n) ถ้า n <=1 ให้คืนค่า 1 End หากประกาศตัวแปรยาวที่ไม่ได้ลงนาม res =0 วนสำหรับ i=0 และ i int main() ประกาศอินพุต n =6 พิมพ์ "catalan is :แล้วเรียกฟังก์ชัน catalan(n)Stop 
ตัวอย่าง
 
#include // ใช้วิธีการแบบเรียกซ้ำเพื่อค้นหาหมายเลขคาตาลัน unsigned long int catalan (unsigned int n) {// กรณีฐานถ้า (n <=1) คืนค่า 1; // catalan(n) คือผลรวมของ catalan(i)*catalan(n-i-1) unsigned long int res =0; สำหรับ (int i=0; i 
ผลลัพธ์
 
คาตาลันคือ :132