C++代写：COMP2011 Social Distancing Under Covid 19|留学生CS代写|代做Java编程|C作业|C++程序|Python代码

使用Covid 19的数据，练习位运算的用法。

IMPORTANT NOTES

There are a few things you CANNOT do. Failure to observe these rules would potentially result in ZERO mark for your assignment.

You cannot define and use any arrays.
You cannot define and use any additional global variables.
You cannot change any function headers already included in the skeleton code.
You cannot include or use any additional libraries (e.g., string)

This programming assignment is challenging, so you are highly recommended to start early. If you need clarification on the requirements, please feel free to post on the Piazza. However, to avoid cluttering the forum with repeated/trivial questions, please carefully read all the given code, webpage description, sample output, and latest FAQ (refresh this page regularly) carefully before you post your questions. Also please be reminded that we won’t debug for any student’s assignment for the sake of fairness.

Introduction

Under the COVID-19 pandemic, we all need to protect ourselves and work together to fight the virus. There are many measures we should take, such as wearing a mask and practicing hand hygiene. And one of the most important measures is to keep Social Distancing. The social distancing measure requires us to keep maximum distance from others in the public space as far as we can, so as to minimize the risk of COVID-19 spreading in the community.

Now, imagine that you are volunteering at your local community, and you are assigned to manage a row of seats in a public area. Your job will be to arrange seats for people according to the social distancing rule. Since you have learned programming with C++ in COMP2011, you want to design a simple Seat Management Program to help you better do this job.

Sounds interesting? Let’s get started now!

Preliminaries

In this programming assignment, we hope that you can make full use of knowledges you have learned so far in the COMP2011 class, like the Control Statement, Loop Statement and Function. Beyond that, you will learn basic usage of Bitwise Operators in C++ to manipulate Binary Numbers to complete this assignment.

NOTE: In this assignment, we consider only binary numbers and bitwise operators for unsigned integers.

Binary Numbers

The integers we used in our daily lives, such as “Year 2021” and “iPhone 12”, are mostly expressed in decimals. In the decimal, each digit in a number takes on one of ten possible values, called “digits”, from 00 to 99, and each position to the left of the decimal indicates an increased positive power of 1010. Alternatively, integers can also be expressed in the binaries. The Binary Numbering System is the most fundamental numbering system in all electronic and computer based systems. It follows the same set of rules as the decimal numbering system except for using powers of 2 instead of 10.

Bitwise Operators in C++

Every programmer knows that computers can only process information represented by a series of binary digits (bits, 11 and 00). This means when we store the decimal number 20212021 in memory of the computer, it actually stores a sequence of bits represented as 1111110010111111100101. In C++ we have a special set of operators to efficiently deal with the binary representation of a number, that is AND (&), OR (|), XOR (^), NOT (~), BIT SHIFT LEFT (<<), and BIT SHIFT RIGHT (>>).

The & (bitwise AND) in C++ takes two numbers as operands and does AND on every bit of two numbers. The result of AND is 1 only if both bits are 1. Otherwise, it returns 0.
The | (bitwise OR) in C++ takes two numbers as operands and does OR on every bit of two numbers. The result of OR is 1 if at least one of the two bits is 1. Otherwise, it returns 0.
The ^ (bitwise XOR) in C++ takes two numbers as operands and does XOR on every bit of two numbers. The result of XOR is 1 if the two bits are different. Otherwise, it returns 0.
The ~ (bitwise NOT) in C++ takes one number and inverts all bits of it.
The << (left shift) in C++ takes two numbers, left shifts the bits of the first operand, the second operand decides the number of places to shift. When we shift any number to the left, the left-most bits are discarded, while the right-most bits are replaced by zeroes.

The >> (right shift) in C++ takes two numbers, right shifts the bits of the first operand, the second operand decides the number of places to shift. When we shift any number to the right, the right-most bits are discarded, while the left-most bits are replaced by zeroes.
You can run the following example code to see how the bitwise operators take effect.

#include <iostream>
using namespace std;

int main()
{
  // 12 = 0000 0000 0000 1100 (in binary)
  // 25 = 0000 0000 0001 1001 (in binary)
  unsigned short a = 12, b = 25;
  unsigned short r1, r2, r3, r4, r5, r6;

  cout << "a = " << a << endl;
  cout << "b = " << b << endl;

  // 0000 0000 0000 1100 & 0000 0000 0001 1001 = 0000 0000 0000 1000 = 8 (in decimal)
  r1 = a & b;
  cout << "a & b = " << r1 << endl;

  // 0000 0000 0000 1100 | 0000 0000 0001 1001 = 0000 0000 0001 1101 = 29 (in decimal)
  r2 = a | b;
  cout << "a | b = " << r2 << endl;

  // 0000 0000 0000 1100 ^ 0000 0000 0001 1001 = 0000 0000 0001 0101 = 21 (in decimal)
  r3 = a ^ b;
  cout << "a ^ b = " << r3 << endl;

  // ~ 0000 0000 0000 1100 = 1111 1111 1111 0011 = 65523 (in decimal)
  r4 = ~a;
  cout << "~ a = " << r4 << endl;

  // 0000 0000 0001 1001 >> 1 = 0000 0000 0000 1100 = 12 (in decimal)
  r5 = b >> 1;
  cout << "b >> 1 = " << r5 << endl;

  // 0000 0000 0001 1001 << 1 = 0000 0000 0011 0010 = 50 (in decimal)
  r6 = b << 1;
  cout << "b << 1 = " << r6 << endl;
 
  return 0;
  }

Important Notes:

Please don’t mix up bitwise operators &, | and logical operators &&, ||.
Bitwise operators can only be used alongside char, short, int, long, long long and their unsigned variant data types.
The BIT SHIFT LEFT (<<) and the BIT SHIFT RIGHT (>>) operators should not be used for negative numbers, since it results in undefined behavior. Also, if a number is shifted more than the size of it, the behavior is undefined. For the size of different variable types, please refer to lecture notes for details.

Common Usages of Bitwise Operation in C++

Multiplying x by 2 can be done with x << 1
Dividing x by 2 can be done with x >> 1
Getting the k-th bit from the right end of x can be done with x >> (k - 1) & 1
Setting the k-th bit from the right end of x to 1 can be done with x | 1 << (k - 1)
Setting the k-th bit from the right end of x to 0 can be done with x & ~(1 << (k - 1))

Please be careful about the size of variable when you are using x | 1 << (k - 1) and x & ~(1 << (k - 1)). The size of literal constant 1 is actually 32 bits, so if xx is a long long or unsigned long long variable, you should consider using x | (long long)1 << (k - 1) and x & ~((long long)1 << (k - 1)) that cast 1 into 64-bit integer first, such that 1 won’t be shifted more than the size of it (32). You can also use a constant variable in this case. Please see the example as follows.

#include <iostream>
using namespace std;
 
const long long ONE = 1;
 
int main()
{
  int k=4;
 
  // 132 = 10000100 in biranry
  // size of unsigned long long is 64 bits
  unsigned long long x = 132;
  unsigned long long r1, r2, r3, r4, r5;

  cout << "x = " << x << endl;
  cout << "k = " << k << endl;
 
  // Multiply by 2
  // 132 * 2 = 264
  r1 = x << 1;
  cout << "x * 2 = " << r1 << endl;

  // Divide by 2
  // 132 / 2 = 66
  r2 = x >> 1;
  cout << "x / 2 = " << r2 << endl;

  // Get the k-th bit from the right end
  // 0
  r3 = x >> (k - 1) & 1;
  cout << "The k-th bit from the right end of x is " << r3 << endl;

  // Set the k-th bit from the right end to 1
  r4 = x | ONE << (k - 1);
  cout << "The result is " << r4 << endl;

  // Set the k-th bit from the right end to 0
  r5 = x & ~(ONE << (k - 1));
  cout << "The result is " << r5 << endl;

  return 0;
}

Definitions

Seat

In this assignment, you will be given a row of numSeats seats. For the simplicity of the coding, here we use zero-based indexing to represent the seats from left to right. That means the index of the left-most seat will be 00 and the right-most will be numSeats-1. In the example shown in the figure above, numSeats=9 and the seat indices are from 00 to 88.

There will be at least one seat in the row. And we assume the number of seats won’t be larger than a global constant LONGLONG_SIZE.

Seat states and bitmap

Each seat will be either empty or occupied. We use 00 and 11 to represent EMPTY and OCCUPIED, respectively.

So, if we list the states of all seats from left to right, we will get a series of 00 and 11, e.g. 1001010010010100. And it is actually a bitmap representing the states of all seats, with each bit in the bitmap stores the corresponding seat’s state. In this assignment, we use a unsigned long long variable to store this bitmap.

Distance

The distance between two seats is the difference between their indices. For example, the distance between seat ii and jj will be |i-j|ij, where |\cdot| denotes the absolute value.

In this assignment, for each seat we will calculate their distance to their closest occupied seats (referred as minDist). Here we define it as follows:

If the seat is already occupied, its distance to its closest occupied seat is 00.
If the seat is empty:
- If there is no occupied seat on both sides (left and right) of that seat (i.e. all seats are empty), we manually define its minDist equals to numSeats.
- If there is no occupied seat on one side (left/right) of that seat, its minDist is its distance to the closest occupied seat on the other side (right/left).
- If there are occupied seats on both sides (left and right) of that seat, its minDist is its distance to the closest occupied seat on both sides (left and right).
  Please also see the example shown in the figure above.

Seat Assignment

In this assignment, customers may come and take a seat, and those who are seated may also leave. So, you must maintain the state of all seats. Meanwhile, we define the Social Distancing rule as that every time you want to assign a seat to a new customer, you must choose an empty seat such that the distance from that seat to the closest occupied seat is the largest among all empty seats (i.e. the seat with the largest minDist). If there is more than one satisfying seat, then choose one with the least index (the left-most one). In the example shown in the figure above, the seat with the maximum minDist is at 3.

Tasks

Before you start to do the tasks, please carefully read through the Preliminaries and Definitions sections, type the example code in your own code editor or IDE, compile and run the example codes, and make sure you have understood them.

We have provided a skeleton code for you, and you must complete the following tasks based on that skeleton code. You are encouraged to complete those tasks in the given order. And you are encouraged to reuse the functions you have already implemented. You can also write your own helper functions. But please make sure the function you call is bug-free, or you may lose marks in all tasks that call this function.
Two global constants have been defined in the skeleton code for you to use:

1 2	const int LONGLONG_SIZE = 64; const long long ONE = 1;

Task 1

Calculate the bitmap (initialization)

1	int initialize(int numSeats, unsigned long long &bitmap)

Parameters:
- numSeats: total number of seats in the row.
- bitmap: bitmap that represents the states of all seats.
Description:
- If numSeats is not in [1,LONGLONG_SIZE], print “Error: Number of seats out of range.” to the screen (standard output) with an ending endl and return -1.
- Else, read numSeats characters from the standard input. The characters should be either ‘0’ or ‘1’ representing the state of each seats from left to right, e.g. ‘010000100’. You can assume the number of input characters is always correct in this assignment.
- If you read characters other than ‘0’ or ‘1’, print “Error: Illegal state input.” to the screen (standard output) with an ending endl and return -1.
- Calculate and assign right value to bitmap, and return 0
Example
- numSeats=9, standard input=010000100
- After function call, bitmap=010000100 (binary), return 0
Hint
- You can use cin>>c in a loop of numSeats rounds, where c is a char variable, to read the seat states one by one.

Task 2

Query the current state of a seat

1	int getSeatState(int numSeats, unsigned long long bitmap, int seatIndex)

Parameters:
- numSeats: total number of seats in the row.
- bitmap: bitmap that represents the states of all seats.
- seatIndex: index of the target seat.
Description:
- If seatIndex is not in [0,numSeats-1], return -1.
- Else return the state of the seat at seatIndex as 0 or 1.
Example
- numSeats=9, bitmap=010000100 (binary), seatIndex=1 return: 1

Task 3

Print the current state of all seats (bitmap) to screen

1	void printSeats(int numSeats, unsigned long long bitmap)

Parameters:
- numSeats: total number of seats in the row.
- bitmap: bitmap that represents the states of all seats.
Description:
- Print the state of all seats to the screen (standard output), with an ending endl.
Example
- numSeats=9, bitmap=010000100 (binary)
- Print 010000100 to screen with and ending endl.
Hints
- You can call the function getSeatState() you have implemented in Task 2.

Task 4

Change the state of a seat to OCCUPIED

1	int setSeatOccupied(int numSeats, unsigned long long & bitmap, int seatIndex)

Parameters:
- numSeats: total number of seats in the row.
- bitmap: bitmap that represents the states of all seats.
- seatIndex: index of the target seat.
Description:
- If seatIndex is not in [0,numSeats-1], return -1.
- If the seat at seatIndex is already occupied, return -1.
- Else change the state of the seat at seatIndex to 1.
- Calculate and assign new value to bitmap, and return 0
Example
- numSeats=9, bitmap=010000100 (binary), seatIndex=8
- After function call, bitmap=010000101 (binary), return 0

Task 5

Change the state of a seat to EMPTY

1	int setSeatEmpty(int numSeats, unsigned long long & bitmap, int seatIndex)

Parameters:
- numSeats: total number of seats in the row.
- bitmap: bitmap that represents the states of all seats.
- seatIndex: index of the target seat.
Description:
- If seatIndex is not in [0,numSeats-1], return -1.
- If the seat at seatIndex is already empty, return -1.
- Else change the state of the seat at seatIndex to 0.
- Calculate and assign new value to bitmap, and return 0
Example
- numSeats=9, bitmap=010000100 (binary), seatIndex=6
- After function call, bitmap=010000000 (binary), return 0

Task 6

Calculate the distance from a seat to its closest occupied seat (minDist)

1	int getSeatDistance(int numSeats, unsigned long long bitmap, int seatIndex)

Parameters:
- numSeats: total number of seats in the row.
- bitmap: bitmap that represents the states of all seats.
- seatIndex: index of the target seat.
Description:
- If seatIndex is not in [0,numSeats-1], return -1.
- Else calculate and return the distance to its closest occupied seats minDist from the seat at seatIndex. Please refer to section 3.4 for details.
Example
- numSeats=9, bitmap=010000100 (binary), seatIndex=8
- return: 2

Task 7

Find an empty seat with maximum minDist

1	int findSeat(int numSeats, unsigned long long bitmap)

Parameters:
- numSeats: total number of seats in the row.
- bitmap: bitmap that represents the states of all seats.
Description:
- If all seats are occupied, return -1.
- Else return the index of the seat with maximum minDist.
Example
- numSeats=9, bitmap=010000100 (binary)
- return: 3