Question

C语言 求此全排列递归算法解析

求此算法的解析 还有其中的一个问题：used[MAX]是未初始化的 ，而下文中
用到了if(!used[i]),而且经运行无错误产生，究竟是什么情况？
#include<stdio.h>
#define MAX 10
int used[MAX];
int result[MAX];
int N;
void print()
{
int i;
for(i=0;i<N;i++)
printf("%d ",result[i]);
printf("\n");
}
void proc(int step)
{
int i;
if(step==N)
print();
else
{
for(i=0;i<N;i++)
{
if(!used[i])
{
used[i]=1;
result[step]=i+1;
proc(step+1);
used[i]=0;
}
}
}
}
int main()
{
scanf("%d",&N);
proc(0);
return 0;
}

Answer 1

used数组是全局变量有隐含初值0；
关于全排列的算法你可以理解为深搜加回溯。
#include<stdio.h>
#define MAX 10
int used[MAX]; //用来标记数字是否已经在前面使用过
int result[MAX]; //存放结果
int N;
void print() //输出结果
{
int i;
for(i=0;i<N;i++)
printf("%d ",result[i]);
printf("\n");
}
void proc(int step) //step用来记录已经摆好了几个数
{
int i;
if(step==N) //如果已经摆好了N个数，那么结果就产生了，就输出结果
print();
else
{
for(i=0;i<N;i++) //枚举1-N，找到没有使用过的最小的数
{
if(!used[i]) //没有使用过
{
used[i]=1; //标记i已经使用
result[step]=i+1; //记录结果
proc(step+1); //递归求解
used[i]=0; //这里就是所谓的回溯，也许比较难理解，你可以人工走一遍加深理解。其实回溯的主要想法是"还原现场".当执行到这一步时，i+1 这个数放在第step个位置的情况已经解决了，我们就要拿出i+1这个数，把它标记为未使用。
}
}
}
}
int main()
{
scanf("%d",&N);
proc(0);
return 0;
}

Answer 2

其实used是应该在main里面初始化的
可以#include <string.h>
然后main里面memset(used,0,sizeof(used));

这个算法生成全排列其实就是枚举的过程
假设有n位，前k位已经生成好了，这时递归进行了k层也就是step=k，然后枚举下一位是哪个数字，所以需要用used数组标记每个数字是否用过，然后回溯。当k==n的时候这时，所有的n位已经生成好了，就可以输出当前的排列了。

还是不懂得话，可以让n=4，然后手动的跟踪调试一下就好啦~

Answer 3

used数组是全局变量有隐含初值0；
关于全排列的算法你可以理解为深搜加回溯。
#include<stdio.h>
#define
MAX
10
int
used[MAX];
//用来标记数字是否已经在前面使用过
int
result[MAX];
//存放结果
int
N;
void
print()
//输出结果
{
int
i;
for(i=0;i<N;i++)
printf("%d
",result[i]);
printf("\n");
}
void
proc(int
step)
//step用来记录已经摆好了几个数
{
int
i;
if(step==N)
//如果已经摆好了N个数，那么结果就产生了，就输出结果
print();
else
{
for(i=0;i<N;i++)
//枚举1-N，找到没有使用过的最小的数
{
if(!used[i])
//没有使用过
{
used[i]=1;
//标记i已经使用
result[step]=i+1;
//记录结果
proc(step+1);
//递归求解
used[i]=0;
//这里就是所谓的回溯，也许比较难理解，你可以人工走一遍加深理解。其实回溯的主要想法是"还原现场".当执行到这一步时，i+1
这个数放在第step个位置的情况已经解决了，我们就要拿出i+1这个数，把它标记为未使用。
}
}
}
}
int
main()
{
scanf("%d",&N);
proc(0);
return
0;
}

Answer 4

其实都不建议这样用，递归这东西理解起来确实很困难。

追问

学c语言才半学期 学校就给出了算法题 我也觉得理解困难
能不能给详细解释下

追答

我也没完全看懂！！