购票问题（回溯法）

#include<bits/stdc++.h> using namespace std; double a[100]; int n,tot; void Print() { int i=1; tot++; for(i=1;i<=2*n;i++) { if(i>1) { printf(","); } cout<<a[i]; } cout<<endl; } void find(int t,int sum1,int sum2){//当前排队人数t sum1有多少人用了0.5 sum2是有多少人用了1 int i; if(t>2*n)//如果填满了，输出并结束递归 { Print(); return; } if(sum1==n)//如果0.5的用完了，剩下的全部赋1，并结束递归 { for(i=t;i<=2*n;i++) { a[i]=1; } Print(); return; } a[t]=0.5;//假设下一个人拿0.5 find(t+1,sum1+1,sum2);//搜索 if(sum1>sum2)//如果拿0.5的人多于拿1的 { a[t]=1;//假设下一个人拿1 find(t+1,sum1,sum2+1);//搜索 a[t]=0;//回溯 } } int main() { scanf("%d",&n); find(1,0,0); return 0; }

运行结果