تقسيم مكعب إلى مكعبات بأقصى حجم ممكن

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

مثال:

Input : l = 2, b = 4, h = 6
Output : 2 6

يمكن تقسيم المكعب ذي الطول 2 والعرض 4 والارتفاع 6 إلى 6 مكعبات قياس كل ضلع فيها 2.

أحجام المكعبات = 6*(2*2*2) = 6*8 = 48
حجم المكعب الأصلي = 2*4*6 = 48

خطوات الخوارزمية

يجب أن لا نفقد في عملية التقسيم أيّ مقدار من حجم المكعب وذلك لأننا نرغب في الحصول على أكبر مجموع لأحجام المكعبات الصغيرة، لذا يجب تقسيم كل جانب في المكعب الأصلي على جميع المكعبات، ولمّا كانت جوانب المضلع الثلاثة متساوية، فيجب أن يكون كل ضلع قابلًا للقسمة على العدد نفسه (ليكن x) والذي سيكون جانب المكعب. لذا يجب زيادة قيمة x والتي ستقسم قيم الطول والعرض والارتفاع المعطاة، وأكبر قيمة للعدد x هي القاسم المشترك الأكبر لقيم الطول والعرض والارتفاع. لذا فإنّ طول المكعب سيكون القاسم المشترك الأكبر لأبعاد المكعب الثلاثة.

يمكن حساب عدد المكعبات الناتجة بعد التقسيم وذلك بحساب مساحة أحد المكعبات، وبذلك يصبح عدد المكعبات الكلي مساويًا لحجم المكعب الأصلي\حجم المكعب.

no. of cubes = (l * b * h)/(x * x * x)

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

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

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

void maximizecube(int l, int b, int h) 
{ 
	// القاسم المشترك الأكبر
	int side = __gcd(l, __gcd(b, h)); 

	// حساب عدد المكعبات
	int num = l / side; 
	num = (num * b / side); 
	num = (num * h / side); 

	cout << side << " " << num << endl; 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int l = 2, b = 4, h = 6; 

	maximizecube(l, b, h); 
	return 0; 
}

• بايثون:

from fractions import gcd 

def maximizecube( l , b , h ): 

	# القاسم المشترك الأكبر
	side = gcd(l, gcd(b, h)) 
	
    # حساب عدد المكعبات
	# dividing to find number of cubes. 
	num = int(l / side) 
	num = int(num * b / side) 
	num = int(num * h / side) 
	
	print(side, num) 

# اختبار الدالة السابقة
l = 2
b = 4
h = 6

maximizecube(l, b, h)

• جافا:

import java.util.*; 

class GFG { 
	
	static int gcd(int m, int n) 
	{ 
		if(n == 0) 
			return m; 
		else if(n > m) 
			return gcd(n,m); 
		else
			return gcd(n, m % n); 
	} 
	
	static void maximizecube(int l, int b, 
									int h) 
	{ 
		// القاسم المشترك الأكبر
		int side = gcd(l, gcd(b, h)); 
	
		// حساب عدد المكعبات
		int num = l / side; 
		num = (num * b / side); 
		num = (num * h / side); 
	
	System.out.println( side + " " + num); 
	} 
	
	/* Driver program */
	public static void main(String[] args) 
	{ 
		int l = 2, b = 4, h = 6; 
		maximizecube(l, b, h); 
	} 
}

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

2 6

مصادر

• صفحة Divide cuboid into cubes such that sum of volumes is maximum في توثيق الخوارزميات في موقع GeeksforGeeks.