用c语言设计一个分治算法求解x的n次幂
时间: 2023-05-22 15:01:02 浏览: 69
以下是一个用C语言设计的分治算法求解x的n次幂的代码示例:
```c
#include <stdio.h>
double power(double x, int n) {
if (n == 0) {
return 1.0;
}
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 = 10;
double result = power(x, n);
printf("%lf\n", result);
return 0;
}
```
这个算法的时间复杂度为O(log n),因为它将问题分成了规模为n/2的两个子问题,并且每次递归都将问题规模减半。
相关问题
用C语言写一个分治算法
以下是一个简单的分治算法代码示例,用于在数组中查找一个元素:
#include <stdio.h>
int binary_search(int arr[], int low, int high, int x) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] > x) {
return binary_search(arr, low, mid - 1, x);
} else {
return binary_search(arr, mid + 1, high, x);
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 6;
int result = binary_search(arr, 0, n - 1, x);
if (result == -1) {
printf("Element not found.");
} else {
printf("Element found at index %d.", result);
}
return 0;
}
c语言求x的n次幂(非递归求解)
可以使用循环来实现非递归求解x的n次幂,具体实现如下:
```c
#include <stdio.h>
int main() {
int x, n, result = 1;
printf("请输入x和n:");
scanf("%d%d", &x, &n);
for (int i = 0; i < n; i++) {
result *= x;
}
printf("%d的%d次幂为%d\n", x, n, result);
return 0;
}
```
在这段代码中,我们首先输入了底数x和指数n,然后使用for循环计算x的n次幂,最后输出结果。