前言
题目介绍
输入样例:
3
1 2 3
输出样例:
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
在开始之前大家可以先自己写一下看一下能不能自己写出来~注意输出的格式哦！
引入：
这个问题，不用说一看就是一个递归或者递推的问题，鄙人不才，只会递归。。所以说怎么进行递归呢？？
首先你要看看这个排序是你懂吧！你看那个3,1,2和3,2,1就是先1,2后2,1这种，我当时做了一晚上，**就有一些测试案例不对！！！很烦！
这个题需要用到回溯法
理论存在，实践开始！
解决方案：
错误方案1：
#include <stdio.h>
void swap(int *q,int *p)
//两个数交换函数，注意函数的形参要用指针变量，这样才能是目标数组中的数据改变；
{
int t;
t = *q; //将q指针指向的数据赋给t；
*q = *p;
*p = t; //将t中的数据赋给p指针指向的位置空间；
}
void f(int a[],int k,int m)
//定义一个求全排列的函数，在下面递归中就将这个函数作为已知完整的函数使用；
{
int i;
if(k==m) //递归结束的标志；
{
for(i=0; i<=m; i++)
{
if(i==0)
printf("%d",a[i]);
else printf(",%d",a[i]);
}
printf("\n");
}
else
{
for(i=k; i<=m; i++)
{
swap(&a[k],&a[i]);
f(a,k+1,m);
swap(&a[k],&a[i]);
}
}
}
int main ()
{
int array[11],i,t,n;
while(~scanf("%d",&t))
{
while(t--)
{
scanf("%d",&n);
for(i=0; i<n; i++)
{
scanf("%d",&array[i]);
}
f(array,0,n-1);
}
}
return 0;
}
这样的话后面那两个案例会先输出3,2,1再输出3,1,2不全对！
错误方案2：
#include<stdio.h>
int a[10],c[10],n,d[10];//c数组对出现过的数字进行标记，d数组为记录答案的数组
void dfs(int i);
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
c[i]=0;//对计数数组进行初始化
}
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
dfs(0);
}
void dfs(int x)
{
if(x==n)
{
for(int v=0;v<n;v++)
{
printf("%d ",d[v]);
}
printf("\n");
return ;
}
else
{
for(int i=0;i<n;i++)
{
if(c[i]==0)
{
d[x]=a[i];
//printf("%d ",a[i]);
c[i]=1;
dfs(x+1);
c[i]=0;
}
}
}
}
这样只能输入一个数，而且不能案例全对（别问，我本来想偷鸡来）
正确方案1：
递归回溯法：（代码后有注释哦！！！）
#include<stdio.h>
void f(int *a, int p, int q)
{
int j,i;//循环变量
if(q == p)// 递归截止条件：尾变量=头变量,截止后输出。
{
for(i = 0 ; i <= q ; i++)
{
if(i == q)
{
printf("%d\n",a[i]);
}// 打印最后一个
else printf("%d,",a[i]);// 打印前面的
}
}
else//进行递归
{
for(i = p ; i <= q ; i ++) //遍历数组每一个
{
if(i == 0)
{
f(a, p + 1, q);//对第二个数以及以后的数进行全排列
}//当p是数组的第一个数时
else
{
int t = a[i];//暂时存一下
for(j = i - 1 ; j >= p ; j --)
{
a[j + 1] = a[j];
}
a[p] = t ;//把第i个数放到最前面
f(a, p + 1 , q);//使用递归求后面的全排列
t = a[p];
for(j = p + 1; j <= i ; j ++)
{
a[j - 1] = a[j];
}
a[i] = t;// 回溯（把第一个数放到末尾）
}
}
}
}
int main()
{
int n ;
scanf("%d",&n);
int a[100] ;
int i;
for(i = 0 ; i < n ; i ++)
{
scanf("%d",&a[i]);
}
f(a, 0, n - 1);//进行全排列
}
总结：
讲一下这个是怎么递归的吧！你看这个！如果输入123的话，他会这样进行！
绿色的是进行回溯的先后
红色的是打印数据的前后
嘿嘿，好好看看应该能看懂吧，很简单的递归回溯问题！
就是把每一个数都移到首位然后再移回去进行回溯！把每个数移到首位就可以实现全排列！
有点不详细哈。。应该能看懂吧，等我考完试再补充补充（画大饼）
Love is worth years.❤
热爱可抵岁月漫长。
