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

好的，我来回答你的问题。

（1）递归法求解 x^n：

递归法求解 x^n 的思路比较简单，即将 x^n 分解成 x * x^(n-1) 的形式，然后递归求解 x^(n-1)，直到 n=0 的时候返回 1。

下面是递归法的代码实现：

int power(int x, int n) {
    if (n == 0) return 1;
    return x * power(x, n-1);
}

但是这种方法的时间复杂度较高，因为要进行 n 次递归调用，时间复杂度为 O(n)。

（2）使用二分法思想求解 x^n：

二分法思想是将问题分解成两个子问题，然后递归求解，最后将子问题的解合并起来。对于 x^n，我们可以将 n 分解成两个子问题，即 n/2 和 n-n/2，然后递归求解 x^(n/2) 和 x^(n-n/2)，最后将两个子问题的解合并起来。

下面是二分法思想的代码实现：

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

这种方法的时间复杂度为 O(logn)，因为每次递归调用都会将 n 减半，所以最多只需要递归 logn 次。

相关问题

用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)。

C++请使用 2 种方法，用户输入数据，求解 x n。 （1）利用传统递归法求解该问题。 （2）使用二分法思想，结合递归方法求解该问题。

(1) 递归法求解 x^n：

#include <iostream>
using namespace std;

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

int main() {
    double x;
    int n;
    cout << "请输入一个数 x 和一个整数 n，计算 x 的 n 次方：" << endl;
    cin >> x >> n;
    cout << x << " 的 " << n << " 次方是：" << power(x, n) << endl;
    return 0;
}

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

#include <iostream>
using namespace std;

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

int main() {
    double x;
    int n;
    cout << "请输入一个数 x 和一个整数 n，计算 x 的 n 次方：" << endl;
    cin >> x >> n;
    double ans = power(x, abs(n));
    if (n < 0) ans = 1 / ans;
    cout << x << " 的 " << n << " 次方是：" << ans << endl;
    return 0;
}

两种方法的时间复杂度都是 O(log n)。