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

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

مثال:

Input : a = 10, b = 3
Output : 3

Input : a = 43, b = -8
Output :  -5

الطريقة العادية

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

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

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

C++‎:

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

// تقسّم الدالة العدد الأول على الثاني وتعيد الناتج مقرّبًا
int divide(int dividend, int divisor) { 

// تحديد إشارة القاسم
// أي أن الإشارة ستكون سالبة إذا -وفقط إذا-
// كان أحد العددين سالبًا، وإلا فإنّ الإشارة ستكون موجبة
int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1; 

// حساب القيمة المطلقة للقاسم والمقسوم عليه
dividend = abs(dividend); 
divisor = abs(divisor); 

// تهيئة المتغير الذي سيحمل نتيجة القسمة
int quotient = 0; 
while (dividend >= divisor) { 
	dividend -= divisor; 
	++quotient; 
} 

return sign * quotient; 
} 

// اختبار الدالة السابقة 
int main() { 
int a = 10, b = 3; 
cout << divide(a, b) << "\n"; 

a = 43, b = -8; 
cout << divide(a, b); 

return 0; 
}

بايثون:

# تقسّم الدالة العدد الأول على الثاني وتعيد الناتج مقرّبًا
def divide(dividend, divisor): 

	# تحديد إشارة القاسم 
	# أي أن الإشارة ستكون سالبة إذا -وفقط إذا- 
	# كان أحد العددين سالبًا، وإلا فإنّ الإشارة ستكون موجبة 
	sign = -1 if ((dividend < 0) ^ (divisor < 0)) else 1
	
	# حساب القيمة المطلقة للقاسم والمقسوم عليه 
	dividend = abs(dividend) 
	divisor = abs(divisor) 
	
	# تهيئة المتغير الذي سيحمل نتيجة القسمة 
	quotient = 0
	while (dividend >= divisor): 
		dividend -= divisor 
		quotient += 1
	
	
	return sign * quotient 


# اختبار الدالة السابقة 
a = 10
b = 3
print(divide(a, b)) 
a = 43
b = -8
print(divide(a, b))

جافا:

import java.io.*; 

class GFG 
{ 
	
	// يقسّم التابع العدد الأول على الثاني وتعيد الناتج مقرّبًا
	static int divide(int dividend, int divisor) 
	{ 
		
		// تحديد إشارة القاسم
		// أي أن الإشارة ستكون سالبة إذا -وفقط إذا- 
		// كان أحد العددين سالبًا، وإلا فإنّ الإشارة ستكون موجبة 
		int sign = ((dividend < 0) ^ 
				(divisor < 0)) ? -1 : 1; 
	
		// حساب القيمة المطلقة للقاسم والمقسوم عليه 
		dividend = Math.abs(dividend); 
		divisor = Math.abs(divisor); 
	
		// تهيئة المتغير الذي سيحمل نتيجة القسمة 
		int quotient = 0; 
		
		while (dividend >= divisor) 
		{ 
			dividend -= divisor; 
			++quotient; 
		} 
	
		return sign * quotient; 
	}	 

	// اختبار التابع السابق
	public static void main (String[] args) 
	{ 
		int a = 10; 
		int b = 3; 
		
		System.out.println(divide(a, b)); 
		
		a = 43; 
		b = -8; 
		
		System.out.println(divide(a, b)); 
	} 
}

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

3
-5

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

يبلغ التعقيد الزمني لهذه الخوارزمية المقدار O(a)‎‎، وتحتاج إلى مساحة ساندة قدرها O(1)‎.

حل المسألة باستخدام خوارزميات البتات

يمكن استخدام العمليات الخاصة بالبتات لإيجاد ناتج القسمة، وذلك بالاعتماد على العلاقة الرياضية التالية:

المقسوم عليه = ناتج القسمة * القاسم + باقي القسمة
dividend = quotient * divisor + remainder

لمّا كان كل عددٍ يُمثَّل في الحاسوب باستخدام الأساس 2 (0 أو 1) فيمكن تمثيل ناتج القسمة في نظام الأعداد الثنائي باستخدام عامل الإزاحة shift operator باتباع الطريقة التالية:

تحديد البت الأكثر أهمية في ناتج القسمة، وذلك بالمرور على الموقع i من البت 31 إلى 1.
العثور على أول بت يكون ناتج العملية divisior << i أصغر من المقسوم عليه، ثم الاستمرار في تحديث الموقع i للبت الذي ينطبق عليه هذا الشرط.
إضافة الناتج إلى متغير مؤقت للتحقق من الموقع التالي بشرط أن يكون ناتج العملية (temp + (divisor << i))‎ أصغر من قيمة المقسوم عليه.
تعاد النتيجة النهائية لناتج القسمة بعد إيجاد الإشارة الصحيحة له.

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

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

C++‎:

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

// تقسّم الدالة العدد الأول على الثاني وتعيد الناتج مقرّبًا
int divide(long long dividend, long long divisor) { 

// تحديد إشارة القاسم
// أي أن الإشارة ستكون سالبة إذا -وفقط إذا-
// كان أحد العددين سالبًا، وإلا فإنّ الإشارة ستكون موجبة 
int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1; 

// حساب القيمة المطلقة للقاسم والمقسوم عليه
dividend = abs(dividend); 
divisor = abs(divisor); 

// تهيئة المتغير الذي سيحمل نتيجة القسمة
long long quotient = 0, temp = 0; 

// المرور على البتات بدءًا من أعلى بت
// وتجميع النتيجة المؤقتة للبتات المطابقة للشرط
for (int i = 31; i >= 0; --i) { 

	if (temp + (divisor << i) <= dividend) { 
	temp += divisor << i; 
	quotient |= 1LL << i; 
	} 
} 

return sign * quotient; 
} 

// اختبار الدالة السابقة 
int main() { 
int a = 10, b = 3; 
cout << divide(a, b) << "\n"; 

a = 43, b = -8; 
cout << divide(a, b); 

return 0; 
}

بايثون:

# تقسّم الدالة العدد الأول على الثاني وتعيد الناتج مقرّبًا
def divide(dividend, divisor): 
	
	# تحديد إشارة القاسم
	# أي أن الإشارة ستكون سالبة إذا -وفقط إذا-
	# كان أحد العددين سالبًا، وإلا فإنّ الإشارة ستكون موجبة
	
	sign = (-1 if((dividend < 0) ^ 
				(divisor < 0)) else 1); 
	
	# حساب القيمة المطلقة للقاسم والمقسوم عليه 
	dividend = abs(dividend); 
	divisor = abs(divisor); 
	
	# تهيئة المتغير الذي سيحمل نتيجة القسمة
	quotient = 0; 
	temp = 0; 
	
	# المرور على البتات بدءًا من أعلى بت
    # وتجميع النتيجة المؤقتة للبتات المطابقة للشرط
	for i in range(31, -1, -1): 
		if (temp + (divisor << i) <= dividend): 
			temp += divisor << i; 
			quotient |= 1 << i; 
	
	return sign * quotient; 

# اختبار الدالة السابقة
a = 10; 
b = 3; 
print(divide(a, b)); 

a = 43; 
b = -8; 
print(divide(a, b));

جافا:

import java.io.*; 
import java.util.*; 

// تقسّم الدالة العدد الأول على الثاني وتعيد الناتج مقرّبًا
class GFG 
{ 
public static long divide(long dividend, 
						long divisor) 
{ 

// تحديد إشارة القاسم
// أي أن الإشارة ستكون سالبة إذا -وفقط إذا-
// كان أحد العددين سالبًا، وإلا فإنّ الإشارة ستكون موجبة
long sign = ((dividend < 0) ^ 
			(divisor < 0)) ? -1 : 1; 

// حساب القيمة المطلقة للقاسم والمقسوم عليه
dividend = Math.abs(dividend); 
divisor = Math.abs(divisor); 

// تهيئة المتغير الذي سيحمل نتيجة القسمة 
long quotient = 0, temp = 0; 

// المرور على البتات بدءًا من أعلى بت
// وتجميع النتيجة المؤقتة للبتات المطابقة للشرط
// تعطي العملية 1<<31 أقل قيمة ممكنة للأعداد الصحيحة وهي نتيجة خاطئة، ولكن تعطي العملية
// 1L<<31
// إجابة صحيحة
for (int i = 31; i >= 0; --i) 
{ 

	if (temp + (divisor << i) <= dividend) 
	{ 
		temp += divisor << i; 
		quotient |= 1L << i; 
	} 
} 

return (sign * quotient); 
} 

// اختبار التابع السابق
public static void main(String args[]) 
{ 
int a = 10, b = 3; 
System.out.println(divide(a, b)); 

int a1 = 43, b1 = -8; 
System.out.println(divide(a1, b1)); 


} 
}

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

يبلغ التعقيد الزمني لهذه الخوارزمية المقدار O(Log(a))‎. وتحتاج إلى مساحة ساندة قدرها O(1)‎.

مصادر

صفحة Divide two integers without using multiplication, division and mod operator في توثيق الخوارزميات في موقع GeeksforGeeks.