问题：设有n辆火车。根据它们的入站顺序把火车标号为1，2，...,n。火车站为一栈式车站，问有多少种出站方式？
举例：n=5,12543就是一种。具体为：1入站，1出站，2入站，2出站，3，4，5入站，5，4，3出站。
很早以前就想过这个问题了, 但一直都没有什么好的解决方法。上网找了一下也没有，也就把这个问题给忘了。 前几天做数据结构题时
发现一个有趣的题，这是中科大91年的题目：
栈的输入是123...n，输出序列是a1,a2,...an。若ai=n(1<=i<=n),则有ai>ai+1>an
判断这个命题是否正确。
我觉得命题是正确的，但我买的复习资料说这个命题错了，却没给解释。
如果不考虑没有意义的情况，即i＝n,i+1没有意义，这个命题应该是正确的。
可以说这个条件是输出序列合理的必要条件。但它不是充要条件。
下面是一个充要条件：
对于输出序列中的每一个数，在它后面的且比它小的数是降序排列的。
证明：
必要性：
对于任意的ai及在它之后出栈且比它小的am1,am2,...alk。因为am1,am2,...amk<ai，说明am1,am2,amk在ai之前入栈，
且ai出栈前它们都还没有出栈，又因为它们出栈顺序是am1,am2,...,amk。所以它们入栈的顺序是amk,...,am2,am1。所以
am1>am2>...>amk。
充分性：
如果一个输出序列满足条件，设为b1,b2,...,bn。 则我们把1到b1间的数入栈，然后把b1出栈，再看b2。如果b2<b1,则b2
=b1-1（因为b1-1是小于b1最后一个入栈的），则把b2=b1-1出栈，否则把b1+1到b2入栈，再b2出栈。一直重复下去，就得到合理
的进出栈方式。
可以举个例子来验证证明过程：
输入是1234，输出是1423。显然4后面的23比4小但不是降序排列。因为4在23前出栈，23在4入栈前已入栈且还没出栈，又因为
2在3前入栈，所以2在3后出栈。
输入是1234，输出是1432。我们可以构造进出栈方式：1入栈出栈。4比1大，将234入栈，4出栈。3＝4－1，3出栈，2＝3－1，2
出栈。
有了这个充要条件就可以判断一个输出序列是否合理的。如果要求所以的合理进出栈方式：则可以先产生n！中排列，来进行判断。
用它来解决一些题也非常简单，比如下面的一些题目。
1. （北航2002年） 若某堆栈的输入序列为1，2，3，...,n，输出序列的第一个为n，则第i个为：
2. （中科院软件所2000年）设堆栈的输入序列是（1，2，3，4），则 不可能是其出栈序列。
A 1243 B 2134 C 1432 D 4312 E 3214
还有一个问题就是有多少中可能的输出：答案是(2n)!/(n!*n!)/(n+1)。 这是北邮的一道题。
它给出的答案是：假设对二叉树的n个节点从1到n加以编号，且令其前序序列为1，2，...,n，则不同二叉树得到的中序序列不同。因此
不同形态的二叉树的数目恰好等于前序序列为1，2，...,n的中序序列的数目，而中序遍历的过程实质是一个节点进栈和出栈的过程。
数列1,2,..,n按不同顺序进栈和出栈所能得到的排列的数目恰好为由前序序列1，2，...,n所能得到的中序序列的数目，也就是前序序列
为1,2,...n的不同形态的二叉树的数目。
这个数目为：(2n)!/(n!*n!)/(n+1)
它把这个问题转化成了树的计数问题。想破脑袋也想不出，记住答案也就算了。
还有就是输出所有合理的出栈序列的问题。
前面说了可以产生所有的n！个组合数然后再判断的方法。
下面还给出了一种回溯的算法。
算法的思想是：
先放置最大的n，它有n个可能位置。
然后放置n-1，如果它在n的左边（n不在第一个位置），则没有限制，
但如果在右边，则只能n的下一个位置。因为n-1是小于n的最大数。
接着放n-2，如果n-2在n-1的左边则n-2在比它大的（n,n-1)的左边，在n-2的右边时只能在n-1右边的第一个非空位置。
putNumber(int k, int[] pos){//把k安排到合适的位置，假设k+1,...,n已经放好。pos[i]=k表示第i个位置已经放了k,没有放数时为0。
if(k==0){
//打印出数组pos
return;
}
//根据当前的pos数组值生成k可放的所有位置。
for k可放的每一个位置possiblePos
pos[possiblePos]=k;//k放在possiblePos上
putNumber(k-1,pos);//试探
pos[possiblePos]=0;//回溯
}
生成合理安排的算法：
当前k的可能位置：k+1位置左边为空的位置以及k+1右边第一个非空位置。
下面举例假设n=5, 则5可以放在任何位置，假设在第3（下标从1到5）在4可以放在1，2或4。
假设5放在位置3，4放在位置2，则3可以放在4的左边的空位1和4右边第一个非空位4。
下面是一个完整的Java实现：
/**
* <p>Title: </p>
* <p>Description: </p>
* <p>Copyright: Copyright (c) 2004</p>
* <p>Company: </p>
* @author not attributable
* @version 1.0
*/
import java.util.*;
import java.io.*;
public class StackPushPop {
private int totalCount=0;
public StackPushPop() {
}
public static void main(String[] args) {
StackPushPop stackPushPop = new StackPushPop();
int n=4;
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
try {
String inStr = reader.readLine();
n=Integer.valueOf(inStr).intValue();
}
catch (IOException ex) {
}
int []pos=new int[n];
for(int i=0;i<n;i++){
pos[i]=0;
}
stackPushPop.putNumber(n,pos);
System.out.println("Total Possible Count: "+stackPushPop.totalCount);
}
public void putNumber(int k, int[]pos){
if(k==0){
this.totalCount++;
for(int i=0;i<pos.length;i++){
System.out.print(pos[i]+"");
}
System.out.println();
return;
}
List possiblePos=generatePos(k,pos);
for(int i=0;i<possiblePos.size();i++){
int tmp=((Integer)possiblePos.get(i)).intValue();
pos[tmp]=k;
putNumber(k-1,pos);
pos[tmp]=0;
}
}
List generatePos(int k, int[] pos){
List result=new ArrayList();
int i;
for(i=0;i<pos.length;i++){
if(pos[i]==0){
result.add(new Integer(i));
}
else if(pos[i]==k+1)
break;
}
for(;i<pos.length&&pos[i]!=0;i++);
if(i<pos.length){
result.add(new Integer(i));
}
return result;
}
}
|
本类阅读TOP10