C++ 解 xn。 (1)利用传统递归法求解该问题。

以下是C++传统递归法求解xn的代码：

#include <iostream>
using namespace std;

double power(double x, int n) {
    if (n == 0) return 1.0; // x^0 = 1
    double half = power(x, n/2);
    if (n % 2 == 0) {
        return half * half;
    }
    else if (n > 0) {
        return half * half * x;
    }
    else {
        return half * half / x;
    }
}

int main() {
    double x = 2.0;
    int n = -3;
    cout << x << "^" << n << " = " << power(x, n) << endl;
    return 0;
}

代码中的power函数用于计算x的n次方。当n为偶数时，利用递归计算x的n/2次方，然后返回其平方；当n为奇数时，则需要额外乘以一个x。需要注意的是，当n为负数时，需要计算x的倒数，即1/x的-n次方。

上述代码输出结果为：

2^-3 = 0.125

即2的-3次方等于1/8=0.125。

相关问题

C++ 请使用 2 种方法，求解 xn。 (1)利用传统递归法求解该问题。 (2)使用二分法思想，结合递归方法求解该问题。

方法一：传统递归法

可以使用递归函数来求解 xn，递归函数的基本思路是将问题不断地拆分成更小的子问题，并将子问题的解合并成原问题的解。

C++代码如下：

#include <iostream>
using namespace std;

int pow(int x, int n) {
    if (n == 0) {
        return 1;
    }
    int half = pow(x, n / 2);
    if (n % 2 == 0) {
        return half * half;
    } else {
        return half * half * x;
    }
}

int main() {
    int x, n;
    cout << "请输入底数x和指数n：" << endl;
    cin >> x >> n;
    int ans = pow(x, n);
    cout << x << "的" << n << "次方是：" << ans << endl;
    return 0;
}

方法二：二分法思想结合递归方法

二分法思想可以帮助我们优化递归过程，减少递归次数，从而提高效率。

具体实现思路是：将指数 n 不断除以 2，如果 n 是偶数，则将底数 x 的幂次方缩小一半，变为 x^(n/2) 的平方；如果 n 是奇数，则将底数 x 的幂次方先缩小一半，变为 x^((n-1)/2) 的平方，然后再乘上一个 x。

C++代码如下：

#include <iostream>
using namespace std;

int pow(int x, int n) {
    if (n == 0) {
        return 1;
    }
    int half = pow(x, n / 2);
    if (n % 2 == 0) {
        return half * half;
    } else {
        return half * half * x;
    }
}

int main() {
    int x, n;
    cout << "请输入底数x和指数n：" << endl;
    cin >> x >> n;
    int ans = pow(x, n);
    cout << x << "的" << n << "次方是：" << ans << endl;
    return 0;
}

这两种方法的时间复杂度都是 O(logn)，效率较高。但是需要注意，当指数 n 很大时，使用递归方式可能会导致栈溢出，需要注意优化递归过程。

用c++的方式请使用 2 种方法，求解 x n。 （1）利用传统递归法求解该问题。 （2）使用二分法思想，结合递归方法求解该问题

1. 利用传统递归法求解 x^n

#include <iostream>

using namespace std;

double pow(double x, int n) {
    if (n == 0) return 1;
    if (n < 0) return 1 / pow(x, -n);
    double half = pow(x, n / 2);
    if (n % 2 == 0) return half * half;
    return half * half * x;
}

int main() {
    double x = 2;
    int n = 10;
    cout << pow(x, n) << endl;
    return 0;
}

2. 使用二分法思想，结合递归方法求解 x^n

#include <iostream>

using namespace std;

double pow(double x, int n) {
    if (n == 0) return 1;
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    double half = pow(x, n / 2);
    if (n % 2 == 0) return half * half;
    return half * half * x;
}

int main() {
    double x = 2;
    int n = 10;
    cout << pow(x, n) << endl;
    return 0;
}

在这里，我们对n的奇偶性进行了判断，如果n为偶数，我们只需要计算一次pow(x, n/2)即可，如果n为奇数，我们需要计算两次pow(x, n/2)，再乘上x。这样就保证了算法的时间复杂度为O(logn)。