مسألة الكسر المصري

يمكن تمثيل أي كسر موجب كمجموع لعدد من الكسور الوحدية unit fractions الفريدة. يكون الكسر كسرًا وحديًا عندما يكون بسطه 1 ومقامه عددًا صحيحًا موجبًا، فعلى سبيل المثال يمثل الكسر 1/3 كسرًا وحديًّا. تسمى طريقة التمثيل هذه بالكسر المصري Egyptian Fraction وذلك لأنّها كانت تستخدم من قبل المصريين القدماء.

تعرض الأمثلة التالية بعض التمثيلات لعدد من الكسور بطريقة الكسر المصري:

الكسر المصري للكسر 2/3 هي 1/2 + 1/6
الكسر المصري للكسر 6/14 هي 1/3 + 1/11 + 1/231
الكسر المصري للكسر 12/13 هي 1/2 + 1/3 + 1/12 + 1/156

يمكن إنشاء الكسور المصرية باستخدام الخوارزميات الجشعة. فلو كان لدينا عدد بالصيغة nr/dr إذ dr > nr، فإنّ الخوارزمية تبحث في البداية عن أكبر كسر وحدي ممكن، ثم تعيد العمل نفسه على الأجزاء المتبقية. فعلى سبيل المثال لو نظرنا إلى الكسر 6/14 فإنّ الخوارزمية تحسب في البداية النتيجة المقربة لأعلى ceiling للكسر 14/6 وهي 3؛ لذا فإنّ أول كسر وحدي سيكون 1/3، ثم تعيد العمل نفسه على حاصل العملية (6/14 - 1/3) وهو 4/42... وهكذا.

تنفيذ الخوارزمية

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

• C++‎:

#include <iostream> 
using namespace std; 

void printEgyptian(int nr, int dr) 
{ 
	// إن كان البسط أو المقام صفرًا
	if (dr == 0 || nr == 0) 
		return; 

	// إن كان المقام يقبل القسمة على البسط، فإنّ القسمة البسيطة
	// 1/n تحول الكسر إلى صيغة
	if (dr%nr == 0) 
	{ 
		cout << "1/" << dr/nr; 
		return; 
	} 

	// إن كان البسط يقبل القسمة على المقام، لا يكون العدد المعطى كسرًا
	if (nr%dr == 0) 
	{ 
		cout << nr/dr; 
		return; 
	} 

	// إن كان البسط أكبر من المقام
	if (nr > dr) 
	{ 
		cout << nr/dr << " + "; 
		printEgyptian(nr%dr, dr); 
		return; 
	} 

	// الوصول إلى هنا يعني أنّ المقام أكبر من البسط وأن باقي قسمة البسط على المقام أكبر ليس صفرًا
	// نقرب حاصل قسمة المقام على البسط إلى أكبر عدد صحيح ونطبع الناتج على هيئة كسر
	int n = dr/nr + 1; 
	cout << "1/" << n << " + "; 

	// تستدعي الدالة نفسها وتستخدم الأجزاء المتبقية كمعاملات
	printEgyptian(nr*n-dr, dr*n); 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int nr = 6, dr = 14; 
	cout << "Egyptian Fraction Representation of "
		<< nr << "/" << dr << " is\n "; 
	printEgyptian(nr, dr); 
	return 0; 
}

• بايثون:

# math استيراد الحزمة
# وذلك لاستخدامها في تقريب ناتج القسمة إلى أكبر عدد صحيح
import math 

def egyptianFraction(nr, dr): 

	print("The Egyptian Fraction " +
		"Representation of {0}/{1} is". 
				format(nr, dr), end="\n") 

	# قائمة فارغة لتخزين قيم المقام
	ef = [] 

	# تستمر الحلقة التكرارية في عملها
	# إلى أن يصبح الكسر صفرًا
	# أي يصبح البسط صفرًا
	while nr != 0: 

		# نقرب العدد العشري إلى أكبر عدد صحيح
		x = math.ceil(dr / nr) 

		# ef تخزين القيمة في قائمة
		ef.append(x) 

		# تحديث قيمتي البسط والمقام
		nr = x * nr - dr 
		dr = dr * x 

	# طباعة القيم 
	for i in range(len(ef)): 
		if i != len(ef) - 1: 
			print(" 1/{0} +" . 
					format(ef[i]), end = " ") 
		else: 
			print(" 1/{0}" . 
					format(ef[i]), end = " ") 

# طباعة النتيجة
egyptianFraction(6, 14)

• جافا:

class GFG { 

	static void printEgyptian(int nr, int dr) { 
		// إن كان البسط أو المقام صفرًا
		if (dr == 0 || nr == 0) { 
			return; 
		} 

		// إن كان المقام يقبل القسمة على البسط، فإنّ القسمة البسيطة
	// 1/n تحول الكسر إلى صيغة
		if (dr % nr == 0) { 
			System.out.print("1/" + dr / nr); 
			return; 
		} 

		// إن كان البسط يقبل القسمة على المقام، لا يكون العدد المعطى كسرًا
		if (nr % dr == 0) { 
			System.out.print(nr / dr); 
			return; 
		} 

		//  إن كان البسط أكبر من المقام 
		if (nr > dr) { 
			System.out.print(nr / dr + " + "); 
			printEgyptian(nr % dr, dr); 
			return; 
		} 

		// الوصول إلى هنا يعني أنّ المقام أكبر من البسط وأن باقي قسمة البسط على المقام أكبر ليس صفرًا
		// نقرب حاصل قسمة المقام على البسط إلى أعلى عدد صحيح ونطبع الناتج على هيئة كسر
		int n = dr / nr + 1; 
		System.out.print("1/" + n + " + "); 

		//  تستدعي الدالة نفسها وتستخدم الأجزاء المتبقية كمعاملات 
		printEgyptian(nr * n - dr, dr * n); 
	} 

// اختبار الدالة السابقة
	public static void main(String[] args) { 
		int nr = 6, dr = 14; 
		System.out.print("Egyptian Fraction Representation of "
				+ nr + "/" + dr + " is\n "); 
		printEgyptian(nr, dr); 
	} 
}

هذه الخوارزمية خوارزمية جشعة لأنّها تختزل قيمة الكسر دائمًا إلى صيغة يكون فيها المقام أكبر من البسط، ولا يكون المقام قابلًا للقسمة على البسط. وتأخذ الدالة المستدعاة تعاوديًا البسط المختزل كمعامل لها، وبهذا تستمر الاستدعاءات التعاودية في اختزال البسط إلى أن تصبح قيمته 1.

مصادر

• صفحة Greedy Algorithm for Egyptian Fraction في توثيق الخوارزميات في موقع GeeksforGeeks.