Airport Simulation 是数据结构与算法教材中用于演示Queue的一个小程序（大多数教师似乎会跳过这个练习）。主程序会通过输入总的运行时间、队列里可以等待的最多飞机数量，平均每个时间单元到来的飞机和离开的飞机（提供泊松分布的均值生成随机数）。
运行效果
程序的结构不算复杂，利用Runaway类来封装两个landing和takeoff队列，处理飞机的请求和行为；Plane类来封装飞机的状态和信息，以及在受到指令时输出信息到控制台。只是教材里的讲述有些分散，运行效果也由于输出太多而显得凌乱无比。练习布置许久之后也是一直没有找到一整块时间写完这个练习。这里是前几天完成的一个经过输出优化后的程序，格式比较易于观测。
该程序应在Linux或macOS下编译。在Windows下编译由于不支持彩色输出会出现一些奇怪的转移序列，sleep函数和usleep函数也应当用windows.h中提供的方法实现。
main.cpp和Random.h的源代码如下。其中Random.h用于提供泊松分布的随机数生成，参考自CSDN。
你可以在这里直接下载：https://billc.io/cloud/index.php/s/FeLekECBFKb6GkF
main.cpp:
#include <iostream> #include <queue> #include <unistd.h> #include "Random.h" using namespace std; typedef int feedback; const int success = 1; const int fail = 0; const int USPEED_SHORT = 1000; const int USPEED_LONG = 1000; enum flightStatus{ null, toLand, toTakeoff }; enum runawayAct{ idle, letTakeoff, letLand }; string percentage(int A, int B){ char *temp = new char[100]; sprintf(temp, "%3.2f%%", (double)A / (double)B * 100); string output = temp; return output; } class Plane{ private: int ID; int comingTime; flightStatus status; public: Plane(){ ID = -1; comingTime = -1; status = null; } Plane(int _ID, int _comingTime, flightStatus _status){ usleep(USPEED_SHORT); ID = _ID; comingTime = _comingTime; status = _status; cout << "[PLANE MESSAGE] Plane NO." << ID << " is applying to " << ((status == toLand) ? "land " : "take off ") << endl; } feedback land(int currentTime){ usleep(USPEED_LONG); cout << " 33[42m[PLANE MESSAGE] Plane NO." << ID << " has landed safely. 33[0m" << endl << " Waiting time before landing: " << currentTime - comingTime << "." << endl; } feedback takeoff(int currentTime){ usleep(USPEED_LONG); cout << " 33[42m[PLANE MESSAGE] Plane NO." << ID << " has taken off. 33[0m" << endl << " Waiting time before taking off: " << currentTime - comingTime << "." << endl; } feedback reject(int currentTime){ usleep(USPEED_LONG); if(status == toLand){ cout << " 33[41m[AIRPORT MESSAGE] Plane NO." << ID << "'s landing request is rejected. 33[0m" << endl << " It has been directed to other airports." << endl; } else{ cout << " 33[41m[AIRPORT MESSAGE] Plane NO." << ID << " 's taking off request is rejected. 33[0m" << endl << " This flight is delayed." << endl; } } int getTime(){ return comingTime; } }; class Runaway{ private: queue<Plane> landingQueue; queue<Plane> takeoffQueue; int limit; runawayAct act; int landingRequests; int landingAccepted; int landingRejected; int takeoffRequests; int takeoffAccepted; int takeoffRejected; int idleUnit; int landingWaitedTime; int takeoffWaitedTime; public: Runaway(int _limit){ limit = _limit; landingRequests = 0; landingAccepted = 0; takeoffRequests = 0; takeoffAccepted = 0; takeoffRejected = 0; idleUnit = 0; landingWaitedTime = 0; takeoffWaitedTime = 0; } feedback CanLand(const Plane ¤t){ landingRequests++; feedback result; if (landingQueue.size() < limit){ result = success; landingQueue.push(current); } else{ result = fail; landingRejected++; } return result; } feedback CanTakeoff(const Plane ¤t){ takeoffRequests++; feedback result; if (takeoffQueue.size() < limit){ result = success; takeoffQueue.push(current); } else{ result = fail; takeoffRejected++; } return result; } runawayAct Act(int timeNow, Plane &moving){ runawayAct result; if (!landingQueue.empty()){ landingAccepted++; moving = landingQueue.front(); landingWaitedTime += timeNow - moving.getTime(); landingQueue.pop(); return letLand; } else if(!takeoffQueue.empty()){ takeoffAccepted++; moving = takeoffQueue.front(); takeoffWaitedTime += timeNow - moving.getTime(); takeoffQueue.pop(); return letTakeoff; } else{ idleUnit++; return idle; } } void SumUp(int simulationTime){ cout << endl; cout << " 33[36m=============== SIMULATION RESULTS =============== 33[0m" << endl << " 33[5;3mCalculating... 33[0m" << endl; sleep(2); cout << " 33[1ATotal simulation time: " << simulationTime << endl << "Total flights simulated: " << landingRequests + takeoffRequests << endl << "Total flights required to land: " << landingRequests << endl << "Landing request accepted: " << landingAccepted << endl << "Landing request rejected: " << landingRejected << endl << "Total flights required to take off: " << takeoffRequests << endl << "Taking off request accepted: " << takeoffAccepted << endl << "Taking off request rejected: " << takeoffRejected << endl << "Flights still left in landing queue: " << landingQueue.size() << endl << "Flights still left in taking off queue: " << takeoffQueue.size() << endl << "Average waiting time in landing queue: " << (float)landingWaitedTime / (float)landingAccepted << endl << "Average waiting time in taking off queue: " << (float)takeoffWaitedTime / (float)takeoffAccepted << endl << "Average observing time for landing flights: " << (float)landingRequests / (float)simulationTime << endl << "Average observing time for taking off flights: " << (float)takeoffRequests / (float)simulationTime << endl << "Ratio for successfully landed flights: " << percentage(landingAccepted, landingRequests) << endl << "Ratio for successfully took off flights: " << percentage(landingAccepted, landingRequests) << endl << "Ratio of runaway idle time: " << percentage(idleUnit, simulationTime) << endl << endl << " 33[3;2mSimulation finished. 33[0m" << endl; } }; void initilize(int &totalTime, int &queueLimit, float &arrivingRate, float &departureRate){ cout << " 33[2J 33[0;0H"; cout << "Welcome to the 33[46mAIRPORT SIMULATOR 33[0m." << endl; sleep(1); cout << " 33[36mPlease enter how many time units you will simulate: 33[0m " << flush; cin >> totalTime; cout << " 33[36mHow many flights can be waiting to land or takeoff? 33[0m" << endl << flush; cin >> queueLimit; cout << " 33[36mWhat is the expected arriving flights per unit time? 33[0m" << endl << flush; cin >> arrivingRate; cout << " 33[36mWhat is the expected departing flights per unit time? 33[0m" << endl << flush; cin >> departureRate; } int main(){ START: float arrivingRate, departureRate; int totalTime, queueLimit; initilize(totalTime, queueLimit, arrivingRate, departureRate); int currentTime; int planeID = 0; Random randomSeed; Runaway airport(queueLimit); for (currentTime = 0; currentTime < totalTime; currentTime++){ cout << " 33[2m----- Current excution time: " << currentTime << " ----- 33[0m" << endl; int comingPerUnit = randomSeed.poisson(arrivingRate); for (int num = 0; num < comingPerUnit; num++, planeID++){ Plane currentPlane(planeID, currentTime, toLand); if(airport.CanLand(currentPlane)==fail){ currentPlane.reject(currentTime); } } int departingPerUnit = randomSeed.poisson(departureRate); for (int num = 0; num < departingPerUnit; num++, planeID++){ Plane currentPlane(planeID, currentTime, toTakeoff); if(airport.CanTakeoff(currentPlane)==fail){ currentPlane.reject(currentTime); } } Plane movingPlane; switch (airport.Act(currentTime, movingPlane)){ case letLand: movingPlane.land(currentTime); break; case letTakeoff: movingPlane.takeoff(currentTime); break; case idle: cout << " 33[46m[AIRPORT MESSAGE]: Runaway is idle. 33[0m" << endl; break; } } airport.SumUp(totalTime); char ch; cout << " 33[36mDo you want to initialize another simulation? ([R] or [r] to restart, any other key to exit.) 33[0m" << endl; while(cin.get()!=' ') ; if (toupper(ch = cin.get()) == 'R') goto START; return 0; }
Random.h:
#ifndef RANDOM_H_INCLUDED #define RANDOM_H_INCLUDED #include <iostream> #include <time.h> #include <limits.h> #include <math.h> using namespace std; class Random { public: Random(bool pseudo = true); double random_real(); int random_integer(int low, int high); int poisson(double mean); private: int reseed(); // Re-randomize the seed. int seed, multiplier, add_on; // constants for use in arithmetic operations }; #include "Random.h" Random::Random(bool pseudo) /*Post: The values of seed, add_on, and multiplier are initialized. The seed is initialized randomly only if pseudo == false. */ { if (pseudo) seed = 1; else seed = time(NULL) % INT_MAX; multiplier = 2743; // 斜率 add_on = 5923; // 位移 } int Random::reseed() //Post: The seed is replaced by a pseudorandom successor. { seed = seed * multiplier + add_on; return seed; } double Random::random_real() /*Post: A random real number between 0 and 1 is returned.*/ { double max = INT_MAX + 1.0; //INT_MAX = (2)31 -1 double temp = reseed(); if (temp < 0) temp = temp + max; return temp / max; } int Random::random_integer(int low, int high) // 这个函数在泊松分布中没有用到 { double max = INT_MAX + 1.0; //INT_MAX = (2)31 -1 double temp = reseed(); if (temp < 0) temp = temp + max; return (int)(temp / (max / (high - low + 1.0) + low)); // 返回整数，且有规定范围 } int Random::poisson(double mean) // 泊松分布的实现 { double x = -1; double u; double log1, log2; log1 = 0; log2 = -mean; do { u = random_real(); log1 += log(u); x++; } while (log1 >= log2); return x; } #endif // RANDOM_H_INCLUDED