题目描述 Description
给出一个n, 请输出n的所有全排列
输入描述 Input Description
读入仅一个整数n (1<=n<=10)
输出描述 Output Description
一共n!行,每行n个用空格隔开的数,表示n的一个全排列。并且按全排列的字典序输出。
样例输入 Sample Input
3
样例输出 Sample Output
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
数据范围及提示 Data Size & Hint
这个题只是一个简单的DFS的算法,但是在做到的时候遇到了两个问题,第一CODE[VS]的编译器对定义的全局变量数组是不初始化为0的,这导致RE了好久。第二,关于cout和cin与printf和scanf之间的速度差异问题,一开始使用的代码是这样的:
/************************************************************************* > File Name: 全排列.cpp > Author: zhanghaoran > Mail: chilumanxi@gmail.com > Created Time: 2015年07月17日 星期五 11时41分21秒 ************************************************************************/ #include <iostream> #include <cstring> using namespace std; int n; int flag[11]; int parr[11]; void dfs(int num){ if(num == n + 1){ for(int i = 1; i <= n; i ++){ cout << parr[i] << " "; } cout << endl; return ; } for(int i = 1; i <= n; i ++){ if(flag[i]) continue; parr[num] = i; flag[i] = 1; dfs(num + 1); flag[i] = 0; } return ; } int main(void){ memset(flag,0,sizeof(flag)); memset(parr,0,sizeof(parr)); cin >> n; dfs(1); return 0; }
此时对于9以上的数据就超时了,弄得我很郁闷。一开始想的该不会是输出效率问题吧,但是实际上确实如此,更换以后就AC了这道题目,cin和cout为什么这么慢(据说要比scanf和printf慢一倍多)。网上说:
默认的时候,cin与stdin总是保持同步的,也就是说这两种方法可以混用,而不必担心文件指针混乱,同时cout和stdout也一样,两者混用不会输出顺序错乱。正因为这个兼容性的特性,导致cin有许多额外的开销
那么我们以后就尽量不用cin和cout作为输入输出吧。。