给定两个整数x和n，编写一个函数来计算x N .我们可以假设x和n很小，不会发生溢出。
null
例如：
Input : x = 2, n = 3 Output : 8 Input : x = 7, n = 2 Output : 49
下面的解决方案将问题划分为大小为y/2的子问题，并递归调用这些子问题。
C++
// C++ program to calculate pow(x,n) #include<iostream> using namespace std; class gfg { /* Function to calculate x raised to the power y */ 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); } }; /* Driver code */ int main() { gfg g; int x = 2; unsigned int y = 3; cout << g.power(x, y); return 0; } // This code is contributed by SoM15242 |
C
#include<stdio.h> /* Function to calculate x raised to the power y */ 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); } /* Program to test function power */ int main() { int x = 2; unsigned int y = 3; printf ( "%d" , power(x, y)); return 0; } |
JAVA
class GFG { /* Function to calculate x raised to the power y */ 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 ); } /* Program to test function power */ public static void main(String[] args) { int x = 2 ; int y = 3 ; System.out.printf( "%d" , power(x, y)); } } // This code is contributed by Smitha Dinesh Semwal |
蟒蛇3
# Python3 program to calculate pow(x,n) # Function to calculate x # raised to the power y 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 ))) # Driver Code x = 2 ; y = 3 print (power(x, y)) # This code is contributed by Smitha Dinesh Semwal. |
C#
using System; public class GFG { // Function to calculate x raised to the power y 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); } // Program to test function power public static void Main() { int x = 2; int y = 3; Console.Write(power(x, y)); } } // This code is contributed by shiv_bhakt. |
PHP
<?php // Function to calculate x // raised to the power y function power( $x , $y ) { if ( $y == 0) return 1; else if ( $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); } // Driver Code $x = 2; $y = 3; echo power( $x , $y ); // This code is contributed by ajit ?> |
Javascript
<script> // Javascript program to calculate pow(x,n) // Function to calculate x // raised to the power y function power(x, y) { if (y == 0) return 1; else if (y % 2 == 0) return power(x, parseInt(y / 2, 10)) * power(x, parseInt(y / 2, 10)); else return x * power(x, parseInt(y / 2, 10)) * power(x, parseInt(y / 2, 10)); } // Driver code let x = 2; let y = 3; document.write(power(x, y)); // This code is contributed by mukesh07 </script> |
输出：
8
时间复杂性： O（n） 空间复杂性： O（1）
算法范例： 分而治之。 通过只计算一次功率（x，y/2）并存储它，可以将上述函数优化为O（logn）。
C++
/* Function to calculate x raised to the power y in O(logn)*/ 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; } // This code is contributed by Shubhamsingh10 |
C
/* Function to calculate x raised to the power y in O(logn)*/ 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; } |
JAVA
/* Function to calculate x raised to the power y in O(logn)*/ static int power( int x, 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; } // This code is contributed by divyeshrabadiya07. |
蟒蛇3
# Function to calculate x raised to the power y in O(logn) def power(x,y): temp = 0 if ( y = = 0 ): return 1 temp = power(x, int (y / 2 )) if (y % 2 = = 0 ) return temp * temp; else return x * temp * temp; # This code is contributed by avanitrachhadiya2155 |
C#
/* Function to calculate x raised to the power y in O(logn)*/ static int power( int x, 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; } // This code is contributed by divyesh072019. |
Javascript
<script> /* Function to calculate x raised to the power y in O(logn)*/ function power(x , y) { var temp; if ( y == 0) return 1; temp = power(x, y / 2); if (y % 2 == 0) return temp*temp; else return x*temp*temp; } // This code is contributed by todaysgaurav </script> |
优化解决方案的时间复杂度： O（logn）
辅助空间： O（1）
让我们将pow函数扩展为负y和浮动x。
C++
/* Extended version of power function that can work for float x and negative y*/ #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; } } // Driver Code int main() { float x = 2; int y = -3; cout << power(x, y); return 0; } // This is code is contributed // by rathbhupendra |
C
/* Extended version of power function that can work for float x and negative y*/ #include<stdio.h> 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; } } /* Program to test function power */ int main() { float x = 2; int y = -3; printf ( "%f" , power(x, y)); return 0; } |
JAVA
/* Java code for extended version of power function that can work for float x and negative 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; } } /* Program to test function power */ public static void main(String[] args) { float x = 2 ; int y = - 3 ; System.out.printf( "%f" , power(x, y)); } } // This code is contributed by Smitha Dinesh Semwal. |
蟒蛇3
# Python3 code for extended version # of power function that can work # for float x and negative y 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 # Driver Code x, y = 2 , - 3 print ( '%.6f' % (power(x, y))) # This code is contributed by Smitha Dinesh Semwal. |
C#
// C# code for extended version of power function // that can work for float x and negative y using System; public 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; } } // Program to test function power public static void Main() { float x = 2; int y = -3; Console.Write(power(x, y)); } } // This code is contributed by shiv_bhakt. |
PHP
<?php // Extended version of power // function that can work // for float x and negative y function power( $x , $y ) { $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 ; } } // Driver Code $x = 2; $y = -3; echo power( $x , $y ); // This code is contributed by ajit ?> |
Javascript
<script> // Javascript code for extended // version of power function that // can work for var x and negative y function power(x, y) { var temp; if (y == 0) return 1; temp = power(x, parseInt(y / 2)); if (y % 2 == 0) return temp * temp; else { if (y > 0) return x * temp * temp; else return (temp * temp) / x; } } // Driver code var x = 2; var y = -3; document.write( power(x, y).toFixed(6)); // This code is contributed by aashish1995 </script> |
输出：
0.125000
时间复杂性： O（log | n |）
辅助空间： O（1）
使用递归：
这种方法几乎类似于迭代解法
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; int power( int x, int y) { // If x^0 return 1 if (y == 0) return 1; // If we need to find of 0^y if (x == 0) return 0; // For all other cases return x * power(x, y - 1); } // Driver Code int main() { int x = 2; int y = 3; cout << (power(x, y)); } // This code is contributed by ukasp. |
JAVA
// Java program for the above approach import java.io.*; class GFG { public static int power( int x, int y) { // If x^0 return 1 if (y == 0 ) return 1 ; // If we need to find of 0^y if (x == 0 ) return 0 ; // For all other cases return x * power(x, y - 1 ); } // Driver Code public static void main(String[] args) { int x = 2 ; int y = 3 ; System.out.println(power(x, y)); } } |
蟒蛇3
# Python3 program for the above approach def power(x, y): # If x^0 return 1 if (y = = 0 ): return 1 # If we need to find of 0^y if (x = = 0 ): return 0 # For all other cases return x * power(x, y - 1 ) # Driver Code x = 2 y = 3 print (power(x, y)) # This code is contributed by shivani. |
C#
// C# program for the above approach using System; class GFG{ public static int power( int x, int y) { // If x^0 return 1 if (y == 0) return 1; // If we need to find of 0^y if (x == 0) return 0; // For all other cases return x * power(x, y - 1); } // Driver Code public static void Main(String[] args) { int x = 2; int y = 3; Console.WriteLine(power(x, y)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // javascript program for the above approach function power(x , y) { // If x^0 return 1 if (y == 0) return 1; // If we need to find of 0^y if (x == 0) return 0; // For all other cases return x * power(x, y - 1); } // Driver Code var x = 2; var y = 3; document.write(power(x, y)); // This code is contributed by Rajput-Ji </script> |
输出：
8
时间复杂性： O（n）
辅助空间： O（1）
使用数学。java的pow（）函数：
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; int power( int x, int y) { // return type of pow() // function is double return ( int ) pow (x, y); } // Driver Code int main() { int x = 2; int y = 3; cout << (power(x, y)); } // This code is contributed by hemantraj712. |
JAVA
// Java program for the above approach import java.io.*; class GFG { public static int power( int x, int y) { // Math.pow() is a function that // return floating number return ( int )Math.pow(x, y); } // Driver Code public static void main(String[] args) { int x = 2 ; int y = 3 ; System.out.println(power(x, y)); } } |
蟒蛇3
# Python3 program for the above approach def power(x, y): # Return type of pow() # function is double return pow (x, y) # Driver Code x = 2 y = 3 print (power(x, y)) # This code is contributed by susmitakundugoaldanga |
C#
// C# program for the above approach using System; public class GFG { public static int power( int x, int y) { // Math.pow() is a function that // return floating number return ( int )Math.Pow(x, y); } // Driver code static public void Main() { int x = 2; int y = 3; Console.WriteLine(power(x, y)); } } |
Javascript
<script> // Javascript program for the above approach function power( x, y) { // Math.pow() is a function that // return floating number return parseInt(Math.pow(x, y)); } // Driver Code let x = 2; let y = 3; document.write(power(x, y)); // This code is contributed by sravan kumar </script> |
输出：
8
时间复杂性： O（1）
辅助空间： O（1）
非递归方法： 对于新手来说，这是一种非常有效的方法，他们觉得很难理解迭代递归调用。这种方法也需要 T（n）=O（对数（n）） 复杂性
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; int power( int x, int y) { int result = 1; while (y > 0) { if (y % 2 == 0) // y is even { x = x * x; y = y / 2; } else // y isn't even { result = result * x; y = y - 1; } } return result; } // Driver Code int main() { int x = 2; int y = 3; cout << (power(x, y)); return 0; } // This code is contributed by Madhav Mohan |
JAVA
// Java program for above approach class GFG{ static int power( int x, int y) { int result = 1 ; while (y > 0 ) { // y is even if (y % 2 == 0 ) { x = x * x; y = y / 2 ; } // y isn't even else { result = result * x; y = y - 1 ; } } return result; } // Driver Code public static void main(String[] args) { int x = 2 ; int y = 3 ; System.out.println(power(x, y)); } } // This code is contributed by hritikrommie |
蟒蛇3
# Python program for the above approach def power( x, y): result = 1 while (y > 0 ): if (y % 2 = = 0 ): # y is even x = x * x y = y / 2 else : # y isn't even result = result * x y = y - 1 return result # Driver Code x = 2 y = 3 print ((power(x, y))) # This code is contributed by shivanisinghss2110 |
C#
// C# program for above approach using System; class GFG{ static int power( int x, int y) { int result = 1; while (y > 0) { // y is even if (y % 2 == 0) { x = x * x; y = y / 2; } // y isn't even else { result = result * x; y = y - 1; } } return result; } // Driver Code public static void Main(String[] args) { int x = 2; int y = 3; Console.Write(power(x, y)); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // Javascript program for the above approach function power(x,y) { let result = 1; while (y > 0) { if (y % 2 == 0) // y is even { x = x * x; y = Math.floor(y / 2); } else // y isn't even { result = result * x; y = y - 1; } } return result; } // Driver Code let x = 2; let y = 3; document.write(power(x, y)) // This code is contributed by rag2127 </script> |
输出
8
时间复杂性： O（原木） 2. y）
辅助空间： O（1）
为pow（x，y）编写一个迭代O（logy）函数 模幂运算（模算术中的幂运算） 如果你喜欢Geeksforgek，并且想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
