إيجاد حاصل ضرب عددين دون استخدام العوامل الحسابية

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

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

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

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

• C++‎:

#include<iostream> 

using namespace std; 
class GFG 
{ 
	
public : int multiply(int x, int y) 
{ 
	/* حاصل ضرب أي رقم مع الصفر هو الصفر */
	if(y == 0) 
	return 0; 

	/* إضافة العدد الأول إلى نفسه خطوة خطوة */
	if(y > 0 ) 
	return (x + multiply(x, y-1)); 

	/* إذا كان العدد الثاني سالبًا */
	if(y < 0 ) 
	return -multiply(x, -y); 
} 
}; 

// اختبار الدالة السابقة
int main() 
{ 
	GFG g; 
	cout << endl << g.multiply(5, -11); 
	getchar(); 
	return 0; 
}

• بايثون:

def multiply(x,y): 

	# حاصل ضرب أي رقم مع الصفر هو الصفر
	if(y == 0): 
		return 0

	# إضافة العدد الأول إلى نفسه خطوة خطوة
	if(y > 0 ): 
		return (x + multiply(x, y - 1)) 

	# إذا كان العدد الثاني سالبًا 
	if(y < 0 ): 
		return -multiply(x, -y) 
	
# اختبار الدالة السابقة
print(multiply(5, -11))

• جافا:

class GFG { 
	
	static int multiply(int x, int y) { 
		
		/* حاصل ضرب أي رقم مع الصفر هو الصفر */
		if (y == 0) 
			return 0; 
	
		/* إضافة العدد الأول إلى نفسه خطوة خطوة */
		if (y > 0) 
			return (x + multiply(x, y - 1)); 
	
		/* إذا كان العدد الثاني سالبًا */
		if (y < 0) 
			return -multiply(x, -y); 
			
		return -1; 
	} 
	
	// اختبار التابع السابق
	public static void main(String[] args) { 
		
		System.out.print("\n" + multiply(5, -11)); 
	} 
}

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

-55

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

يبلغ التعقيد الزمني لهذه الخوارزمية المقدار O(y)‎ ويمثّل y قيمة العدد الثاني.

مصادر

• صفحة Multiply two integers without using multiplication, division and bitwise operators, and no loops في توثيق الخوارزميات في موقع GeeksforGeeks.