إيجاد أقل فارق بين مجموعتين فرعيتين

من موسوعة حسوب
اذهب إلى: تصفح، ابحث

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

فمثلاً:

المدخلات : n = 4
المخرجات : مجموع عناصر المجموعة الفرعية الأولى = 5 
         مجموع عناصر المجموعة الفرعية الأولى = 5
         الفارق = 0

التوضيح:
المجموعة الفرعية 1: 1 4 
المجموعة الفرعية 2: 2 3
المدخلات : n = 6
المخرجات : مجموع عناصر المجموعة الفرعية الأولى = 10 
         مجموع عناصر المجموعة الفرعية الأولى = 11
         الفارق = 0

التوضيح:
المجموعة الفرعية 1: 1 3 6 
المجموعة الفرعية 2: 2 4 5

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

تعتمد هذه الخوارزمية على حقيقة مفادها أنّ بالإمكان تقسيم أي أربعة أرقام متتابعة إلى مجموعتين، تتضمن المجموعة الأولى العددين الوسطيين، والمجموعة الثانية العددين الطرفيين. إن كان عدد الأرقام n من مضاعفات العدد 4 فإنّ الفارق بين مجموعي عناصر كل من المجموعتين يساوي 0. هذا يعني أنّ مجموع عناصر أي من المجموعتين سيساوي نصف مجموع العناصر في المجموعة الأصلية، والذي يمكن حسابه باستخدام العلاقة: sum = n*(n+1)/2

هناك ثلاث حالات إضافية لا يمكن فيه تقسيم المجموعات إلى 4 عناصر، وسيكون الفارق في هذه الحالات هو 1 و 2 و 3:

  1. إن كان الفارق يساوي 1 فإنّ جميع العناصر الأخرى n-1 ستقسّم في مجموعات من 4 عناصر وبهذا فإن مجموع هذه العناصر سيساوي int(sum/2)‎ أما مجموع عناصر النصف الآخر فيساوي int(sum/2+1)‎، ويساوي الفارق بينهما 1 دائمًا.
  2. إذا كان باقي قسمة n على 4 يساوي 2 فإنّنا سنتبع الخطوات السابقة نفسها، إذ سنكوّن مجموعات تتضمن أربعة عناصر تبدأ من الرقم 3 وما بعده، وسيتبقى رقمان هما 1 و2، فيضاف الرقم 1 إلى مجموعة ويضاف الرقم 2 إلى الأخرى.
  3. إذا كان باقي قسمة n على 4 يساوي 3، فسنكوّن مجموعات تتضمن أربعة عناصر تبدأ من الرقم 4، وستتبقى الأرقام 1 و2 و 3. يضاف الرقمان 1 و 2 إلى مجموعة، ويضاف الرقم 3 إلى الأخرى، وبهذا يساوي الفارق 0 ويكون مجموع عناصر كل مجموعة مساويًا للمقدار sum/2.

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

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

  • C++‎:
#include <bits/stdc++.h> 
using namespace std; 

void subsetDifference(int n) 
{ 
	// مجموع عناصر المجموعة الأصلية
	int s = n * (n + 1) / 2; 

	// إن كان عدد العناصر يقبل القسمة على 4
	if (n % 4 == 0) { 
		cout << "First subset sum = "
			<< s / 2; 
		cout << "\nSecond subset sum = "
			<< s / 2; 
		cout << "\nDifference = " << 0; 
	} 
	else { 

		// إن كان باقي القسمة يساوي 1 أو 2.
		// إن كان باقي القسمة يساوي 2 فسنقسم العناصر
		// من الرقم 3 إلى الرقم المعطى إلى مجموعات ذات 4 عناصر
		// ونضيف الرقم 1 إلى إحدى المجموعات و 2 إلى مجموعة أخرى
		// يساوي الفارق في هذه الحالة 1
		if (n % 4 == 1 || n % 4 == 2) { 

			cout << "First subset sum = "
				<< s / 2; 
			cout << "\nSecond subset sum = "
				<< s / 2 + 1; 
			cout << "\nDifference = " << 1; 
		} 

		// نضع العناصر من الرقم 4 إلى العدد المعطى في مجموعات
		// ذات أربعة عناصر. يمكن تقسيم العناصر الباقية وهي
		// 1 و 2 و 3 إلى (1,2) و (3)
		else
		{ 
			cout << "First subset sum = "
				<< s / 2; 
			cout << "\nSecond subset sum = "
				<< s / 2; 
			cout << "\nDifference = " << 0; 
		} 
	} 
} 

// اختبار الدالة السابقة 
int main() 
{ 
	int n = 6; 
	subsetDifference(n); 
	return 0; 
}
  • بايثون:
def subsetDifference( n ): 

	# مجموع عناصر المجموعة الأصلية 
	s = int(n * (n + 1) / 2) 
	
	# إن كان عدد العناصر يقبل القسمة على 4
	if n % 4 == 0: 
		print("First subset sum = ", int(s / 2)) 
		print("Second subset sum = ",int(s / 2)) 
		print("Difference = " , 0) 

	else: 

		# إن كان باقي القسمة يساوي 1 أو 2. 
		# إن كان باقي القسمة يساوي 2 فسنقسم العناصر 
		# من الرقم 3 إلى الرقم المعطى إلى مجموعات ذات 4 عناصر 
		# ونضيف الرقم 1 إلى إحدى المجموعات و 2 إلى مجموعة أخرى
		#  يساوي الفارق في هذه الحالة 1
		if n % 4 == 1 or n % 4 == 2: 
			print("First subset sum = ",int(s/2)) 
			print("Second subset sum = ",int(s/2)+1) 
			print("Difference = ", 1) 
			
		# نضع العناصر من الرقم 4 إلى العدد المعطى في مجموعات 
		# ذات أربعة عناصر. يمكن تقسيم العناصر الباقية وهي 
		# 1 و 2 و 3 إلى (1,2) و (3) 
		else: 
			print("First subset sum = ", int(s / 2)) 
			print("Second subset sum = ",int(s / 2)) 
			print("Difference = " , 0) 
			
# اختبار الدالة السابقة
n = 6
subsetDifference(n)
  • جافا:
import java.util.*; 

class GFG { 
	
	static void subsetDifference(int n) 
	{ 
		// مجموع عناصر المجموعة الأصلية
		int s = n * (n + 1) / 2; 
	
		// إن كان عدد العناصر يقبل القسمة على 4
		if (n % 4 == 0) { 

				System.out.println("First subset sum = " + s / 2); 
				System.out.println("Second subset sum = " + s / 2); 
				System.out.println("Difference = " + 0); 
		} 
		else { 
	
			// إن كان باقي القسمة يساوي 1 أو 2.
			// إن كان باقي القسمة يساوي 2 فسنقسم العناصر
			// من الرقم 3 إلى الرقم المعطى إلى مجموعات ذات 4 عناصر
			// ونضيف الرقم 1 إلى إحدى المجموعات و 2 إلى مجموعة أخرى
			// يساوي الفارق في هذه الحالة 1
			if (n % 4 == 1 || n % 4 == 2) { 
	
				System.out.println("First subset sum = " + s / 2); 
				System.out.println("Second subset sum = " + ((s / 2) + 1)); 
				System.out.println("Difference = " + 1); 
			} 
	
			// نضع العناصر من الرقم 4 إلى العدد المعطى في مجموعات 
			//  ذات أربعة عناصر. يمكن تقسيم العناصر الباقية وهي
			// 1 و 2 و 3 إلى (1,2) و (3) 
			else
			{ 
				System.out.println("First subset sum = " + s / 2); 
				System.out.println("Second subset sum = " + s / 2); 
				System.out.println("Difference = " + 0); 
			} 
		} 
	} 
	
	/* اختبار الدالة السابقة */
	public static void main(String[] args) 
	{ 
		int n = 6; 
		subsetDifference(n); 
	} 
}

مصادر