الأعداد الكاتالانية

الأعداد الكاتالانية Catalan Numbers هي متتالية من الأعداد الطبيعية والتي تظهر في عدد من مسائل العدّ مثل:

1. حساب عدد التعابير التي تحتوي على n زوج من الأقواس الهلالية، والتي تطابق بعضها البعض تطابقًا صحيحًا. إذا كانت n = 3 فإنّ التعابير الممكنة هي: ((())), ()(()), ()()(), (())(), (()()).
2. حساب عدد أشجار البحث الثنائية والتي تحتوي على n مفتاح.
3. حساب عدد الأشجار الثنائية الممتلئة full binary trees (تكون الشجرة الثنائية ممتلئة إذا امتلك كل رأس فيها عقدتي أبناء أو لم يمتلك أي عقدة) التي تمتلك n+1 من الأوراق.

أول مجموعة من الأعداد الكاتالانية والتي تقابل قيم n = 0, 1, 2, 3, ...‎ هي ‎1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...‎

الطريقة التعاودية

تحقق الأعداد الكاتالانية العلاقة التعاودية التالية:

تعرض الأمثلة التالية كيفية تنفيذ هذه الطريقة في عدد من لغات البرمجة:

• C++‎:

#include<iostream> 
using namespace std; 

unsigned long int catalan(unsigned int n) 
{ 
	// الحالة الأساسية
	if (n <= 1) return 1; 

	// catalan(n) العدد
	// هو مجموع
	// catalan(i)*catalan(n-i-1)
	unsigned long int res = 0; 
	for (int i=0; i<n; i++) 
		res += catalan(i)*catalan(n-i-1); 

	return res; 
} 

// اختبار الدالة السابقة
int main() 
{ 
	for (int i=0; i<10; i++) 
		cout << catalan(i) << " "; 
	return 0; 
}

• بايثون:

def catalan(n): 
	# الحالة الأساس
	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 

# اختبار الدالة السابقة
for i in range(10): 
	print catalan(i),

• جافا:

class CatalnNumber { 

	int catalan(int n) { 
		int res = 0; 
		
		// الحالة الأساس
		if (n <= 1) { 
			return 1; 
		} 
		for (int i = 0; i < n; i++) { 
			res += catalan(i) * catalan(n - i - 1); 
		} 
		return res; 
	} 

	public static void main(String[] args) { 
		CatalnNumber cn = new CatalnNumber(); 
		for (int i = 0; i < 10; i++) { 
			System.out.print(cn.catalan(i) + " "); 
		} 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

1 1 2 5 14 42 132 429 1430 4862

التعقيد الزمني

التعقيد الزمني لهذه الطريقة أسّي exponential.

طريقة البرمجة الديناميكية

يمكن ملاحظة أنّ الطريقة التعاودية تؤدي الكثير من العمل المكرّر، ونظرًا لوجود مشاكل فرعية متداخلة مع بعضها البعض، يمكن استخدام البرمجة الديناميكية لحل هذه المسألة.

تعرض الأمثلة التالية كيفية تنفيذ هذه الطريقة في عدد من لغات البرمجة:

• C++‎:

#include<iostream> 
using namespace std; 

unsigned long int catalanDP(unsigned int n) 
{ 
	// جدول لتخزين نتائج المشاكل الفرعية
	unsigned long int catalan[n+1]; 

	// تهيئة أول قيمتين في الجدول
	catalan[0] = catalan[1] = 1; 

	// catalan[] تعبئة العناصر في مصفوفة
	// باستخدم الصيغة التعاودية
	for (int i=2; i<=n; i++) 
	{ 
		catalan[i] = 0; 
		for (int j=0; j<i; j++) 
			catalan[i] += catalan[j] * catalan[i-j-1]; 
	} 

	// إعادة العنصر الأخير
	return catalan[n]; 
} 

// اختبار الدالة السابقة
int main() 
{ 
	for (int i = 0; i < 10; i++) 
		cout << catalanDP(i) << " "; 
	return 0; 
}

• بايثون:

def catalan(n): 
	if (n == 0 or n == 1): 
		return 1

	# جدول لتخزين نتائج حل المشاكل الفرعية
	catalan = [0 for i in range(n + 1)] 

	# تهيئة أول قيمتين في الجدول
	Catalan[0] = 1
	catalan[1] = 1

	# catalan[] تعبئة العناصر في مصفوفة
	# باستخدم الصيغة التعاودية
	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] 

# اختبار الدالة السابقة
for i in range (10): 
	print (catalan(i),end=" ")

• جافا:

class GFG{ 

	static int catalanDP(int n) { 
		// جدول لتخزين نتائج حل المشاكل الفرعية
		int catalan[] = new int[n + 2]; 

		// تهيئة أول قيمتين في الجدول
		catalan[0] = 1; 
		catalan[1] = 1; 

		// catalan[] تعبئة العناصر في مصفوفة
		// باستخدم الصيغة التعاودية 
		for (int i = 2; i <= n; i++) { 
			catalan[i] = 0; 
			for (int j = 0; j < i; j++) { 
				catalan[i] += catalan[j] * catalan[i - j - 1]; 
			} 
		} 

		// إعادة العنصر الأخير
		return catalan[n]; 
	} 

// اختبار التابع السابق
	public static void main(String[] args) { 
		for (int i = 0; i < 10; i++) { 
			System.out.print(catalanDP(i) + " "); 
		} 
	} 
}

تعطي الشيفرات السابقة المعطيات التالية:

1 1 2 5 14 42 132 429 1430 4862

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الطريقة المقدار O(n^2)‎.

طريقة المعامل ثنائي الحدود

يمكن استخدام طريقة المعامل ثنائي الحدود Binomial Coefficient لحساب العدد ذو الترتيب n من الأعداد الكاتالانية، وذلك باستخدام الصيغة الرياضية التالية:

تعرض الأمثلة التالية كيفية تنفيذ هذه الطريقة في عدد من لغات البرمجة:

• C++‎:

#include<iostream> 
using namespace std; 

// C(n, k) تعيد الدالة قيمة المعامل ثنائي الحدود 
unsigned long int binomialCoeff(unsigned int n, unsigned int k) 
{ 
	unsigned long int res = 1; 

	// C(n, k) = C(n, n-k) لما كان
	if (k > n - k) 
		k = n - k; 

	// [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1] حساب المقدار
	for (int i = 0; i < k; ++i) 
	{ 
		res *= (n - i); 
		res /= (i + 1); 
	} 

	return res; 
} 

// دالة تعتمد على المعامل ثنائي الحدود لإيجاد العدد الكاتالاني وبالترتيب المعطى
unsigned long int catalan(unsigned int n) 
{ 
	// 2nCn حساب قيمة المقدار 
	unsigned long int c = binomialCoeff(2*n, n); 

	// 2nCn/(n+1) إعادة القيمة
	return c/(n+1); 
} 

// اختبار الدالتين السابقتين
int main() 
{ 
	for (int i = 0; i < 10; i++) 
		cout << catalan(i) << " "; 
	return 0; 
}

• بايثون:

# C(n, k) تعيد الدالة قيمة المعامل ثنائي الحدود 
def binomialCoefficient(n, k): 

	# C(n, k) = C(n, n-k) لما كان
	if (k > n - k): 
		k = n - k 

	# تهيئة النتيجة 
	res = 1

	# [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1] حساب المقدار 
	for i in range(k): 
		res = res * (n - i) 
		res = res / (i + 1) 
	return res 

# دالة تعتمد على المعامل ثنائي الحدود
# لإيجاد العدد الكاتالاني وبالترتيب المعطى 
def catalan(n): 
	c = binomialCoefficient(2*n, n) 
	return c/(n + 1) 

# اختبار الدالتين السابقتين
for i in range (10): 
	print (catalan(i),end=" ")

• جافا:

class GFG { 

// C(n, k) تعيد الدالة قيمة المعامل ثنائي الحدود 
	static long binomialCoeff(int n, int k) { 
		long res = 1; 

		// C(n, k) = C(n, n-k) لما كان 
		if (k > n - k) { 
			k = n - k; 
		} 

		// [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1] حساب المقدار 
		for (int i = 0; i < k; ++i) { 
			res *= (n - i); 
			res /= (i + 1); 
		} 

		return res; 
	} 

// دالة تعتمد على المعامل ثنائي الحدود لإيجاد العدد الكاتالاني وبالترتيب المعطى 
	static long catalan(int n) { 
		// 2nCn حساب قيمة المقدار 
		long c = binomialCoeff(2 * n, n); 

		// 2nCn/(n+1) إعادة القيمة 
		return c / (n + 1); 
	} 

// اختبار الدالتين السابقتين 
	public static void main(String[] args) { 
		for (int i = 0; i < 10; i++) { 
			System.out.print(catalan(i) + " "); 
		} 

	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

1 1 2 5 14 42 132 429 1430 4862

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الطريقة المقدار O(n)‎.

مصادر

• صفحة Program for nth Catalan Number في توثيق الخوارزميات في موقع GeeksforGeeks.