Algorithms/square root

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

مثال:

Input: x = 4
Output: 2

Input: x = 11
Output: 3

أسلوب القوة الغاشمة

أبسط طريقة لإيجاد الجذر التربيعي للعدد المعطى هي تجربة جميع الأعداد بدءًا من 1؛ ولكلّ عدد في هذا النطاق (ليكن i) يجري التحقق من أنّ ناتج العملية i*i أصغر من العدد المعطى x، ثُم تُزاد قيمة i. تتوقف الخوارزمية عن العمل عندما تصبح قيمة i*i أكبر من x أو مساوية له.

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

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

• C++‎:

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

int floorSqrt(int x) 
{ 
	// الحالتان الأساسيتان 
	if (x == 0 || x == 1) 
	return x; 

	// بدءًا من العدد 1 نجرّب جميع الأعداد
	// i*i إلى أن تصبح القيمة 
	// أكبر من العدد المعطى أو مساوية له
	int i = 1, result = 1; 
	while (result <= x) 
	{ 
	i++; 
	result = i * i; 
	} 
	return i - 1; 
} 

// اختبار الدالة السابقة 
int main() 
{ 
	int x = 11; 
	cout << floorSqrt(x) << endl; 
	return 0; 
}

• بايثون:

def floorSqrt(x): 

	# الحالتان الأساسيتان 
	if (x == 0 or x == 1): 
		return x 

	# بدءًا من العدد 1 نجرّب جميع الأعداد 
	# i*i إلى أن تصبح القيمة
	# أكبر من العدد المعطى أو مساوية له
	
	i = 1; result = 1
	while (result <= x): 
	
		i += 1
		result = i * i 
	
	return i - 1

# اختبار الدالة السابقة
x = 11
print(floorSqrt(x))

• جافا:

class GFG { 
	
	static int floorSqrt(int x) 
	{ 
		// الحالتان الأساسيتان  
		if (x == 0 || x == 1) 
			return x; 

		// بدءًا من العدد 1 نجرّب جميع الأعداد
		// i*i إلى أن تصبح القيمة 
		// أكبر من العدد المعطى أو مساوية له
		int i = 1, result = 1; 
		
		while (result <= x) { 
			i++; 
			result = i * i; 
		} 
		return i - 1; 
	} 

	// اختبار التابع السابق
	public static void main(String[] args) 
	{ 
		int x = 11; 
		System.out.print(floorSqrt(x)); 
	} 
}

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

3

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

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

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

يعتقد أن الطريقة البابلية Babylonian method هي أوّل خوارزمية وضعت لإيجاد الناتج التقريبي للجذر التربيعي لعدد معين. وتسّمى هذه الطريقة كذلك بطريقة هيرون Heron's method نسبة إلى الرياضي الإغريقي هيرون السكندري الذي وضع أول وصف دقيق لهذه الطريقة في القرن الأول الميلادي في كتابه Metrica.

تتبع هذه الخوارزمية الخطوات التالية:

1. البدء بقيمة معيّنة موجبة (لتكن x)، ويستحسن أن تكون القيمة قريبة من الجذر التربيعي.
2. تهيئة y = 1.
3. تنفيذ الخطوات التالية إلى حين الوصول إلى النتيجة المقرّبة المطلوبة:
   1. الحصول على التقريب التالي للجذر وذلك بحساب معدل القيمتين x و y
   2. تعيين قيمة y لتصبح n/x.

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

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

• C++‎:

#include <iostream> 
using namespace std; 
float squareRoot(float n) 
	{ 
		/* تستخدم هذه الشيفرة العدد المعطى كقيمة التقريب الأولية
		ولكن يمكن تحسين ذلك بالتأكيد */
		float x = n; 
		float y = 1; 
		float e = 0.000001; /* تحديد نسبة الخطأ */
		while (x - y > e) { 
			x = (x + y) / 2; 
			y = n / x; 
		} 
		return x; 
}

/* اختبار الدالة السابقة */
int main() 
{ 
	int n = 50; 
	cout << "Square root of " << n << " is " << squareRoot(n); 
	getchar(); 
}

• بايثون:

def squareRoot(n): 

	# تستخدم هذه الشيفرة العدد المعطى كقيمة التقريب الأولية
	# ولكن يمكن تحسين ذلك بالتأكيد
		x = n 
		y = 1
		
		# تحديد نسبة الخطأ 
		e = 0.000001
		while(x - y > e): 
	
			x = (x + y)/2
			y = n / x 
	
		return x 

# اختبار الدالة السابقة
n = 50

print("Square root of", n, "is", 
			round(squareRoot(n), 6))

• جافا:

class GFG { 

	static float squareRoot(float n) 
	{ 

		/*تستخدم هذه الشيفرة العدد المعطى كقيمة التقريب الأولية 
		ولكن يمكن تحسين ذلك بالتأكيد */
		float x = n; 
		float y = 1; 

		// تحديد نسبة الخطأ 
		double e = 0.000001; 
		while (x - y > e) { 
			x = (x + y) / 2; 
			y = n / x; 
		} 
		return x; 
	} 

	/* اختبار التابع السابق */
	public static void main(String[] args) 
	{ 
		int n = 50; 

		System.out.printf("Square root of "
						+ n + " is " + squareRoot(n)); 
	} 
}

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

Square root of 50 is 7.071068

طريقة البحث الثنائي

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

1. البدء بالقيمتين start = 0 و end = x.
2. تنفيذ العمليات التالية ما دامت قيمة x أصغر من قيمة end أو مساوية لها.
   1. حساب متوسط القيمتين start و end وهو mid = (start + end) / 2.
   2. مقارنة mid*mid مع x.
   3. إن كانت قيمة x مساوية لقيمة mid*mid، تُعاد قيمة mid.
   4. إن كانت قيمة x أكبر من قيمة mid*mid، تُنفذ عملية بحث ثنائي بين القيمتين mid+1 و end.
   5. إن كانت قيمة x أصغر من قيمة mid*mid، تُنفذ عملية بحث ثنائي بين القيمتين start و mid.

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

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

• C++‎:

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

int floorSqrt(int x) 
{	 
	// الحالتان الأساسيتان 
	if (x == 0 || x == 1) 
	return x; 

	// عملية البحث الثنائي 
	int start = 1, end = x, ans; 
	while (start <= end) 
	{		 
		int mid = (start + end) / 2; 

		// إن كان العدد المعطى مربّعًا كاملًا
		if (mid*mid == x) 
			return mid; 

		// لما كان المطلوب إيجاد ناتج تقريبي
		// mid*mid تحدّث الإجابة عندما يكون ناتج التعبير 
		// أصغر من العدد المعطى لنقترب أكثر من الجذر التربيعي
		if (mid*mid < x) 
		{ 
			start = mid + 1; 
			ans = mid; 
		} 
		// mid*mid إن كان ناتج التعبير 
		// أكبر من العدد المعطى
		else 
			end = mid-1;		 
	} 
	return ans; 
} 

// اختبار الدالة السابقة
int main() 
{	 
	int x = 11; 
	cout << floorSqrt(x) << endl; 
	return 0; 
}

• بايثون:

def floorSqrt(x) : 

	# الحالتان الأساسيتان
	if (x == 0 or x == 1) : 
		return x 

	# عملية البحث الثنائي
	start = 1
	end = x 
	while (start <= end) : 
		mid = (start + end) // 2
		
		# إن كان العدد المعطى مربّعًا كاملًا 
		if (mid*mid == x) : 
			return mid 
			
		# لما كان المطلوب إيجاد ناتج تقريبي 
		# mid*mid تحدّث الإجابة عندما يكون ناتج التعبير 
		# أصغر من العدد المعطى لنقترب أكثر من الجذر التربيعي 
		if (mid * mid < x) : 
			start = mid + 1
			ans = mid 
			
		else : 
			
			# mid*mid إن كان ناتج التعبير  
			# أكبر من العدد المعطى
			end = mid-1
			
	return ans 

# اختبار الدالة السابقة	 
x = 11
print(floorSqrt(x))

• جافا:

public class Test 
{ 
	public static int floorSqrt(int x) 
	{ 
		// الحالتان الأساسيتان
		if (x == 0 || x == 1) 
			return x; 

		// عملية البحث الثنائي 
		int start = 1, end = x, ans=0; 
		while (start <= end) 
		{ 
			int mid = (start + end) / 2; 

			// إن كان العدد المعطى مربّعًا كاملًا 
			if (mid*mid == x) 
				return mid; 

			// لما كان المطلوب إيجاد ناتج تقريبي
			// mid*mid تحدّث الإجابة عندما يكون ناتج التعبير 
			// أصغر من العدد المعطى لنقترب أكثر من الجذر التربيعي
			if (mid*mid < x) 
			{ 
				start = mid + 1; 
				ans = mid; 
			} 
					// mid*mid إن كان ناتج التعبير 
		// أكبر من العدد المعطى
			else  
				end = mid-1; 
		} 
		return ans; 
	} 

	// اختبار التابع السابق
	public static void main(String args[]) 
	{ 
		int x = 11; 
		System.out.println(floorSqrt(x)); 
	} 
}

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

3

مصادر

• صفحة Square root of an integer في توثيق الخوارزميات في موقع GeeksforGeeks.

• صفحة Babylonian method for square root في توثيق الخوارزميات في موقع GeeksforGeeks.