PTA练习题7-2输出全排列（20分）递归法（C语⾔实现）
**
7-2 输出全排列 (20 分)
**
请编写程序输出前n个正整数的全排列（n<10），并通过9个测试⽤例（即n从1到9）观察n逐步增⼤时程序的运⾏时间。
输⼊格式:
输⼊给出正整数n（<10）。
输出格式:
输出1到n的全排列。每种排列占⼀⾏，数字间⽆空格。排列的输出顺序为字典序，即序列a1,a2,…,a n排在序列b1,b2,…,b n之前，如果存在k使得a1=b1,…,a k=b k
并且 a k+1<b k+1。
输⼊样例：
3
输出样例：
123
132
213
231
312
321
代码部分
#include<stdio.h>
#define YES 1
#define NO 0
int order[10],is_mark[10],n;
//在此使⽤全局变量，数组order⽤来存储排序组合，数组is_mark⽤来标记某⼀个数是否在排序⾥被⽤过，默认没⽤过(NO) //注意：函数初始化不要忘
void recursion(int k)
//递归函数思路：传⼊的参数k⽤于表⽰待填⼊数字的位序，先判断该位置是否合理（有没有超过n）不合理就输出全部，//合理就往该位置处填⼊数字，填完之后，递归调⽤填下⼀个位置的数。
{
int i;
//判断。。不合理就代表能填的位置都已经填完了，直接将序列输出就可以了
if(k>n){
for(i=1;i<n;++i)printf("%d",order[i]);
printf ("%d\n",order[n]);
return;
}
//否则（合理）就进⾏往⾥⾯填数操作
else{
for(i=1;i<=n;++i){//该for循环⽤于不断从1开始试每⼀个数
if(!is_mark[i]){//is-mark数组记录的是数i有没有被⽤过。
order[k]=i;is_mark[i]=YES;// 如果没有被⽤过，就将i填⼊k位置处，将i标记为已经使⽤
recursion(k+1);//递归调⽤，⽤于填⼊下⼀个位置（k+1）的值
c语言编写递归函数order[k]=0;is_mark[i]=NO;//调⽤结束后把该位置空出来，原来⽤过的数也取消标记
}
}
}
}
int main ()
{
scanf ("%d",&n);
recursion(1);
return0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。