文档介绍：第18课排队买票——回溯电影《》就要开始了,外面有2×n个人排队购买票价为5元的电影票,其中一半人拿一张10元人民币,另一半人拿一张5元的人民币,售票员一开始就没有准备零钱,要使售票员在售票中不发生找钱困难,问这2×n应该如何排队?请你帮她找出所有排队的方案。【分析】根据题意可以看出,要使在售票中,不发生找钱困难,则在排队中,应该是任何情况下,排在前面的持5元的人数等于或多于持10元的人数。该问题可以用二进制数表示,用0表示持5元的人,用1表示持10元和人,那么2n个人排队问题化为2×n个0,1的排队问题。这里我们用数组b[1..2*n]存放持币情况。设k是b数组下标指针,b[k]=0或b[k]=1,另用数组d[0],d[1]记录0与1的个数,且必须满足:n>d[0]d[1]。先将b[1],b[2],…b[2n]置-1,从第一个元素开始搜索,每个元素先取0,再取1,即b[k]+1→b[k],试探新的值,若符合规则,增加一个新元素。若k<2×n,则k值加1,试探下一个元素,若k=2×n则输出b[1],b[2]……,b[2*n]。如果b[k]的值不符合要求,则b[k]再加1,试探新的值,若b[k]=2,表示第k个元素的所有值都搜索过,均不符合条件,只能返回到上一个元素b[k-1],即回溯。返回到上一个元素k:=k-1,并修改d[0],d[1]的值。求出所有解。【参考程序】Programp18_1;constmax=100;varb:array[1..2*max]of-1..2;d:array[0..1]of0..max;done:boolean;total,n,k:integer;procedureprint;{输出一组解}varx:integer;begininc(total);{增加一种可能的排列方案}write('No',total);{输出第几种排列方案}forx:=1to2*ndowrite(b[x]:2);{输出当前的可行排列方案}writeln;end;begin{主程序}write('n=');readln(n);fork:=1to2*ndob[k]:=-1;{初始化数组的值}total:=0;{初始化方案数为0}k:=1;{从第一个位置开始排列}d[0]:=0;{初始化排列中持5元的人数为0}d[1]:=1;{初始化排列中持105元的人数为0}repeatrepeat{按照问题的要求,产生一组数或回溯到上一个元素}done:=false;inc(b[k]);if(b[k]=0)and(d[0]<n)thenbegin{当前排列的当前位置为持5元的人}inc(d[0]);{持5元的人数加1}done:=ture;end;if(b[k]=1)and(d[1]<d[0])then{当前排列的当前位置为持10元的人}ifd[0]>=nthenbegin{持5元的人数超过n}dec(d[0]);{持5元的人数减1}inc(d[1]);{持10元的人数加1}done:=true;end;elsebegininc(d[1]);{持10元的人数加1}done:=true;end;untildoneor(b[k]=2);he if(k=2*n)and(d[0]=d[1])thenprint{一组数满足要求,则输出}elseinc(k){如