我的家庭作业有问题，需要帮助！
问题1:
完成下面的Java方法，使raiseToPower(x，n(将数字x提高到整数n的幂(即计算值xn(。请记住，x-n=1/xn，并且x0＝1。
您应该以尽可能少的步骤数(即，在O(logn(时间内(完成此操作。
给出一个非递归(迭代(的解决方案：
这是我的解决方案：
public static double raiseToPower (double x, int n) {
double res=1;
boolean neg=false;
if(n<0)
{
neg=true;
}
if(n>0)
for (int i=0;i<n;i++) {
res = res * x;
}
if(neg==true) {
n=n*-1;
for (int i=0;i<n;i++) {
res = res * x;
}
res=1/res;
}
return res;
}
但这是不正确的，因为不是效率
这是我的错误，例如：52.49的9次方在9个步骤中解决，但本可以在4个步骤中完成89.89的75次方在75个步骤中解决，但本可以在7个步骤中完成78.57的63次方在63个步骤中解决，但本可以在6个步骤中完成70.17到44的幂在44个步骤中解决，但它本可以在6个步骤中完成
注意：不能在方法java.lang.MathPow 中使用
问题2:
我需要编写与问题1完全相同的代码，但在递归中
这是我的问题：给出一个递归解决方案：
这是我的代码：
public static double raiseToPower (double x, int n) {
ouble dev=0.0;
if (n == 0) {
return 1;
} else {
if (n < 0) {
double count= raiseToPower (x, n+1);
dev=count*x;
return 1 / raiseToPower (x, -n);
}
if (n > 0) {
double count= raiseToPower (x, n-1);
dev=count*x;
}
}
return dev;
}
此代码是正确的，但不是有效的。
这是我的错误，例如：
53.31的44次方在44个步骤中解决，但本可以在6个步骤中完成6.90的74次方在74个步骤中解决，但本可以在7个步骤中完成80.76的76次方用76个步骤解决，但本可以用7个步骤完成51.44的86次方在86个步骤中解决，但本可以在7个步骤中完成76.26的50次方在50个步骤中解决，但本可以在6个步骤中完成63.53的93次方在93个步骤中解决，但它本可以在7个步骤中完成
注意：不得在方法java.lang.MathPow中使用
感谢大家的帮助和解决这两个问题！！！
您可以通过将n分解为2的幂来计算O(logN(x^n，如下所示：
9=1+8
15=1+2+4+8
因此，x^9=(x^1(*(x^8(。
为了将n分解为2的幂，可以使用逐位运算符。像这样：n&pow2意味着你在N和pow2之间进行"与"运算，这意味着如果N有一个位1，pow2也有那个位1，结果将是非零的。假设pow2必须有一个比特1(它是2的幂(，你基本上可以检查n的每一个比特。所以你把n分解为2的幂，当你循环2的幂时，你可以简单地保持一个powx，这意味着x^(pow2(，然后当你发现n确实是由2的幂组成时，把它乘以res。
因此，我们可以为第一个解决方案制作此代码：
public static double raiseToPower (double x, int n) {
double res=1;
double powx=x;
int pow2=1;
boolean neg=false;
if(n<0)
{
neg=true;
n=n*-1;
}
while(n!=0) {
if((n&pow2)!=0)
{
res=res*powx;
n=n-pow2;
}
powx=powx*powx;
pow2=pow2*2;
}
if(neg==true)
res=1/res;
return res;
}
以下是更多关于位运算符的文章：https://www.tutorialspoint.com/java/java_basic_operators.htm
类似地，您可以修改递归代码以在O(logN(中获得它。
下面是递归代码：
public static double raiseToPower(double x, int n)
{
boolean neg= false;
double res=1;
if(n<0)
{
neg=true;
n=-n;
}
if (n == 0) return 1;
if (n % 2 == 0)
{
res= raiseToPower(x, n / 2);
res=res*res;
}
else
{
res= x * raiseToPower(x, n - 1);
}
if(!neg)
return res;
return 1/res;
}
public class ExponentialCalculator {
public static void main(String[] args) {
double x = 2;
int n = -4;
System.out.println(raiseToPower(x, n));
}
//Divide and Conquer method
public static double raiseToPower (double x, int n) {
if(n==0) {
return 1;
}
double temp = raiseToPower(x, n/2) * raiseToPower(x, n/2);
if(n%2==0) {
return n > 0 ? temp: 1/temp;
}
else {
return n > 0 ? x * temp: 1/(x * temp);
}
}
}
结果0.0625
复杂度对数(n(