利用树结构求解经栈操作的所有序列到达问题

利用树结构求解经栈操作的所有序列到达问题浙江省慈溪实验中学张利波315300第八届信息学初赛普及组问题求解第一题:如下图,有一个无穷大的栈S，在栈的右边排列着1，2，3，4，5共五个车厢。其中每个车厢可以向左行走，也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。出口←←12345S↓【模拟分析】这是一例典型的车辆调度题目，其本质是求经过栈操作的到达出口的所有序列，若单纯求数量，可以套用公式C(2n,n)/(n+1)，但要进一步排列所有序列，则需要运用其他方法或结构实现，以前有文章提到运用0、1数字串实现(具体可参看《全国青少年信息学联赛培训教材(复赛篇)》(主编：李建江马茂年)P88例15火车转轨问题)，今天笔者将采用树结构来实现某一状态下(已知首个到达元素)所有符合的输出序列。以上题为例分析，原始序列1、2、3、4、5，第一个到达出口的是3。我们不妨以当前到达出口元素为界限，分成左右两部分。左边：根据原始序列，结合当前到达出口元素，说明该元素左边的所有元素目前处在栈中，若出栈，根据“先进后出”特点，只能选择最近一次入栈的元素2。对于元素较多的一般情况，左边范围的元素作为下一个到达出口的元素，是在其左边，距其最近允许访问的元素，元素若存在，仅有一个。右边：根据当前到达出口的元素，其右元素可以入栈，也可以不入栈(或入栈后马上出栈)。如果选择下一个到达出口的元素，那么可以是右边元素集合中的任一个，且不应遗漏。343452图1那么后继结点，该如何再扩展呢？即在一般情况下，某种状态下到达出口的元素，同样适合于上面分析，按左右分开，左边选择最近的一个未访问的元素(相当于最后一次入栈元素)，右边选择所有未访问过的元素，之所以要求未访问，主要避免重复访问。如图1，若当前元素为2，其下一个到达的元素中，应剔除3，即剔除该结点的祖先(可以通过逐层剔除父结点办法实现)，而其他后继子结点运用同样方法，以此继续发展当前元素的下一层结点。由于涉及到是否访问，在编程实现中需要将原始序列的每个元素添加一个访问标记flag。根据以上分析，我们可以把发展后继子结点的方法看成深度和宽度结合的遍历方式，对于某个元素，先产生其下一层的所有子结点，再在子结点中选择一个，继续产生其下一层的子结点，直到树的深度(到达序列个数)等于原始序列的数量。这个过程总的方向是先深度，后宽度，但在发展深度的一层中先满足该层上的宽度。图2③②④图2③②④⑤①④⑤②⑤④④⑤①⑤④①⑤②②⑤④⑤①①⑤①①①【编程分析】data12345data12345flagtruetruetruetruetrue原始序列初始状态下用数组表示如右：其中flag=true表示该元素允许访问。初始状态下，先由3写入数组，填写其相关参数，pre=0，dep=0，引入指针变量p、q、succ，其中p指向当前扩展的元素下标(此时为1)，q指向填写扩充元素的下标(此时为2)，succ指向扩展的第1个结点下标，用于深度扩展时，将该结点作为扩展时的当前点执行循环操作。然后根据原始序列表格，从左边找到最近的元素2，写入数组q位置，填写参数，a[q].data:=d[j].data，a[q].pre:=p，a[q].dep:=a[p].dep+1，此时，q后移一位，即q:=q+1，左边结束。同样从右边找到所有未访问的元素4，5，可以用循环依次写入a[q]位置，填写参数，同时q后移一位，循环结束，表示左右两边元素已经全部写入数组，即当前元素的下一层结点扩展完成。为避免后继结点对祖先的重复访问，扩展完毕后需把当前元素的访问标记改为false，同时检验当前结点深度是否为最深，若为最深，需回溯，如何回溯后面将有分析。若不为最深，即还需沿深度方向继续扩展结点。这时，将下一个扩展的元素，指向已扩展该层上首个元素(succ)，即p=succ，q不变，succ=q，继续扩展下一层的结点，直到深度为最深max-1。若完成第一个到达序列(即32145)后，数组a元素分布情况，p、q、succ指针情况如下表所示：下标123456789101112data3245145455pre0111222558dep0111222334↑p↑↑qsucc此时，由于深度达到最深max-1，即产生了一个新的序列，该状态下，d[]数组中的访问标记已经全部变成false，即不允许再次访问了。此时要进行回溯了，在回溯前，先撤消当前元素的访问标记，变允许访问，由于在数组中写入一个元素，q指针后移一位，如表格的p,q指针所示，具体语句实现用d[a[q–1].data].flag:=True，同时其父结点的访问标记修改为True，即d[a[p].data].flag:=True。待完成回溯前的准备工作，先回溯到父结点的兄弟结点，即p:=p+1(此时p=9)，如果其深度和父结点的深度相同(此时相同)，说明与父结点是兄弟关系，应扩展该结点；若不是，表示父结点的所有兄弟结点已经全部扩展完毕，意味着再回溯到上上层父结点的兄弟结点。由于回溯，必先修改相关元素的访问标记，此时可以用循环的办法执行d[a[p–1].data].flag:=True，p:=a[p–1].Pre+1，d[a[p–1].data].flag:=True，直到找到可以扩展(尚未扩展)的结点。若这样的结点存在，继续沿深度方向扩展；若不存在，表示已经回溯到根，即该棵树上的所有结点已经扩展完毕，该状态下所有到达的序列排列已经全部生成。剩下问题就是读取生成序列了，先查找数组中的叶子结点，即深度为max-1，找到叶子结点，由前驱pre指引，找到其父结点下标，若不为1，继续找父结点，直到父结点下标为1，即根。查找过程是一个由叶子结点到根结点的过程，而输出序列应由根结点到叶子结点的序列。【参考程序】程序在FreePascal通过。programArriveSerial(input,output);typePointData=recorddata:integer;{访问元素}pre:integer;{前驱}dep:integer;{深度}end;ValueData=recorddata:integer;{访问元素}flag:boolean;{访问标记}end;vari,j,k,max,nowi,n,p,q,succ:integer;{max为序列长度,

nowi为首个到达元素的下标;p,q,succ为指针}d:array[1..10]ofValueData;a:array[1..10000]ofPointData;s:string;procedureSerialPrint();{序列打印过程}varj,succ:integer;answer:char;beginn:=0;fori:=1toq-1doifa[i].dep=max-1thenn:=n+1;{如果是叶子结点，表示一个序列产生}writeln('The',nowi,'tharrivedatfirst,andinthestatethenumberofserialis:',n);writeln('Doyouwanttoseethedetail?(YorN)');{是否查看每个序列}readln(answer);if(answer='Y')or(answer='y')then{如果查看，具体显示每个序列}beginwriteln(n,'serialsshowasfollow.');n:=0;fori:=1toq-1doifa[i].dep=max-1then{从叶子结点开始回溯到根的过程}beginifnmod5=0thenwriteln;{一行显示5个}n:=n+1;j:=i;succ:=1;s[succ]:=chr(a[j].data+ord('0'));{将数字格式转换字符格式}whilej<>0do{逐个登记从叶子结点到根的元素序列}begins[succ]:=chr(a[j].data+ord('0'));{写入数组，以便逆序输出}j:=a[j].pre;succ:=succ+1;end;forj:=succdownto1dowrite(s[j]);{从根到叶子结点依次输出}write(';');end;writeln;end;end;begin{主程序}writeln('inputnumberserial:');{数据输入}readln(s);max:=length(s);writeln('inputfisrtarrivenumber:');readln(nowi);fori:=1tomaxdo{分离各数字}begind[i].data:=ord(s[i])-ord('0');d[i].flag:=true;{标记初始化，允许访问}end;a[1].data:=d[nowi].data;{首个元素写入数组，并填写参数}a[1].pre:=0;a[1].dep:=0;q:=2;p:=1;{初始指针状态，p前，q后}whilep<>0do{是否回溯到最前}beginsucc:=q;{指向下一步(不一定是下一层)扩展元素的下标}k:=a[p].data;{当前扩展元素在原始序列数组d[]中的下标，用于在其左右两边分别查找符合要求的元素写入a[]数组}ifk>1then{找左边}beginj:=k-1;{定位向左查找的初始点}whiled[j].flag<>truedoj:=j-1;ifj>0then{在数组d[]找到，有且仅有1个符合要求的元素}begin{写入到数组a[]}a[q].data:=d[j].data;a[q].pre:=p;a[q].dep:=a[p].dep+1;q:=q+1;end;end;forj:=k+1tomaxdo{找右边}ifd[j].flag=truethen{查找允许访问的所有元素，一一写入数组a[]}begin{写入到数组a[]}a[q].data:=d[j].data;a[q].pre:=p;a[q].dep:=a[p].dep+1;q:=q+1;end;d[k].flag:=false;{扩展该元素的下一层结点后，将该元素的访问标记改为假，不允许被访问}ifa[q-1].dep<>max-1then{没有扩展到最深max-1，不回溯}p:=succ{将当前扩展点标记到下一层结点中的首个元素位置}else{需要回溯}begind[a[q-1].data].flag:=true;{将元素的访问标记重新设为允许访问}d[a[p].data].flag:=true;{父结点的访问标记重新设为允许访问}p:=p+1;{回溯到父结点的兄弟结点}whilea[p].dep<>a[p-1].depdo{父结点的所有兄弟是否全部已经扩展(包含其子孙)，如果是，则需要继续回溯，直到找到可以再扩展的元素}