Bill Chen

I play code and pixels.

HomeArchiveSearchAbout

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

2019-03-29#Algorithm#C/C++#Solution

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

运行效果

程序的结构不算复杂，利用 Runaway 类来封装两个 landing 和 takeoff 队列，处理飞机的请求和行为；Plane 类来封装飞机的状态和信息，以及在受到指令时输出信息到控制台。只是教材里的讲述有些分散，运行效果也由于输出太多而显得凌乱无比。练习布置许久之后也是一直没有找到一整块时间写完这个练习。这里是前几天完成的一个经过输出优化后的程序，格式比较易于观测。

该程序应在 Linux 或 macOS 下编译。在 Windows 下编译由于不支持彩色输出会出现一些奇怪的转移序列，sleep 函数和 usleep 函数也应当用 windows.h 中提供的方法实现。

main.cpp 和 Random.h 的源代码如下。其中 Random.h 用于提供泊松分布的随机数生成，参考自 CSDN。

你可以在这里直接下载：https://cloud.billc.io/s/FeLekECBFKb6GkF

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#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

Toc

Contact

Archives

Categories

Tags

一个简单的 Adobe Premiere Pro 入门指南使用 VSCode 在 Mac 上配置 C/C++ 调试环境
©️ Bill Chen | 2019 - 2021
Theme By RandomYang Powered By hexo