電車候客問題

作者︰佚名 | 來源︰網絡 | 添加時間︰2006-02-28 22:57:35 | 人氣︰1328

電車候客問題

這個問題時在我寫一個列隊算法時偶爾想到的，
覺得有趣，就拿出看玩玩，
算法的故事描述如下︰
有兩個電車司機，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司機從來不會誤事～呵呵

責任編輯︰冬天來了