电车候客问题

作者：佚名 | 来源：网络 | 添加时间：2006-02-28 22:57:35 | 人气：1302

电车候客问题

这个问题时在我写一个列队算法时偶尔想到的，
觉得有趣，就拿出看玩玩，
算法的故事描述如下：
有两个电车司机，A是个老好人，B是个工作狂，
A司机在电车到站候客的时候，每次等待5秒，如果5秒内有人上车，
那么继续重新等待5秒，
知道5秒内没有乘客再次上车或者车上乘客数量已满，才开车，
B司机在电车到站候客的时候，很讲效率，每次总共等待50秒，
50秒内乘客尽量上车，时间一到或者车上乘客已满就开车。

于是有了这个代码：
A bus driver

import java.util.ArrayList;
import java.util.List;

/**
* @author wwei
* @version $Id
* @since 2006-1-10
*/
public class BusA
{
   private List passengersPool = new ArrayList();
   private final int CARRYING_CAPACITY = 60;
   boolean newPassenger = false;

   private final int WAIT_TIME = 5000;

   public void goUp(Passenger passenger)
   {
       List passengers;
       newPassenger = true;
       //有新来的乘客
       this.notifyAll();
       synchronized (this) {
           passengersPool.add(passenger);
           passengers = passengersPool;

           if (CARRYING_CAPACITY <= passengers.size()) {
               busStartup(passengers);
               newPassenger = false;
               passengersPool.clear();
           }
           else {
               try {
                   newPassenger = false;//乘客上车坐下了
                   this.wait(WAIT_TIME);
                   if (!newPassenger) {
                       //等下一个乘客上车的时间到了，发现没有新的乘客
                       busStartup(passengers);
                       newPassenger = false;
                       passengersPool.clear();
                   }
               }
               catch (InterruptedException e) {
                   e.printStackTrace();
               }
               finally{
                   passengersPool.clear();
               }
           }
       }
   }

   private void busStartup(List passengers)
   {
       //开车咯～
   }
}

B bus driver

import java.util.List;
import java.util.ArrayList;

/**
* @author wwei
* @version $Id
* @since 2006-1-10
*/
public class Bus2
{
   private List passengersPool = new ArrayList();
   private final int CARRYING_CAPACITY = 60;
   boolean firstPassenger = true;

   private final int WAIT_TIME = 50000;

   public void goUp(Passenger passenger)
   {
       List passengers;
       synchronized(this){
           passengersPool.add(passenger);
           passengers = passengersPool;
           //第一个乘客上车开始计时
           if(firstPassenger){
               try {
                   firstPassenger = false;
                   this.wait(WAIT_TIME);
                   firstPassenger = true;
               }
               catch (InterruptedException e) {
                   e.printStackTrace();
               }
               finally {
                   passengersPool.clear();
               }
           }
           else if(CARRYING_CAPACITY <= passengersPool.size()){
               //人满走人～
               this.notifyAll();
           }
       }
       if(firstPassenger){
           busStartup(passengers);
       }
   }

   private void busStartup(List passengers)
   {
       //开车咯～
   }
}

两个算法效率当然各有所长，
如果大规模的人一天到晚围堵在候车台的地方，
B司机当然爽歪歪了，上车走人，一气呵成，
当这个候车台的乘客时多时少的时候，
那么，A司机从来不会误事～呵呵

责任编辑：冬天来了