计算n个数的全排列,输入n,输出1,2,3,...n的全排列,利用分治法实现要求简便并用c语言实现
时间: 2023-06-15 08:07:45 浏览: 58
以下是使用分治算法实现全排列的C语言代码:
```c
#include <stdio.h>
// 交换两个数的值
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 递归产生全排列
void permute(int arr[], int start, int end) {
if (start == end) {
// 已经到达末尾,输出排列
for (int i = 0; i <= end; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return;
}
for (int i = start; i <= end; i++) {
// 交换第一个元素和后面的元素
swap(&arr[start], &arr[i]);
// 递归产生子排列
permute(arr, start + 1, end);
// 恢复原来的顺序
swap(&arr[start], &arr[i]);
}
}
int main() {
int n;
printf("请输入n:");
scanf("%d", &n);
int arr[n];
for (int i = 0; i < n; i++) {
arr[i] = i + 1;
}
permute(arr, 0, n - 1);
return 0;
}
```
该算法的时间复杂度为O(n*n!),因为共产生了n!个排列,每个排列需要O(n)的时间复杂度来输出。