C++程序,用户输入数据,求解 x n,使用二分法思想,结合递归方法求解该问题。
时间: 2023-12-21 15:03:08 浏览: 89
以下是使用递归方法和二分法思想求解 x^n 的 C++ 程序:
```cpp
#include <iostream>
using namespace std;
double power(double x, int n) {
if (n == 0) return 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;
int n;
cout << "请输入底数 x:";
cin >> x;
cout << "请输入指数 n:";
cin >> n;
double result = power(x, n);
cout << x << " 的 " << n << " 次方等于 " << result << endl;
return 0;
}
```
程序中定义了一个 `power` 函数,用于计算 x^n 的值。该函数使用了递归方法和二分法思想,将指数 n 不断缩小为 n/2,直到 n 缩小到 0。在每次递归过程中,将原问题分解为两个子问题,分别计算 x^(n/2) 的值,并根据 n 的奇偶性将子问题的结果相乘或相乘再乘以底数 x,最终得到原问题的解。时间复杂度为 O(log n)。
相关问题
C++请使用 2 种方法,用户输入数据,求解 x n。 (1)利用传统递归法求解该问题。 (2)使用二分法思想,结合递归方法求解该问题。
(1) 递归法求解 x^n:
```cpp
#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:
```cpp
#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)。
用c++的方式请使用 2 种方法,求解 x n。并且要求用户自己输入数据 (1)利用传统递归法求解该问题。 (2)使用二分法思想,结合递归方法求解该问题
1 利用传统递归法求解该问题
代码如下:
```c++
#include <iostream>
using namespace std;
double power(double x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
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:";
cin >> x;
cout << "请输入指数n:";
cin >> n;
cout << x << "的" << n << "次方为:" << power(x, n) << endl;
return 0;
}
```
2. 使用二分法思想,结合递归方法求解该问题
代码如下:
```c++
#include <iostream>
using namespace std;
double myPow(double x, int n) {
if (n == 0) return 1;
double half = myPow(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;
int n;
cout << "请输入底数x:";
cin >> x;
cout << "请输入指数n:";
cin >> n;
cout << x << "的" << n << "次方为:" << myPow(x, n) << endl;
return 0;
}
```
阅读全文