[Aha]1~n的全排列

2019-11-06 06:36:15

字体：大中小

来源：转载

供稿：网友

题目：见啊哈算法，P73页。即输入n，生成1~n的全排列。分析：代码比较通俗的理解如何DFS。代码：

#include<iostream>#include<cstdio>#include<cstring>using namespace std ;int a[10],book[10] ,n;void dfs(int step){//step表示站在第几盒子面前 if(step == n+1){//如果站在第n+1个面前，则表示前n个都已经放好了扑克牌。 for(int i = 1 ; i <= n ; i ++) PRintf("%d",a[i]); printf("/n"); return ; } //此时站在第step个盒子面前，应该放哪张拍呢？ //按照1，2，3，...，n的顺序来一一尝试 for(int i = 1 ; i <= n ; i++){ //判断扑克牌i是否还在手上 if(book[i]==0){//book[i]等于0表示第i号扑克牌在手上 //开始尝试使用扑克牌i a[step] = i ;//将第i号扑克牌放到第step个盒子中 book[i] = 1 ; //第step个盒子已经放好扑克牌，接下来需要走到第step+1个盒子。 dfs(step+1); book[i] = 0 ;//将刚才尝试的扑克牌收回 } } return ; }int main(){ while(scanf("%d",&n)!=EOF){ memset(a,0,sizeof(a)); memset(book,0,sizeof(book)); dfs(1); } return 0 ; }

上一篇：ProtoBuffer 简单例子

下一篇：CF 779A Pupils Redistribution 模拟，水题