Algorithms/cubic root

المطلوب في هذه المسألة هو إيجاد الجذر التكعيبي للعدد المعطى (ليكن n).

مثال:

Input:  n = 3
Output: Cubic Root is 1.442250

Input: n = 8
Output: Cubic Root is 2.000000

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

يمكن استخدام عملية البحث الثنائي لإيجاد الجذر التكعيبي للعدد المعطى.

تعرّف الخوارزمية في البداية قيمة للخطأ (لتكن e) وستفترض طريقة التنفيذ أنّها تساوي 0.0000001، ثم تتبع الخوارزمية الخطوات التالية لإيجاد الجذر التكعيبي للعدد n:

1. البدء بالقيمتين start = 0 و end = n.
2. حساب متوسّط القيمتين السابقتين mid = (start + end)/2.
3. التحقّق من أنّ القيمة ‎(n - mid*mid*mid) < e‎. إن تحقّق الشرط فإنّ المتوسّط المحسوب في الخطوة السابقة هو الجذر التكعيبي للعدد n.
4. إن كانت القيمة ‎(mid*mid*mid) > n‎ تُعيّن قيمة المتوسّط كقيمة للنهاية end = mid.
5. إن كانت القيمة ‎(mid*mid*mid) < n‎ تُعيّن قيمة المتوسّط كقيمة للبداية start = mid.

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

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

• C++‎:

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

// تعيد الدالة القيمة المطلقة لناتج التعبير
// n-mid*mid*mid
double diff(double n,double mid) 
{ 
	if (n > (mid*mid*mid)) 
		return (n-(mid*mid*mid)); 
	else
		return ((mid*mid*mid) - n); 
} 

// تعيد الدالة الجذر التكعيبي للعدد المعطى
double cubicRoot(double n) 
{ 
	// تعيين قيمتي البداية والنهاية للبحث الثنائي
	double start = 0, end = n; 

	// تعيين نسبة الخطأ
	double e = 0.0000001; 

	while (true) 
	{ 
		double mid = (start + end)/2; 
		double error = diff(n, mid); 

		// إن كان الخطأ أقلّ من نسبة الخطأ المعينة
		// يكون المتوسّط هو الجذر التكعيبي للعدد المعطى
		if (error <= e) 
			return mid; 

		// mid*mid*mid إن كان ناتج التعبير 
		// أكبر من العدد المعطى نجعل قيمة المتوسّط قيمة النهاية
		if ((mid*mid*mid) > n) 
			end = mid; 

		// mid*mid*mid إن كان ناتج التعبير 
		// أصغر من العدد المعطى نجعل قيمة المتوسّط قيمة البداية 
		else
			start = mid; 
	} 
} 

// اختبار الدالتين السابقتين
int main() 
{ 
	double n = 3; 
	printf("Cubic root of %lf is %lf\n", 
		n, cubicRoot(n)); 
	return 0; 
}

• بايثون:

# تعيد الدالة القيمة المطلقة لناتج التعبير 
# n-mid*mid*mid 
def diff(n, mid) : 
	if (n > (mid * mid * mid)) : 
		return (n - (mid * mid * mid)) 
	else : 
		return ((mid * mid * mid) - n) 
		
# تعيد الدالة الجذر التكعيبي للعدد المعطى 
def cubicRoot(n) : 
	
	# تعيين قيمتي البداية والنهاية للبحث الثنائي 
	start = 0
	end = n 
	
	# تعيين نسبة الخطأ 
	e = 0.0000001
	while (True) : 
		
		mid = (start + end) / 2
		error = diff(n, mid) 

		# إن كان الخطأ أقلّ من نسبة الخطأ المعينة
		# يكون المتوسّط هو الجذر التكعيبي للعدد المعطى 
		if (error <= e) : 
			return mid 
			
		# mid*mid*mid إن كان ناتج التعبير
		# أكبر من العدد المعطى نجعل قيمة المتوسّط قيمة النهاية
		if ((mid * mid * mid) > n) : 
			end = mid 
			
		# mid*mid*mid إن كان ناتج التعبير 
		# أصغر من العدد المعطى نجعل قيمة المتوسّط قيمة البداية 
		else : 
			start = mid 
			
# اختبار الدالتين السابقتين
n = 3
print("Cubic root of", n, "is", 
	round(cubicRoot(n),6))

• جافا:

import java.io.*; 

class GFG 
{ 
	// يعيد التابع القيمة المطلقة لناتج التعبير
	// n-mid*mid*mid 
	static double diff(double n,double mid) 
	{ 
		if (n > (mid*mid*mid)) 
			return (n-(mid*mid*mid)); 
		else
			return ((mid*mid*mid) - n); 
	} 
	
	// يعيد التابع الجذر التكعيبي للعدد المعطى
	static double cubicRoot(double n) 
	{ 
		// تعيين قيمتي البداية والنهاية للبحث الثنائي 
		double start = 0, end = n; 

		// تعيين نسبة الخطأ 
		double e = 0.0000001; 

		while (true) 
		{ 
			double mid = (start + end)/2; 
			double error = diff(n, mid); 

			// إن كان الخطأ أقلّ من نسبة الخطأ المعينة
			// يكون المتوسّط هو الجذر التكعيبي للعدد المعطى
			if (error <= e) 
				return mid; 

			// mid*mid*mid إن كان ناتج التعبير
			// أكبر من العدد المعطى نجعل قيمة المتوسّط قيمة النهاية 
			if ((mid*mid*mid) > n) 
				end = mid; 

			// mid*mid*mid إن كان ناتج التعبير
			// أصغر من العدد المعطى نجعل قيمة المتوسّط قيمة البداية 
			else
				start = mid; 
		} 
	} 
	
	// اختبار التابعين السابقين 
	public static void main (String[] args) 
	{ 
		double n = 3; 
		System.out.println("Cube root of "+n+" is "+cubicRoot(n)); 
	} 
}

مصادر

• صفحة Find cubic root of a number في توثيق الخوارزميات في موقع GeeksforGeeks.