이러쿵저러쿵


Question!

 

Write a program that simulates a (single) checkout line at a supermarket. The line is a queue object. Customer(i.e., customer objects) arrive in random integer intervals of 1—4 minutes. Also, each customer is served in random integer intervals of 1—4 minutes. Run the supermarket simulation for a 12-hour day (720 minutes) using the following algorithm:

 

 

 

For the better service at the next time, the supermarket decided to record the name of the customers. A customer’s name is a random integer between 0 to 10000. Whenever a new customer arrives at the queue, you assign a new random name to the customer. We assume the customer’s name is unique for every customer. For efficiency, the customers’ names are recorded in the binary search tree structure (forget about balancing).

 

 

After the simulation, you display the binary tree for the customers’ names on the screen. The function should output the tree row by row, with the top of the tree at the left on the screen and the bottom of the tree toward the right of the screen. Each row is output vertically. For example, one example output is as follows:

 

 

 

 

 

 

where 83 is a root of the tree having left child 71 and right child 97, and so on.

 

 

 

 

Solution!

 

1) Description the usage of the program.

 

 

1-1) Execution

 

* At the Console Window, Use a similar form following. And there are two execution way.

 

First Way : If you just input the command ‘simulate’, You can simulate the program with default value.

- Default Value 1: Maximum Interval time of customers’ arrival is 4 (1 ~ 4 minutes)

   - Default Value 2: Maximum Interval time of service for customer is 4 (1 ~ 4 minutes)

 

   - Default Value 3: Simulation Time : 720 minutes

 

 

 

 

 

 

Second Way : You can add the extra parameters like the following example

  - First extra parameter: You can set the maximum interval time of customers’ arrival

  - Second extra parameter: You can set the maximum interval time of service for customer

 

  - Third extra parameter: You can set the simulation time

 

 

 

* Notice : If you just only input one or two additional parameters, the parameters are not applied to program. So this program is executed with default values

 

 

 

 

1-2) Execution Result

 

* You can see the following result after execution

 

 

 

 

It shows the number of customers in the line at every time, (This data amount is so large, So you can’t see the all data)

And the ‘in’ and ‘out’ marks mean that customers in and out at the checkout line.

 

 

 

 

 

 

It shows the maximum number of customers in the queue at particular time and longest wait time of particular customer among all customers.

 

 

 

 

 

 

It shows the binary search tree of customers’ names to 5 levels of the name tree from the root.

 

 

 

 * Another Example (Execution command : simulate 4 4 720)

 

 

 

 

2) Implementation

 

 

2-1) Queue

 

 

l  I implemented the Queue structure using double linked list.

The queue in this program consist of queue node structure, some additional variables and some functions(Enqueue, Dequeue and so on).

 

 

 

Implemented Part

Location

Description

Queue Node Structure

20 ~ 25 Line

It is used to save one node in queue

Head and Tail Node

36 Line

It is the head and tail node for double linked list, that is to say, head node means ‘front’ and tail node means ‘rear’ in queue concept.

Variables for queue

37 ~ 40 Line

It is used to solve the problem about queue in spec.

Functions for queue

48 ~ 52 Line

There is functions’ declaration for queue operation

InitQueue()

151~161 Line

Initialize the queue

Enqueue(int value)

164~183 Line

Put data to rear of queue

Dequeue()

186~205 Line

Get data from front of queue

ClearQueue()

208~233 Line

Release all queue data. Namely, Initialize the queue

AddWaitTimeToQueue()

226~236 Line

Add the waiting time at the line per customer (Extra function)

 

 

 

2-2) Binary Search Tree

 

l  The tree in this program consist of tree node structure, some additional variables and some functions(InsertToTree, OutputTree and so on)

 

 

Implemented Part

Location

Description

Tree Node Structure

28 ~ 33 Line

It is used to save one node in tree

Base Node

43 Line

It is the base node of tree

Variables for queue

44 ~ 45 Line

It is used to solve the problem about binary search tree in spec.

Functions for queue

55 ~ 58 Line

There is functions’ declaration for tree operation

InitTree(int initValue)

242~248 Line

Initialize binary search tree

InsertToTree(int value)

251~280 Line

Insert data to proper position of tree

GetNewCustomerNumber()

283~300 Line

Get new customer's name without overlapping (Extra function)

OutputTree(tnode *node, int totalSpace, int depth)

307~326 Line

Output the tree on screen

 

 

 

 

3)Test Cases

 

3-1) What is the maximum number of customers in the queue at any time?

 

* To solve this problem, I makes two additional variables – maxNumber, maxTime

  > maxNumber : this variable always maintain the maximum number of customers in queue

  > maxTime : maxTime save that time when maxNumber variable is updated

* And every time when 1 minute passes, I checked the number of customers in queue. So if the number of customers in current-state queue is larger than maxNumber, change the maxNumber data as number of customers in current-state queue. So the maxNumber always can maintain the maximum number of customers in the queue at particular time

* Please, refer the 101~105 Lines in source code.

 

 

 

 

3-2) What is the longest wait any one customer experiences?

 

* To solve this problem, I save the customer’s waiting time in the each queue node (waitTime) and maxWaitTime.

> maxWaitTime: this variable always maintain the longest wait time of particular customer among all customers.

First, customer comes to the checkout line, Input the customer data to queue, and initialize the customers’ wait time to 0. And Whenever 1 minute passes, add 1 minute to the each customers’ wait time. And if a customer get out from the checkout line (Dequeue operation), Compare the value with maxWaitTime. So if the current customer’s wait time is larger than maxWaitTime, change the maxWaitTime data as the current customer’s wait time.

* Please, refer the 122~128 Lines in source code.

 

 

 

 

3-3) What happens if the arrival interval is changed from 1—4 minutes to 1—3 minutes?

 * These are some examples that the arrival interval is changed to 1-3 minutes

 

 

 

 

* As you can see, If the arrival interval is changed from 1 – 4 minutes to 1 – 3 minutes, Generally, the maximum number of customers and longest wait time is getting lager than data of general case.

 

* The reason: ‘The arrival interval time is getting smaller’ means ‘the many more customers can come to the checkout line’. Because the arrival interval time is small, the queue maybe take more customers. But the service interval time is not decreased. So the same service time is needed as ever.

 

 

 * Result : The number of customers that comes in checkout line is increased and the processing time of service for customers is same. In result the queue is larger and the processing efficiency will be slower.

 

 

 

 

Source & Execution Files Download

 

supermarket_simulation.zip

 

 

 

저작자 표시 비영리 변경 금지
신고

Comment +0

티스토리 툴바