عرض مصدر Algorithms/power x y

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

'''مثال:'''

<source lang="text">Input : x = 2, y = 3
Output : 8

Input : x = 7, y = 2
Output : 49</source>
== تنفيذ الخوارزمية ==

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

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

* C++‎:

<source lang="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; 
} </source>
* بايثون:

<source lang="python">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)) </source>
* جافا:

<source lang="java">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)); 
	} 
} </source>
== التعقيد الزمني ==

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

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

<source lang="c++">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; 
} 
</source>
== الأعداد السالبة والعشرية ==

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

* C++‎:

<source lang="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 
</source>
* بايثون:

<source lang="python">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))) </source>
* جافا:

<source lang="java">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)); 
	} 
} </source>
تعطي الشيفرات السابقة المخرجات التالية:

<source lang="text">0.125000</source>
== مصادر ==

* صفحة [https://www.geeksforgeeks.org/write-a-c-program-to-calculate-powxn/ Write a program to calculate pow(x,n)‎] في توثيق الخوارزميات في موقع GeeksforGeeks.

[[تصنيف: الخوارزميات]]
[[تصنيف: فرق تسد]]
[[تصنيف: الخوارزميات الرياضية]]