当前位置： 首页 > news >正文

Airport Simulation (数据结构与算法 – 队列 / Queue 的应用)

news 来源：原创 2024/5/19 20:54:17

Airport Simulation 是数据结构与算法教材中用于演示Queue的一个小程序（大多数教师似乎会跳过这个练习）。主程序会通过输入总的运行时间、队列里可以等待的最多飞机数量，平均每个时间单元到来的飞机和离开的飞机（提供泊松分布的均值生成随机数）。

https://billc.io/wp-content/uploads/2019/03/image-14-1600x1238.png运行效果

程序的结构不算复杂，利用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 << "\033[42m[PLANE MESSAGE] Plane NO." << ID << " has landed safely.\033[0m" << endl
             << "                Waiting time before landing: " << currentTime - comingTime << "." << endl;
    }
    feedback takeoff(int currentTime){
        usleep(USPEED_LONG);
        cout << "\033[42m[PLANE MESSAGE] Plane NO." << ID << " has taken off.\033[0m" << endl
             << "                Waiting time before taking off: " << currentTime - comingTime << "." << endl;
    }
    feedback reject(int currentTime){
        usleep(USPEED_LONG);
        if(status == toLand){
            cout << "\033[41m[AIRPORT MESSAGE] Plane NO." << ID << "'s landing request is rejected.\033[0m" << endl
                 << "                  It has been directed to other airports." << endl;
        }
        else{
            cout << "\033[41m[AIRPORT MESSAGE] Plane NO." << ID << " 's taking off request is rejected.\033[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 &current){
        landingRequests++;
        feedback result;
        if (landingQueue.size() < limit){
            result = success;
            landingQueue.push(current);
        }
        else{
            result = fail;
            landingRejected++;
        }
        return result;
    }
    feedback CanTakeoff(const Plane &current){
        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 << "\033[36m=============== SIMULATION RESULTS ===============\033[0m" << endl
             << "\033[5;3mCalculating...\033[0m" << endl;
        sleep(2);
        cout
            << "\033[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
            << "\033[3;2mSimulation finished.\033[0m" << endl;
    }
};
void initilize(int &totalTime, int &queueLimit, float &arrivingRate, float &departureRate){
    cout << "\033[2J\033[0;0H";
    cout << "Welcome to the \033[46mAIRPORT SIMULATOR\033[0m." << endl;
    sleep(1);
    cout << "\033[36mPlease enter how many time units you will simulate:\033[0m\n"
         << flush;
    cin >> totalTime;
    cout << "\033[36mHow many flights can be waiting to land or takeoff?\033[0m" << endl
         << flush;
    cin >> queueLimit;
    cout << "\033[36mWhat is the expected arriving flights per unit time?\033[0m" << endl
         << flush;
    cin >> arrivingRate;
    cout << "\033[36mWhat is the expected departing flights per unit time?\033[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 << "\033[2m----- Current excution time: " << currentTime << " -----\033[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 << "\033[46m[AIRPORT MESSAGE]: Runaway is idle.\033[0m" << endl;
            break;
        }
    }
    airport.SumUp(totalTime);
    char ch;
    cout << "\033[36mDo you want to initialize another simulation? \n([R] or [r] to restart, any other key to exit.)\033[0m" << endl;
    while(cin.get()!='\n')
        ;
    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

 

来源：https://billc.io/2019/03/airport-simulation/

转载于:https://www.cnblogs.com/BillChen2000/p/airport-simulation.html

相关文章：

  • 掌握 Dojo 工具包
  • js中用变量作为$()内id的值、动态获取id，及获取其下面的class元素
  • 读Google三大论文后感
  • 数据展现DataList控件（26）
  • [转帖] 使用 InstallShield 安装和卸载SQL Server 数据库
  • Spring Cloud微服务如何设计异常处理机制？
  • SpringCloud 之 Bus消息总线
  • 26步打造高访问量网站[经典]
  • Silverlight 4中把DataGrid数据导出Excel—附源码下载
  • 类加载、反射
  • Ubuntu 中的编程语言(上)
  • 17.Merge Two Binary Trees（合并两个二叉树）
  • 03与08组策略区别
  • [Pytorch] pytorch笔记 三
  • 五子棋游戏
  • [LeetCode] Wiggle Sort
  • 【个人向】《HTTP图解》阅后小结
  • Apache的80端口被占用以及访问时报错403
  • cookie和session
  • JavaScript对象详解
  • Lucene解析 - 基本概念
  • PHP的Ev教程三(Periodic watcher)
  • Unix命令
  • 讲清楚之javascript作用域
  • 理解IaaS, PaaS, SaaS等云模型 (Cloud Models)
  • 前端存储 - localStorage
  • 我是如何设计 Upload 上传组件的
  • 消息队列系列二（IOT中消息队列的应用）
  • kubernetes资源对象--ingress
  • #我与Java虚拟机的故事#连载05：Java虚拟机的修炼之道
  • （C语言）fgets与fputs函数详解
  • （day 12）JavaScript学习笔记（数组3）
  • (done) 两个矩阵 “相似” 是什么意思？
  • （八）c52学习之旅-中断实验
  • （第一天）包装对象、作用域、创建对象
  • （附源码）springboot优课在线教学系统 毕业设计 081251
  • （附源码）计算机毕业设计SSM基于健身房管理系统
  • （含react-draggable库以及相关BUG如何解决）固定在左上方某盒子内（如按钮）添加可拖动功能，使用react hook语法实现
  • （黑马C++）L06 重载与继承
  • (汇总)os模块以及shutil模块对文件的操作
  • （蓝桥杯每日一题）love
  • （最简单，详细，直接上手）uniapp/vue中英文多语言切换
  • **PHP分步表单提交思路（分页表单提交）
  • *1 计算机基础和操作系统基础及几大协议
  • .MSSQLSERVER 导入导出 命令集－－堪称经典，值得借鉴！
  • .NET CORE 3.1 集成JWT鉴权和授权2
  • .net 按比例显示图片的缩略图
  • .NET6 命令行启动及发布单个Exe文件
  • .NET构架之我见
  • ？？javascript里的变量问题
  • ??在JSP中，java和JavaScript如何交互？
  • @AliasFor注解
  • @GetMapping和@RequestMapping的区别
  • @Not - Empty-Null-Blank
  • [ vulhub漏洞复现篇 ] Apache Flink目录遍历(CVE-2020-17519)