字典序的递归写法
程序员文章站
2022-06-03 12:09:08
...
//算法竞赛入门经典的7.2枚举排列
伪代码
void Print_permutation(序列A,集合S)
{
if(S为空) 输出序列A;
else 按从小到大的顺序依次考虑S的每个元素V
{
Print_permutation(在A的末尾添加V后得到的新序列,S-{V});
}
首先不考虑序列A和集合S如何表示,首先理解一下伪代码。
递归边界是S为空的情况;
按照从小到大的顺序考虑S中的每个元素;
每次递归调用以A开头
#include <iostream>
using namespace std;
int A[10];
int n,cur;
int Print_permutation(int n,int *A,int cur)
{
if(cur==n)
{
for(int i=0;i<n;i++)
cout<<A[i]<<" ";
cout<<endl;
}
else
{
for(int i=1;i<=n;i++)
{
int ok=1;//检查变量是否用过
for(int j=0;j<cur;j++)
{
if(A[j]==i) ok=0;
}
if(ok)
{
A[cur]=i;//i没有出现过,添加到末尾,递归调用
Print_permutation(n,A,cur+1);
}
}
}
}
int main()
{
cin>>n;
Print_permutation(n,A,0);
return 0;
}
上一篇: 2020-11-22
下一篇: 递归——汉诺塔