Java 方法像 MathPow 的解决方案迭代和递归效率 - 家庭作业
Java method like MathPow with a solution iterative and recursive in efficiency-Homework
我的作业有问题,我需要帮助!
问题一:
完成下面的 Java 方法,使 raiseToPower(x,n) 将数字 x 提高到 n 的整数次方(即计算值 xn )。请记住 x-n = 1/xn,
并且 x0 = 1.
您应该以尽可能少的步骤执行此操作(即,在 O(log n) 时间内)。
给出一个非递归(迭代)的解决方案:
这是我的解决方案:
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
问题二:
我需要编写与问题 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 之间进行 "AND" 操作,这意味着如果 n 有一个位 1 并且 pow2 也有那个位 1,那么结果将是非零的。鉴于 pow2 必须有一位 1(它是 2 的幂),您基本上可以检查 n 的每一位。所以你正在分解 n 的 2 的幂,你可以简单地保持一个 powx 表示 x^(pow2) 当你循环遍历 2 的幂时,然后只要你发现 n 确实由以下组成,就将它乘以 res 2 的幂。
所以我们可以为第一个解决方案编写此代码:
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)
我的作业有问题,我需要帮助!
问题一:
完成下面的 Java 方法,使 raiseToPower(x,n) 将数字 x 提高到 n 的整数次方(即计算值 xn )。请记住 x-n = 1/xn, 并且 x0 = 1.
您应该以尽可能少的步骤执行此操作(即,在 O(log n) 时间内)。
给出一个非递归(迭代)的解决方案:
这是我的解决方案:
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
问题二:
我需要编写与问题 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 之间进行 "AND" 操作,这意味着如果 n 有一个位 1 并且 pow2 也有那个位 1,那么结果将是非零的。鉴于 pow2 必须有一位 1(它是 2 的幂),您基本上可以检查 n 的每一位。所以你正在分解 n 的 2 的幂,你可以简单地保持一个 powx 表示 x^(pow2) 当你循环遍历 2 的幂时,然后只要你发现 n 确实由以下组成,就将它乘以 res 2 的幂。
所以我们可以为第一个解决方案编写此代码:
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)