3 solutions
-
2
背景
本题求的是1-n的全排列,emm我也不知道为啥会放在新手村,因为这道题需要用到dfs算法。还不知道dfs的同学可以康康这个 https://blog.csdn.net/qq_51536841/article/details/120892489?spm=1001.2014.3001.5501 明白了dfs就很好做了
思路
就是分别把每个数字放在每个位置上,比如n==3时,第一个位置先放1,然后把1标记已经使用,第二个位置就只能放2或3,如果放2,再把2标记,那么第三个位置就只能放3,然后返回第二个位置放3,把2的标记去掉,那么第三个位置就只能放2,再返回到第一个位置,第一个位置放2,把1的标记取消,就可以在后面的位置放1,以此类推。
附上代码
#include<iostream> using namespace std; #define N 10000 int a[N]; int pd[N]={0}; int n; void print(){ for(int i=1;i<=n;i++){ printf("%d ",a[i]); }cout<<"\n"; } void dfs(int x){ if(x==n){ print();//x表示的是当前已经放了几个数了,当n个的时候就可以输出了 return; } for(int i=1;i<=n;i++){ if(!pd[i]){/i未被标记,即可使用 a[x+1]=i;//讲i放再a数组里 pd[i]=1;//标记i表示i被放过了 dfs(x+1);//然后dfs下一个 a[x+1]=0;//此时已经返回当前这个位置了,就表示这个数已经用过了,要换下一个排列了 pd[i]=0;//标记取消让笑一个位置可以用这个数。 } } } int main(){ cin>>n; dfs(0); return 0; }
-
1
1.递归调用(dfs):
#include<bits/stdc++.h> using namespace std; void permutation(vector<int> a, int begin_, int end_){ if(begin_ == end_){ for(auto i:a)cout<<i<<" "; cout<<endl; return; } for(int i=begin_;i<=end_;i++){ swap(a[i],a[begin_]); sort(a.begin()+begin_+1,a.begin()+end_+1); permutation(a, begin_+1, end_); swap(a[i],a[begin_]); } } int main(){ int n; cin>>n; vector<int> a; for(int i=1;i<=n;i++){ a.push_back(i); } sort(a.begin(),a.end()); permutation(a, 0, n-1); //传入的数组,起始下标 return 0; }
2、stl库中的next_permutation函数:
#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> a; for(int i=1;i<=n;i++){ a.push_back(i); } sort(a.begin(),a.end()); do { for(auto i:a)cout<<i<<" "; cout<<endl; } while(next_permutation(a.begin(),a.end())); return 0; }
-
1
除了用dfs解决这个问题以外,我们也可以用一用stl库里面的next_permutation
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<vector> using namespace std; int num[10000005]; int main(void) { int n; cin>>n; for(int i=1;i<=n;i++) num[i-1]=i; sort(num,num+n); do{ for(int i=0;i<n;i++) cout<<num[i]<<" "; cout<<endl; }while(next_permutation(num,num+n)); return 0; }
- 1
Information
- ID
- 45
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 5
- Tags
- # Submissions
- 338
- Accepted
- 122
- Uploaded By