Algorithms/ugly numbers

الأعداد القبيحة هي الأعداد التي تكون عواملها الأولية هي الأعداد ‎2, 3, 5‎. تمثل الأعداد ‎1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15...‎ أعدادًا قبيحة وقد جرى الاتفاق على إضافة العدد 1 إلى هذه المتتالية.

الطريقة البسيطة

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

يمكن التحقق من كون العدد قبيحًا أو لا بتقسيمه على أكبر قوّة للأعداد ‎2,3,4‎ يقبل العدد القسمة عليها، فإن حصلنا على الرقم 1 كان العدد قبيحًا.

فعلى سبيل المثال للتحقق من كون العدد 300 قبيحًا أو لا، يُقسّم على أكبر قوّة للعدد 2 يقبل القسمة عليها وهي العدد 4، ويكون الناتج 75، والذي يقسّم على أكبر قوّة للعدد 3 يقبل القسمة عليها وهي 3 للحصول على 25، والذي يقسّم على أكبر قوّة للعدد 5 يقبل القسمة عليها وهي 25 للحصول على 1. ولما كانت نهاية عمليات القسمة هي 1 فإن العدد 300 هو عدد قبيح.

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

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

• C++‎:

# include<stdio.h> 
# include<stdlib.h> 

/* تقسّم الدالة العدد الأول على أكبر قوة للعدد الثاني يقبل العدد الأول القسمة عليها */
int maxDivide(int a, int b) 
{ 
while (a%b == 0) 
a = a/b; 
return a; 
}	 

/* تتحقق الدالة من كون العدد المعطى قبيحًا أو لا */
int isUgly(int no) 
{ 
no = maxDivide(no, 2); 
no = maxDivide(no, 3); 
no = maxDivide(no, 5); 
	
return (no == 1)? 1 : 0; 
}	 

/* تعيد الدالة جميع الأعداد القبيحة وصولًا إلى العدد المعطى */
int getNthUglyNo(int n) 
{ 
int i = 1; 
int count = 1; /* تعداد الأعداد القبيحة */

/* التحقق من جميع الأعداد الصحيحة إلى أن يصل تعداد الأعداد القبيحة إلى العدد المعطى */
while (n > count) 
{ 
	i++;	 
	if (isUgly(i)) 
	count++; 
} 
return i; 
} 

/* اختبار الدوال السابقة */
int main() 
{ 
	unsigned no = getNthUglyNo(150); 
	printf("150th ugly no. is %d ", no); 
	getchar(); 
	return 0; 
}

• بايثون:

# تقسّم الدالة العدد الأول على أكبر قوة
# للعدد الثاني يقبل العدد الأول القسمة عليها 
def maxDivide( a, b ): 
	while a % b == 0: 
		a = a / b 
	return a 

# تتحقق الدالة من كون العدد المعطى قبيحًا أو لا 
def isUgly( no ): 
	no = maxDivide(no, 2) 
	no = maxDivide(no, 3) 
	no = maxDivide(no, 5) 
	return 1 if no == 1 else 0

# تعيد الدالة جميع الأعداد القبيحة وصولًا إلى العدد المعطى  
def getNthUglyNo( n ): 
	i = 1
	count = 1 # تعداد الأعداد القبيحة 

	# التحقق من جميع الأعداد الصحيحة
	# إلى أن يصل تعداد الأعداد القبيحة إلى العدد المعطى 
	while n > count: 
		i += 1
		if isUgly(i): 
			count += 1
	return i 

# اختبار الدوال السابقة  
no = getNthUglyNo(150) 
print("150th ugly no. is ", no)

• جافا:

class GFG { 
	
	/*تقسّم الدالة العدد الأول على أكبر قوة للعدد الثاني يقبل العدد الأول القسمة عليها*/
	static int maxDivide(int a, int b) 
	{ 
		while(a % b == 0) 
			a = a/b; 
		return a; 
	} 
	
	/* تتحقق الدالة من كون العدد المعطى قبيحًا أو لا  */
	static int isUgly(int no) 
	{ 
		no = maxDivide(no, 2); 
		no = maxDivide(no, 3); 
		no = maxDivide(no, 5); 
		
		return (no == 1)? 1 : 0; 
	} 
	
	/* تعيد الدالة جميع الأعداد القبيحة وصولًا إلى العدد المعطى*/
	static int getNthUglyNo(int n) 
	{ 
		int i = 1; 
		
		// تعداد الأعداد القبيحة 
		int count = 1; 
		
		// التحقق من جميع الأعداد الصحيحة
		// إلى أن يصل تعداد الأعداد القبيحة إلى العدد المعطى 
		while(n > count) 
		{ 
			i++; 
			if(isUgly(i) == 1) 
				count++; 
		} 
		return i; 
	} 
	
	/* اختبار الدوال السابقة  */
	public static void main(String args[]) 
	{ 
		int no = getNthUglyNo(150); 
		System.out.println("150th ugly "
					+ "no. is "+ no); 
	} 
}

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

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

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

لما كانت الأعداد القبيحة تقبل القسمة على الأعداد ‎2, 3, 5‎، فيمكن تقسيم تسلسل الأاعداد القبيحة إلى ثلاث مجموعات:

(1) 1×2, 2×2, 3×2, 4×2, 5×2, …
(2) 1×3, 2×3, 3×3, 4×3, 5×3, …
(3) 1×5, 2×5, 3×5, 4×5, 5×5, …

ويمكن ملاحظة أنّ كل تسلسل فرعي هو تسلسل أعداد قبيحة في حد ذاته، أي ‎(1, 2, 3, 4, 5, ...)‎ مضروبًا بالأعداد 2 و 3 و 5. يمكن استخدام طريقة للدمج تشبه طريقة الترتيب بالدمج للحصول على جميع الأعداد القبيحة من التسلسلات الفرعية الثلاثة. يجري اختيار أصغر عدد في كل خطوة ثم الانتقال إلى خطوة واحدة إلى الأمام.

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

تتبع طريقة البرمجة الديناميكية الخطوات التالية:

1. إنشاء مصفوفة فارغة لجمع الأعداد القبيحة.
2. إضافة العدد 1 في بداية المصفوفة.
3. تهيئة ثلاثة متغيرات تمثل مواقع في المصفوفة i2, i3, i5 للإشارة إلى أول عنصر في مصفوفة الأعداد القبيحة.
4. تهيئة ثلاثة اختيارات للعدد القبيح التالي.
5. تنفيذ حلقة تكرارية لتعبئة المصفوفة بالأعداد القبيحة وصولًا إلى العدد المطلوب.

مثال:

يعرض المثال التالي الخطوات التي تمرّ بها الخوارزمية لإيجاد الأعداد القبيحة وصولًا إلى العدد 150:

تهيئة المتغيرات:
   ugly[] =  | 1 |
   i2 =  i3 = i5 = 0;

الدورة الأولى: 
   ugly[1] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
            = Min(2, 3, 5)
            = 2
   ugly[] =  | 1 | 2 |
   i2 = 1,  i3 = i5 = 0  (i2 got incremented ) 

الدورة الثانية:
    ugly[2] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
             = Min(4, 3, 5)
             = 3
    ugly[] =  | 1 | 2 | 3 |
    i2 = 1,  i3 =  1, i5 = 0  (i3 got incremented ) 

الدورة الثالثة:
    ugly[3] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
             = Min(4, 6, 5)
             = 4
    ugly[] =  | 1 | 2 | 3 |  4 |
    i2 = 2,  i3 =  1, i5 = 0  (i2 got incremented )

الدورة الرابعة:
    ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
              = Min(6, 6, 5)
              = 5
    ugly[] =  | 1 | 2 | 3 |  4 | 5 |
    i2 = 2,  i3 =  1, i5 = 1  (i5 got incremented )

الدورة الخامسة:
    ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
              = Min(6, 6, 10)
              = 6
    ugly[] =  | 1 | 2 | 3 |  4 | 5 | 6 |
    i2 = 3,  i3 =  2, i5 = 1  (i2 and i3 got incremented )

الاستمرار بنفس الطريقة إلى حين الوصول إلى 150

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

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

• C++‎:

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

unsigned getNthUglyNo(unsigned n) 
{ 
	unsigned ugly[n]; // تخزّن المصفوفة الأعداد القبيحة
	unsigned i2 = 0, i3 = 0, i5 = 0; 
	unsigned next_multiple_of_2 = 2; 
	unsigned next_multiple_of_3 = 3; 
	unsigned next_multiple_of_5 = 5; 
	unsigned next_ugly_no = 1; 

	ugly[0] = 1; 
	for (int i=1; i<n; i++) 
	{ 
	next_ugly_no = min(next_multiple_of_2, 
						min(next_multiple_of_3, 
							next_multiple_of_5)); 
	ugly[i] = next_ugly_no; 
	if (next_ugly_no == next_multiple_of_2) 
	{ 
		i2 = i2+1; 
		next_multiple_of_2 = ugly[i2]*2; 
	} 
	if (next_ugly_no == next_multiple_of_3) 
	{ 
		i3 = i3+1; 
		next_multiple_of_3 = ugly[i3]*3; 
	} 
	if (next_ugly_no == next_multiple_of_5) 
	{ 
		i5 = i5+1; 
		next_multiple_of_5 = ugly[i5]*5; 
	} 
	} 
	return next_ugly_no; 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int n = 150; 
	cout << getNthUglyNo(n); 
	return 0; 
}

• بايثون:

def getNthUglyNo(n): 

	ugly = [0] * n # To store ugly numbers 

	# العدد 1 هو أول عدد قبيح
	ugly[0] = 1

	# تمثّل هذه المتغيرات مواقع الأعداد 2 و 3 و 5
	i2 = i3 =i5 = 0

	# تعيين القيمة الأوّلية
	# set initial multiple value 
	next_multiple_of_2 = 2
	next_multiple_of_3 = 3
	next_multiple_of_5 = 5

	# تنفيذ حلقة تكرارية لإيجاد القيمة ضمن النطاق المعطى
	for l in range(1, n): 

		# اختيار القيمة الأصغر من بين المضاعفات المتاحة
		ugly[l] = min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5) 

		# زيادة قيمة الفهرس تبعًا لذلك
		# increment the value of index accordingly 
		if ugly[l] == next_multiple_of_2: 
			i2 += 1
			next_multiple_of_2 = ugly[i2] * 2

		if ugly[l] == next_multiple_of_3: 
			i3 += 1
			next_multiple_of_3 = ugly[i3] * 3

		if ugly[l] == next_multiple_of_5: 
			i5 += 1
			next_multiple_of_5 = ugly[i5] * 5

	return ugly[-1] 

def main(): 

	n = 150

	print getNthUglyNo(n) 


if __name__ == '__main__': 
	main()

• جافا:

import java.lang.Math; 

class UglyNumber 
{ 
	int getNthUglyNo(int n) 
	{ 
		int ugly[] = new int[n]; // تخزّن المصفوفة الأعداد القبيحة
		int i2 = 0, i3 = 0, i5 = 0; 
		int next_multiple_of_2 = 2; 
		int next_multiple_of_3 = 3; 
		int next_multiple_of_5 = 5; 
		int next_ugly_no = 1; 
		
		ugly[0] = 1; 
		
		for(int i = 1; i < n; i++) 
		{ 
			next_ugly_no = Math.min(next_multiple_of_2, 
								Math.min(next_multiple_of_3, 
										next_multiple_of_5)); 
			
			ugly[i] = next_ugly_no; 
			if (next_ugly_no == next_multiple_of_2) 
			{ 
			i2 = i2+1; 
			next_multiple_of_2 = ugly[i2]*2; 
			} 
			if (next_ugly_no == next_multiple_of_3) 
			{ 
			i3 = i3+1; 
			next_multiple_of_3 = ugly[i3]*3; 
			} 
			if (next_ugly_no == next_multiple_of_5) 
			{ 
			i5 = i5+1; 
			next_multiple_of_5 = ugly[i5]*5; 
			} 
		} 
		return next_ugly_no; 
	} 

	/* اختبار الدالة السابقة */
	public static void main(String args[]) 
	{ 
		int n = 150; 
		UglyNumber obj = new UglyNumber(); 
		System.out.println(obj.getNthUglyNo(n)); 
	} 
}

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

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

مصادر

• صفحة Ugly Numbers في توثيق الخوارزميات في موقع GeeksforGeeks.