حساب ناتج رفع عدد إلى قوّة معينة

يمكن استخدام أسلوب فرِّق تسد في كتابة خوارزمية تحسب ناتج رفع عدد معين (ليكن x) إلى قوّة معينة (لتكن y)، مع افتراض أنّ قيمتي x و y صغيرتان نسبيًا ولن تتسببا في حدوث فيضان overflow.

مثال:

Input : x = 2, y = 3
Output : 8

Input : x = 7, y = 2
Output : 49

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

تُقسَّم المسألة في الأمثلة التالية إلى مسائل فرعية ذات حجم y/2 ثم تستدعى المسائل الفرعية استدعاءً تعاوديًا.

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

• C++‎:

#include<iostream> 
using namespace std; 
class gfg 
{ 
	
public: 
int power(int x, unsigned int y) 
{ 
	if (y == 0) 
		return 1; 
	else if (y % 2 == 0) 
		return power(x, y / 2) * power(x, y / 2); 
	else
		return x * power(x, y / 2) * power(x, y / 2); 
} 
}; 

/* اختبار التابع السابق */
int main() 
{ 
	gfg g; 
	int x = 2; 
	unsigned int y = 3; 

	cout << g.power(x, y); 
	return 0; 
}

• بايثون:

def power(x, y): 

	if (y == 0): return 1
	elif (int(y % 2) == 0): 
		return (power(x, int(y / 2)) *
			power(x, int(y / 2))) 
	else: 
		return (x * power(x, int(y / 2)) *
				power(x, int(y / 2))) 

# اختبار الدالة السابقة
x = 2; y = 3
print(power(x, y))

• جافا:

class GFG { 
	static int power(int x, int y) 
	{ 
		if (y == 0) 
			return 1; 
		else if (y % 2 == 0) 
			return power(x, y / 2) * power(x, y / 2); 
		else
			return x * power(x, y / 2) * power(x, y / 2); 
	} 

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

		System.out.printf("%d", power(x, y)); 
	} 
}

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

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

يمكن تحسين التعقيد الزمني للدالة السابقة إلى المقدار O(logn)‎ بحساب المقدار power(x, y/2)‎ مرة واحدة فقط وتخزين الناتج.

int power(int x, unsigned int y) 
{ 
	int temp; 
	if( y == 0) 
		return 1; 
	temp = power(x, y/2); 
	if (y%2 == 0) 
		return temp*temp; 
	else
		return x*temp*temp; 
}

الأعداد السالبة والعشرية

يمكن توسيع عمل الدالة في الأمثلة السابقة لتعمل مع القوى السالبة ‎-y والأعداد العشرية.

• C++‎:

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

float power(float x, int y) 
{ 
	float temp; 
	if(y == 0) 
		return 1; 
	temp = power(x, y / 2); 
	if (y % 2 == 0) 
		return temp * temp; 
	else
	{ 
		if(y > 0) 
			return x * temp * temp; 
		else
			return (temp * temp) / x; 
	} 
} 

// اختبار الدالة السابقة
int main() 
{ 
	float x = 2; 
	int y = -3; 
	cout << power(x, y); 
	return 0; 
} 

// This is code is contributed 
// by rathbhupendra

• بايثون:

def power(x, y): 

	if(y == 0): return 1
	temp = power(x, int(y / 2)) 
	
	if (y % 2 == 0): 
		return temp * temp 
	else: 
		if(y > 0): return x * temp * temp 
		else: return (temp * temp) / x 
	
# اختبار الدالة السابقة
x, y = 2, -3
print('%.6f' %(power(x, y)))

• جافا:

class GFG { 
	
	static float power(float x, int y) 
	{ 
		float temp; 
		if( y == 0) 
			return 1; 
		temp = power(x, y/2); 
		
		if (y%2 == 0) 
			return temp*temp; 
		else
		{ 
			if(y > 0) 
				return x * temp * temp; 
			else
				return (temp * temp) / x; 
		} 
	} 
	
	/* اختبار الدالة السابقة */
	public static void main(String[] args) 
	{ 
		float x = 2; 
		int y = -3; 
		System.out.printf("%f", power(x, y)); 
	} 
}

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

0.125000

مصادر

• صفحة Write a program to calculate pow(x,n)‎ في توثيق الخوارزميات في موقع GeeksforGeeks.