首页 > 代码库 > [Wikioi 1294]全排列---两种不同的解法(复习)
[Wikioi 1294]全排列---两种不同的解法(复习)
题目描述 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还是用STL库都能轻松过，毕竟这题数据太弱了
1、纯DFS
#include <stdio.h>#define MAXN 100int num[MAXN],out[MAXN];int n; //num[i]=1表示数字i已经打印过了,n=打印1-n的字典序全排列void dfs(int step){ int i,j,flag=0; if(step>n) { for(i=1;i<=n;i++) printf("%d ",out[i]); printf("\n"); return; } for(i=1;i<=n;i++) { if(num[i]==0) //如果数字i没被用过 { num[i]=1; out[step]=i; dfs(step+1); num[i]=0; out[step]=0; } }}int main(){ scanf("%d",&n); dfs(1); return 0;}
2、C++ STL的next_permutation函数
#include <stdio.h>#include <algorithm>int a[10]={1,2,3,4,5,6,7,8,9,10},n;void print(){ for(int i=0;i<n;++i) { printf("%d ",a[i]); } printf("\n");}int main(){ scanf("%d",&n); print(); while(std::next_permutation(a,a+n)) { print(); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。