火车进出栈式车站问题

类别:Java 点击:0 评论:0 推荐:

                       
   问题:设有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;
  }

}

       
           

 

   
  
   

本文地址:http://com.8s8s.com/it/it12819.htm