深搜--全排列
[题 目]
输入一个数n,输出1~n的全排列。 举例:假如有编号为1 2 3的3张扑克牌和编号为1 2 3
的3个盒子里,并且每个盒子有且只能放一张扑克牌。那么一共有多少种不同的放法呢
[分 析]
当小哼走到第四个盒子的时候,已经完成一种排列。产生一种排列之后小哼需要立即返回。小哼需要退一步重新回到3号盒子前面,取回放在3号盒子的扑克牌,再往3号盒子放牌时已没有别的选择,于是再回退一步,回到2号盒子面前,收回2号牌。现在需要往2号盒子放3号牌,再把仅剩的2号牌放入3号盒子,又来到4号盒子,产生新排列132,按此步骤模拟,会依次产生所有排列213 231 312 321
[代 码]
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
int a[10],book[10],n;
void dfs(int step)//step表示站在第几个盒子面前
{int i;
if(step==n+1) //如果站在第n+1个盒子面前,则表示前n个盒子已经放好扑克牌
{//输出一种排列(1-n个盒子中的扑克牌)
for(i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
return;// 返回之前的一步 (最近一次调用dfs函数的地方) 回溯
}
for(i=1;i<=n;i++)
{//判断扑克牌i是否还在手中
if (book[i]==0)
{a[step]=i;//将i号扑克牌放入到第step个盒子中
book[i]=1;//将book[i]设为1,表示i号扑克牌已经不在手上
//第step个盒子已经放好扑克牌,接下来需要走到下一个盒子面前
dfs(step+1);
book[i]=0;//这是非常重要的一步,一定要将刚才尝试的扑克牌收回,才能进行下一次尝试
}
}
return;
}
int main()
{cin>>n;//输入的时候要注意n为1-9之间的整数
dfs(1); //首先站在1号小盒子面前
return 0;
}