设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列用c语言
时间: 2024-10-12 09:12:21 浏览: 14
设计一个递归算法用于生成n个元素的全排列,我们可以采用经典的“回溯”思想。这里是一个简单的C语言实现:
```c
#include <stdio.h>
// 宏定义数组长度
#define N 5
// 交换两个元素
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// 递归函数,用于生成全排列
void permute(int arr[], int l, int r) {
if (l == r)
printf("%d ", arr[l]);
else {
for (int i = l; i <= r; i++) {
// 交换当前元素和左边界元素
swap(&arr[l], &arr[i]);
// 继续处理剩余部分
permute(arr, l + 1, r);
// 回溯:恢复当前元素到原来位置
swap(&arr[l], &arr[i]);
}
}
}
int main() {
int arr[N] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Permutations of %d elements: \n", n);
permute(arr, 0, n - 1);
return 0;
}
```
这个程序首先定义了一个`permute`函数,它接受一个数组、开始索引`l`和结束索引`r`作为输入。如果开始索引等于结束索引,就打印出该位置的元素;否则,对数组中的每个元素与开始位置的元素进行一次交换,然后递归地调用`permute`处理剩下的元素,并在每次递归返回前恢复原状态。
阅读全文