1. 从1-n这n(n<20)个整数中随机选择任意多个,输出所有可能的选择方案。
int n; vector<int> v; inline int dg(int t) { if(t>n){//递归边界 调试的时候要看一下只有一个等极端数据对不对 if(v.size()==0) cout<<"空集"<<endl; else{ for(int i=0; i<v.size(); ++i) printf("%d ",v[i]); cout<<endl; } }else{/*递归树左右子树顺序根据最方便还原现场的方法去写, 也就是根左右和跟右左是等效的, 但是递归从根到叶再到根的顺序是固定的*/ //左边的分支(可以看成边,也就是转换条件) dg(t+1);//下一层递归,可以看成是递归树上当前节点的左右子树 //还原现场(根据边上的转换条件进行现场还原,因为要保持左右边进入时初始状态都是当前结点状态) v.push_back(t);//右边的分支 dg(t+1);//递归树当前节点左右子树 v.pop_back();//还原现场 } } int main(){ while(1){ cin>>n; dg(1);//最大最完整的一棵递归树,当前状态处于根节点 } return 0; }
2. 把1-n这n(n<10)个整数排成一行后随机打乱顺序,输出所有可能的次序。(全排列)
int n; int a[maxn]; int main() { while(1){ sc(n); for(int i=1;i<=n;++i) a[i-1]=i; do{ for(int i=0;i<n;++i) printf("%d ",a[i]); cout<<endl; }while(next_permutation(a,a+n)); } return 0; }
3.把1-n这n(n<10)个整数排成一行后随机打乱顺序,输出所有可能的次序。(递归)
int order[maxn]; bool chosen[maxn]; int n; bool dg(int x){ if(x>=n){ for(int i=0; i<n; ++i) printf("%d ",order[i]); cout<<endl; }else{ for(int i=1; i<=n; ++i)//当前递归树有n个分支,接下来dfs每个分支 if(!chosen[i]){ chosen[i]=1; order[x]=i; dg(x+1); //还原结点是为了进入同一层递归结点的时候初始状态是一样的 chosen[i]=0; } } } int main(){ while(1){ sc(n); for(int i=0;i<=n;++i) order[i]=0; dg(0);//从第0个位置开始 } return 0; }