CS2310 Computer Programming
2016/17 Semester A
Department of Computer Science
City University of Hong Kong
Assignment Two
Due Date: 2 Dec 2016 (Friday) 23:00 (firmed, no extension)
All questions should be sent to the TAs of the course. Note that all solutions will be assessed by (1) correctness, (2) programming styles (including comments), and (3) non-redundancy in expressing solutions, if applicable.
This assignment consists of 13 pages, including this cover page. It contains 4 questions named as Q1 to Q4. Q4 has 10% bonus.
Do not INCLUDE any library other than <iostream>, <iomanip>, <cstring>, <fstream>, and/or <cmath> in your solutions. Each solution using any function/facility in other libraries will receive 0 mark. If possible, not using <cstring> in your solution.
Solution Submission Instruction:
• Name your folder as your student number, and create one sub-folder for your solution for each question. Name your solution using the student number followed by the question number. E.g. 5xxxxxxx_Q1.cpp, 5xxxxxxx_Q2.cpp, 5xxxxxxx_Q3.cpp, etc.
• Zip the whole folder into one ZIP file, and name it as your student with a .zip extension.
o For instance, if the student number is 51234567, create a folder 51234567. Create subfolders Q1, Q2, …, Q4 under the folder 51234567. Place the .cpp file of your C++ solution for Q1 under the folder Q1, place the .cpp file of your C++ solution for Q2 under the folder Q2, and so on.
o Zip your folder 51234567 into one and only one ZIP file named as 51234567.zip.
• Submit your ZIP file through Canvas on or before 2 Dec 2016 23:00.
Plagiarism Check:
The course will use multiple code plagiarism detection software to check every solution the whole class submits. These software tools include the following two tools. Students are suggested to keep important immediate versions and paper draft of their solutions in case that students are asked to show evidences of self-effort and originality in developing their solutions of each question. All suspicious cases will be forwarded to the CS Departmental Disciplinary Committee for further actions.
• PASS: https://pass3.cs.cityu.edu.hk/index.jsp and
• MOSS: https://theory.stanford.edu/~aiken/moss .
NEVER place your solution in the common network directory used in the tutorial sessions.
|
Question |
Context |
TA responsible for inquiry |
Eamil Address |
|
Q1 |
Array |
Arif KHAN |
aliakhan2-c@my.cityu.edu.hk |
|
Q2 |
File I/O, String |
Xikang FENG |
xikanfeng2-c@my.cityu.edu.hk |
|
Q3 |
Pointer |
Yuming Lyu |
yueminglv2-c@my.cityu.edu.hk |
|
Q4 |
Class and Object |
Ernest POBEE |
ebpobee2-c@my.cityu.edu.hk |
This assignment is set based on the following mark-grade mapping. If you get A+, it means that you have exceeded the level required by the course. On the other hands, if you get D or F, you should develop better programming skills.
|
Marks |
Grade by Intuition |
|
x >= 80 |
A+ |
|
70 <= x < 80 |
A |
|
55 <= x < 70 |
B |
|
40 <= x < 55 |
C |
|
30 <= x < 40 |
D |
|
Less than 30 |
F |
Q1. Sum Matrix Game [20%]
Sum Matrix is a number placement game. In this game, an n x n matrix is filled with numbers such that (1) the sum of the numbers in every row or every column is all same, and (2) all the numbers from 1 to n*n should be placed in the matrix. The program should develop the matrix based on the following given rules.
1. The program should ensure the input value n as an odd number in the range of 1 to 11. Otherwise, the program should display the following message and terminate: Please enter an odd positive number in the range of [1-11]. Bye.
2. The possible range of values in each cell of the matrix should be a product of the input odd number.
• E.g., For sum matrix of order 3*3, the cell values should be in the range of (1-9)
• E.g., For sum matrix of order 5*5, the cell values should be in the range of (1-25)
3. In the output, set the width of each column of the matrix to 4 characters and there is one space to separate two columns.
4. Note that the cells in your matrix may have different values. (There are multiple solutions, and you only need to generate one possible solution.)
5. Hint: observe the patterns of the numbers illustrated in each matrix and figure out the placement rule yourself.
Example 1
|
Enter an odd number (n) for (n*n) matrix [Max Matrix Size: 11*11] 2
Please enter an odd positive number in the range of [1-11]. Bye. |
Example 2
|
Enter an odd number (n) for (n*n) matrix [Max Matrix Size: 11*11] 3
The Sum Matrix for 3 * 3 Order is
8 1 6 ——-> 15 3 5 7 ——-> 15 4 9 2 ——-> 15 —- —- —- 15 15 15 |
Example 3
|
Enter an odd number (n) for (n*n) matrix [Max Matrix Size: 11*11] 5
The Sum Matrix for 5 * 5 Order is
17 24 1 8 15 ——-> 65 23 5 7 14 16 ——-> 65 4 6 13 20 22 ——-> 65 10 12 19 21 3 ——-> 65 11 18 25 2 9 ——-> 65 —- —- —- —- —- 65 65 65 65 65 |
Example 4
|
Enter an odd number (n) for (n*n) matrix [Max Matrix Size: 11*11] 7
The Sum Matrix for 7 * 7 Order is
30 39 48 1 10 19 28 ——-> 175 38 47 7 9 18 27 29 ——-> 175 46 6 8 17 26 35 37 ——-> 175 5 14 16 25 34 36 45 ——-> 175 13 15 24 33 42 44 4 ——-> 175 21 23 32 41 43 3 12 ——-> 175 22 31 40 49 2 11 20 ——-> 175 —- —- —- —- —- —- —- 175 175 175 175 175 175 175 |
Example 5
|
Enter an odd number (n) for (n*n) matrix [Max Matrix Size: 11*11] 9
The Sum Matrix for 9 * 9 Order is
47 58 69 80 1 12 23 34 45 ——-> 369 57 68 79 9 11 22 33 44 46 ——-> 369 67 78 8 10 21 32 43 54 56 ——-> 369 77 7 18 20 31 42 53 55 66 ——-> 369 6 17 19 30 41 52 63 65 76 ——-> 369 16 27 29 40 51 62 64 75 5 ——-> 369 26 28 39 50 61 72 74 4 15 ——-> 369 36 38 49 60 71 73 3 14 25 ——-> 369 37 48 59 70 81 2 13 24 35 ——-> 369 —- —- —- —- —- —- —- —- —- 369 369 369 369 369 369 369 369 369 |
Example 6
|
Enter an odd number (n) for (n*n) matrix [Max Matrix Size: 11*11] 11
The Sum Matrix for 11 * 11 Order is
68 81 94 107 120 1 14 27 40 53 66 ——-> 671 80 93 106 119 11 13 26 39 52 65 67 ——-> 671 92 105 118 10 12 25 38 51 64 77 79 ——-> 671 104 117 9 22 24 37 50 63 76 78 91 ——-> 671 116 8 21 23 36 49 62 75 88 90 103 ——-> 671 7 20 33 35 48 61 74 87 89 102 115 ——-> 671 19 32 34 47 60 73 86 99 101 114 6 ——-> 671 31 44 46 59 72 85 98 100 113 5 18 ——-> 671 43 45 58 71 84 97 110 112 4 17 30 ——-> 671 55 57 70 83 96 109 111 3 16 29 42 ——-> 671 56 69 82 95 108 121 2 15 28 41 54 ——-> 671 —- —- —- —- —- —- —- —- —- —- —- 671 671 671 671 671 671 671 671 671 671 671 |
Q2. Document Correction and Alignment Problem [30%]
Nowadays, speech recognition technology is becoming more and more mature. Recently the Smartisan company released their latest smart phone, Smartisan M1. The most eye-catching part of their release conference is not their new smart phone, but rather, a speech recognition input method ¾ Xunfei input method.
Now suppose we have a document, the content of which is generated by a speech recognition input method. Due to the error of the speech recognition input method, some continuously duplicated words appear in the content. Also, the format of the content is messy because of different length of each line (see the content of D1.txt in Example 1).
You are required to write a program to remove the word duplication and align the content based on the following instructions:
1) Your program can assume that every word in the input document consist of at most 20 characters, the input document may be jammed with empty line, but the whole input document represents one single paragraph with at most 1000 words. Similarly, your output document should contain one paragraph with at most 1000 words.
2) Your program can only consider the duplication for a single word, like “The the the world”. The duplication for multiple words, like “The world the world”, will not appear in the given document. That is, if there is a consecutive sequence of same word, then it is a duplication of that single word.
3) Your program can assume that the following characters consider as punctuations in an English sentence: comma and full stop. All other characters are treated as a part of a word. In Example 2 on next page, “(Friday)” is a word. In this case, “(Friday) Friday” has no word duplication.
4) The number of the duplication is indefinite.
5) Each duplication of a single word should be replaced by that single occurrence of the word after your correction. For example, “The the the world” should become “The world” after your correction.
6) After the alignment, each line should contain exactly 60 characters (contain the space and punctuations), with the exception of the last line.
7) Your program can align the content by adjusting the number of words per line and the space between the words. The space number between the words should be determined by the total space number and the total words number in this line. The target is to make the space to distribute evenly. There is no space between words and punctuations.
a) E.g., if a line can contain 4 words and 3 spaces, then the amounts of space characters in between two consecutive words on this line should be 1, 1, and 1.
b) E.g., if one line can contain 4 words and 5 spaces, then the amounts of space characters in between two consecutive words should be 2, 2, 1.
8) After the alignment, each line should start with a word and also end with a word or a punctuation.
9) No word can be split during the alignment process.
10) The result is required to be stored in a text file named as output.txt.
Example 1:
Input document D1.txt:
|
The the the town revolved around the river river. In summer, when the blazing sun sun sun sun beat beat down, it dozed under the weight of of sultry days. On Main Street a sow and her litter litter litter of pigs might root along the wooden side walks, sharing the deeply deeply rutted rutted roadway with foraging hens and and and and a hound languidly scratching his fleas fleas. |
Output Content of Output.txt is as follows
|
The town revolved around the river. In summer, when the blazing sun beat down, it dozed under the weight of sultry days. On Main Street a sow and her litter of pigs might root along the wooden side walks, sharing the deeply rutted roadway with foraging hens and a hound languidly scratching his fleas. |
Example 2:
Input document:
|
CS2310 Computer Programming 2016/17 Semester A Department of Computer Science City University of Hong Kong Assignment Two Due Date: 2 Dec 2016 (Friday) 23:00 (firmed, no extension)
All questions should be sent to the TAs of the course. Note that all solutions will be assessed by (1) correctness, (2) programming styles (including comments), and (3) non-redundancy in expressing solutions, if applicable.
This assignment consists of 13 pages, including this cover page. It contains 4 questions named as Q1 to Q4. |
Output: Content of Output.txt is as follows
|
CS2310 Computer Programming 2016/17 Semester A Department of Computer Science City University of Hong Kong Assignment Two Due Date: 2 Dec 2016 (Friday) 23:00 (firmed, no extension) All questions should be sent to the TAs of the course. Note that all solutions will be assessed by (1) correctness, (2) programming styles (including comments), and (3) non-redundancy in expressing solutions, if applicable. This assignment consists of 13 pages, including this cover page. It contains 4 questions named as Q1 to Q4. |
Q3. Pointer and Dynamic Array [25%]
The code on the next page is an executable solution for Exercise 5 of Tutorial 7 on Array.
Your task is to (1) rewrite the program to perform the same computation that meets the following requirements. Note that you can use your own array-version programs as long as your program meets the following requirements.
• Every array in the program is a dynamic array.
• Except the statement in which it uses of the “new” operator (e.g., int* faces = new int[12];), there is no any use of any array construct in the program. (hint: Use Pointers!)
o For example, the current usage of arrays like those listed are disallowed to be used in your program.
▪ sum[i + j – 1]
▪ sum[k]
▪ sum[index]
▪ sorted[index][0]
▪ sorted[index][1]
▪ sorted[k][0]
▪ sorted[k – 1][0]
▪ sorted[k][1]
▪ sorted[k – 1][1]
▪ sorted[i][0]
▪ sorted[i-1][0]
▪ faces[sorted[0][1] – 1]
▪ faces[sorted[i][1] – 1]
▪ faces[k]
• Every dynamic array must be deleted before the program terminates.
o Hint: when deleting the 1D array faces, use delete: delete[] faces;
o Hint: when deleting a 2D array, you need to delete all the rows of the 2D array first, and then the 2D array.
o Hint: Study Exercise 12 of Tutorial 9 on Pointers
•
|
#include <iostream> using namespace std;
int main() { char faces[12] = { 0 }; int sum[12] = { 0 }; // max 12 values of occurrence counts int sorted[12][2]; // a 2D array // sorted[i][0] = sum of face values kept in sum[index] // sorted[i][1] = index of sum[index]
for (int i = 1; i <= 6; i++) // i is dice 1 for (int j = 1; j <= 6; j++) // j is dice 2 sum[i + j – 1] = sum[i + j – 1] + 1;
for (int k = 0; k < 12; k++) if (sum[k] != 0) cout << sum[k] << ” occurrence(s) of the sum “ << k + 1 << endl;
// we firstly copy sum to rank for (int index = 0; index < 12; index++) { sorted[index][0] = sum[index]; sorted[index][1] = index + 1; }
// then we sort the array sorted[] using bubble sort // check out the lecture note slide 31 of Lec07 // we want sorted[0] as the LARGEST after the sorting process int tmp; for (int j = 0; j < 12 – 1; j++) // outer loop for (int k = 12 – 1; k > j; k–) // bubbling if (sorted[k][0] > sorted[k – 1][0]) { // check against col 0 // note that the condition is “>” rather than “<“. tmp = sorted[k][0]; // swap neighbors for col 0 sorted[k][0] = sorted[k – 1][0]; sorted[k – 1][0] = tmp; tmp = sorted[k][1]; // swap neighbors for col 1 sorted[k][1] = sorted[k – 1][1]; sorted[k – 1][1] = tmp; } for (int i = 0; i < 12; i++) if (sorted[i][0] != 0) cout << sorted[i][0] << ‘ ‘ << sorted[i][1] << endl;
char c = ‘A’; // the 1st character to be shown faces[sorted[0][1] – 1] = c; for (int i = 1; i < 12; i++) { if (sorted[i][0] != sorted[i – 1][0]) c++; if (sorted[i][0] != 0) faces[sorted[i][1] – 1] = c; }
// print out the letter rank for (int k = 0; k < 12; k++) if (faces[k] != 0) cout << faces[k] << ” occurrence(s) of the sum ” << k + 1 << endl; return 0; } |
Example:
|
1 occurrence(s) of the sum 2 2 occurrence(s) of the sum 3 3 occurrence(s) of the sum 4 4 occurrence(s) of the sum 5 5 occurrence(s) of the sum 6 6 occurrence(s) of the sum 7 5 occurrence(s) of the sum 8 4 occurrence(s) of the sum 9 3 occurrence(s) of the sum 10 2 occurrence(s) of the sum 11 1 occurrence(s) of the sum 12 6 7 5 6 5 8 4 5 4 9 3 4 3 10 2 3 2 11 1 2 1 12 F occurrence(s) of the sum 2 E occurrence(s) of the sum 3 D occurrence(s) of the sum 4 C occurrence(s) of the sum 5 B occurrence(s) of the sum 6 A occurrence(s) of the sum 7 B occurrence(s) of the sum 8 C occurrence(s) of the sum 9 D occurrence(s) of the sum 10 E occurrence(s) of the sum 11 F occurrence(s) of the sum 12 |
Q4. Ash and Pikachu [25% + 10% Bonus]
In the Pokemon series of manga, Ash is the main character who joins force with Pikachu, a Pokémon, for various adventure. Recently, we have the Pokemon Go. In this question, we are going to implement some involved concepts through C++ classes.
In this question, your program should allow a user to input a Pokemon world, a list of Pokemon, as well as the information about a trainer called Ash. Ensure to format the output so that the schedules are presented nicely.
Important note: Your program can assume the following: (1) the number of Pokemon is at least 1 and at most 1000, (2) the name of any object is a cstring consisting of at most 10 characters (including ‘\0’), and (3) all user inputs are valid.
• The concept of PokemonWorld is implemented as a C++ class.
o Each PokemonWorld object owns two PokemonStation objects. We simply refer to each PokemonStation object of this class as a station.
o Each PokemonWorld object is responsible to initialize the two stations.
▪ (Note: The use of an array to keep two stations will make your program significantly more complex than keeping them as two separate variables. The reason is due to our limited known-how introduced in CS2310 to use object pointers rather than the limitation of C++.)
o When a Pokemon enters a PokemonWorld, the PokemonWorld is responsible to assign this Pokemon to one of the two stations its owned. The rule is that if this Pokemon is assigned to the first station, then the next Pokemon will be assigned to the second station; on the other hand, if the current Pokemon is assigned to the second station, then the next one will be assigned to the first station, and so on; i.e., the assignment is done in a round-robin manner.
o The name of the PokemonWorld object can only be accessed by the object itself.
o Hint: study http://stackoverflow.com/questions/12927169/how-can-i-initialize-c-object-member-variables-in-the-constructor
• The concept of PokemonStation is implemented as a C++ class.
o Each object of this class represents a station which has a station identifier. We simply refer to each object of this class as a station. The station identifiers are 1 and 2, respectively.
o The identifier of each station is provided by the PokemonWorld object that owns the station through the class constructor of PokemonStation. (Hint: You may wish to initialize each station when the constructor of PokemonWorld object is being called.)
o Each station maintains its own list of Pokemon assigned by the PokemonWorld object.
o Both the identifier, the list of Pokemon (and include each Pokemon in it) of each station should not be accessed by another other object nor be returned via a function.
o Only PokemonWorld and the station itself can invoke the function of that station.
• The concept of Pokemon is implemented as a C++ class.
o Each Pokemon is an object of this class.
o Each Pokemon object has its own name (a cstring) and hp value (an integer).
o All data members (name, hp) of each Pokemon object once initialized can only be accessed by that Pokemon object.
• The main() function is responsible for the following:
o To accept all the inputs from the user.
o To create a PokemonWorld and all Pokemon.
o To set each Pokemon to enter the PokemonWorld.
o To call the method print() of Pokemon, which in turn calls the method print() of each PokemonStation, which in turn calls the method print() of each Pokemon to print out the information of the PokemonWorld, the PokemonStation, and the Pokemon, respectively.
More description about the above three classes
|
|
|
||||||||||||||||||||
Bonus Part [Extra 10%]
• Meet all of the requirements above.
• A Trainer is implemented as a C++ class.
o Each trainer is an object of this class.
o Each trainer has his/her own name (cstring), identifier (integer), and strength (integer). All these information are inputted from user.
o All data members of each trainer object cannot be accessed outside the trainer object. That is, the value of each data member should not be returned via a function nor be retrieved via call-by-reference.
• The main() function is responsible to create a trainer called Ash and let Ash enter the PokemonWorld.
• PokemonWorld is responsible to guide Ash to visit its two stations one by one once Ash enters this world.
• Each station is responsible to determine whether a trainer can capture each Pokemon kept by the station. Specifically, if the hp of the Pokemon is strictly less than the strength of the trainer, then the Pokemon is marked as captured by the trainer.
o Note that following the above requirements, both the hp of the Pokemon and the strength of the trainer should not be returned via any function.
• The print() method of each captured Pokemon calls the print() method of the trainer object that captures it to print the information of that trainer.
Example 1: (without Bonus)
|
What is the World Name? Macau Please input the number of Pokemon in the Macau world 7 Please input the characteristics of all Pokemon: Name HP Pikachu 50 Regice 100 Articuno 100 Charizard 150 Blastoise 240 Mew 340 Gengar 101
World is Macau Pokemon in Station #1: Pikachu HP 50 Articuno HP 100 Blastoise HP 240 Gengar HP 101 Pokemon in Station #2: Regice HP 100 Charizard HP 150 Mew HP 340 |
Example 2: (without Bonus)
|
What is the World Name? Hongkong Please input the number of Pokemon in the Hongkong world 1 Please input the characteristics of all Pokemon: Name HP Pikachu 50
World is Hongkong Pokemon in Station #1: Pikachu HP 50 No Pokemon in Station #2 |
Example 3: (with Bonus)
|
What is the World Name? Macau Please input the number of Pokemon in the Macau world 7 Please input the characteristics of all Pokemon: Name HP Pikachu 50 Regice 100 Articuno 100 Charizard 150 Blastoise 240 Mew 340 Gengar 101
Enter Trainer information: ID NAME HP 1 Ash 101
World is Macau Pokemon in Station #1: Pikachu HP 50 Ash is its master Articuno HP 100 Ash is its master Blastoise HP 240 Gengar HP 101 Pokemon in Station #2: Regice HP 100 Ash is its master Charizard HP 150 Mew HP 340 |