代写ENGG1340代写编程、C++设计程序调试、c++编程代做

日期：2021-03-23 11:39

ENGG1340 / COMP2113, Assignment 2

Due Date: Apr 1, 2021 23:59

If you have any questions, please post to the Moodle discussion forum on Assignment 1.

General Instructions

Problem 1: (C++) Pokémon in Order (20 marks)

Problem 2: (C++) Sudoku (25 marks)

Problem 3: (C++) Word Mask (25 marks)

Problem 4: (C) Luhn algorithm (25 marks)

Total marks: 100 marks

5 marks for proper code comments, indentation and use of functions

95 marks for program correctness

A maximum of 5 marks will be deducted if you fail to follow the submission instructions strictly.

General Instructions

Read the instructions in this document carefully.

In this assignment you will solve 4 problems and a tester would automatically test your submitted program. So if your

submitted files and program outputs do not conform to our instructions given here, your programs cannot be evaluated and

you will risk losing marks totally.

Sample test cases are provided with each problem in this document. Note that the test cases may or may not cover all

boundary cases for the problem. It is also part of the assessment whether you are able to design proper test cases to verify

the correctness of your program. We will also use additional test cases when marking your submission.

Input and output format

Note carefully whether your C/C++ programs should read from the standard input, command line input or file input. Also,

unless specified otherwise, your answer should be printed through the standard output. If you failed to follow the

instructions, the tester may not be able to give a score for your program. Additionally, you should strictly follow the sample

output format (including space, line breaker, etc.), otherwise, your answer might be considered as wrong.

How to use the sample test cases

Sample test cases in text file formats are made available for you to check against your work to avoid formatting errors which

might fail the tester. Here's how you may use the sample test cases. Take Problem 2 test case 3 as an example. The sample

input and the expected output are given in the files input2_3.txt and output2_3.txt , respectively. Suppose that your

program is named "2", do the followings at the command prompt of the terminal to check if there is any difference between

your output and the expected output.

./2 < input2_3.txt > myoutput.txt

diff myoutput.txt output2_3.txt

Testing against the sample test cases is important to avoid making formatting mistakes. The additional test cases for

grading your work will be of the same formats as the sample test cases.

Coding environment

You must make sure that your program can compile, execute and generate the required outputs on our standard environment,

namely, the gcc C/C++11 environment we have on the CS Linux servers (academy*).

For Problems 1, 2 and 3 on C++ programming, make sure the following compilation command is used to compile your

programs:

g++ -pedantic-errors -std=c++11 [yourprogram].cpp

For Problem 4 on C programming, make sure the following compilation command is used to compile your program:

gcc -pedantic-errors -std=c11 4.c

As a programmer/developer, you should always ensure that your code can work perfectly as expected on a target (e.g., your

client's) environment, not only on yours.

While you may develop your work on your own environment, you should always try your program (compile & execute & check

results) on our standard environment before submission.

Submission

Name your C/C++ programs as in the following table and put them together into one directory. Make sure that the folder

contains only these source files ( *.cpp / *.c ) and no other files. Compress this directory as a [uid].zip file where [uid]

is your university number and check carefully that the correct zip file have been submitted. We suggest you to download

your submitted file from Moodle, extract them, and check for correctness. You will risk receiving 0 marks for this

assignment if you submit incorrect files. Resubmission after the deadline is not allowed.

Problem Code templates provided Files to Submit

1 - 1.cpp

2 2.cpp 2.cpp

3 3.cpp 3.cpp

4 - 4.c

Late submission

If submit within 3 days after the deadline, 50% deduction. After that, no mark.

Evaluation

Your code will be auto-graded for technical correctness. In principle, we use test cases to benchmark your solution, and you

may get zero marks for not being able to pass any of the test cases. Normally partial credits will not be given for incomplete

solution, as in many cases the logic of the programs are not complete and an objective assessment could be difficult.

However, your work may still be considered on a case-by-case basis during the rebuttal stage.

Academic dishonesty

We will be checking your code against other submissions in the class and from the Internet for logical redundancy. Please be

reminded that no matter whether it is providing your work to others, assisting others to copy, or copying others will all be

considered as committing plagiarism and we will follow the departmental policy to handle such cases. Please refer to the

course information notes for details.

Getting help

You are not alone! If you find yourself stuck on something, post your question to the course forum. We want this assignment

to be rewarding and instructional, not frustrating and demoralizing. But we don’t know when or how to help unless you ask.

Please be careful not to post spoilers. Please don’t post any code that is directly related to the assignments to the

discussion forums or share your work to any public domain. However you are welcome and encouraged to discuss general

ideas on the discussion forums.

Problem 1: (C++) Pokémon in Order

Write a C++ program which reads in some Pokémon names from user input and outputs them in a way as described below.

Input:

Each line contains a single word which is the name of a Pokémon.

Last line is always "???" indicating end of input.

You may assume the number of input names are no more than 30.

Output:

Names of the input Pokémon, one on each line, in the following order:

In descending order of length of Pokémon name.

If two Pokémon names are of the same length, then the two names will be printed in lexicographical order (case

insensitive).

Requirement:

Your program MUST implement the selection sort algorithm you learned in Module 6. You will need to adapt the sorting

algorithm to satisfy the output requirement. In other words, you are not allowed to use external libraries to handle the

sorting.

You can ONLY use the data types char , bool , int , double , strings and arrays.

You are NOT allowed to use data structures from other external libraries such as STL containers (e.g., vectors), etc.

Sample Test Cases

User inputs are shown in blue.

Problem 2: Sudoku

Sudoku is a puzzle game whose goal is to enter the digits 1 to 9 into a game board with 9 x 9 cells, such that:

Each digit appears exactly once in each row

Each digit appears exactly once in each column

Each digit appears exactly once in each of the nine 3 x 3 sub-grid.

An example game solution is shown below.

Given an incomplete game board, we may determine the allowed digits for an empty cell, which are the digits that can be

entered into the cell without violating the above rules for the game board. For example, in the following game board, the

allowed digits for cell at position (6, 2) are 3, 5, 6 and 7.

A very basic Sudoku solving technique, named Naked Single, is to determine the allowed digits of an empty cell and if the

empty cell has only one allowed digits, we fill the empty cell with this allowed digit. In the above game board, the cell at

position (4, 5) can be filled with the digit 5.

We may then apply the Naked Single technique to the empty cells to solve a Sudoku game as much as possible. Note that

Once an empty cell is filled, the allowed digits for other empty cells may change so we will need to redetermine them.

We can apply the Naked Single technique to the empty cells repeatedly, until we find that no empty cells can be filled

after visiting all empty cells once.

For some very simple Sudoku game board, all empty cells can be solved eventually by using the Naked Single technique

alone, but in general we may still end up with an incomplete board.

Write a C++ program that uses the Naked Single technique alone to solve a Sudoku game as much as possible as described

above.

You are provided with a template program 2.cpp .

Input:

Nine lines, each containing nine digits from 0 to 9, representing a Sudoku game board.

A digit 0 represents an empty cell, while any digit from 1 to 9 represent a filled cell.

You may assume that the input board is always consistent, which means that there must be at least one allowed digit for

an empty cell at any time during the solving process.

Output:

Your program should first display the given game board in the format as specified in the sample test cases, in which an

empty cell is printed as x , and we have grid lines to better visualize the sub-grids.

Your program should then display the final game board (which may be complete or incomplete) obtained by repeatedly

applying the Naked Single technique ONLY until no more empty cells can be filled.

Requirement:

You should start working from the 2.cpp provided.

The main() function has been written for you. A 2D array is also defined in main() for storing the game board. You do

not need to change anything in the main() function.

Complete the following functions in 2.cpp . Read the code in the template carefully to see what have been provided for

you. You will find details of the function prototypes in the in-code comments too.

ReadBoard() which reads a Sudoku board from input

PrintBoard() which displays a given Sudoku board to screen

SolveBoard() which solves a given Sudoku board as much as possible using the Naked Single technique only.

You can ONLY use the simple data types char , bool , int , double , strings and arrays. In other words, you are not

allowed to use other data types or data structures STL containers (e.g., vectors), etc.

You may add your own functions wherever appropriate for better program modularity.

Sample Test Cases

User inputs are shown in blue.

2_1:

3 9 0 7 8 0 0 0 0

0 0 4 9 0 6 8 0 7

0 0 0 0 0 3 0 6 0

0 0 8 2 4 0 0 0 0

7 3 1 0 0 0 6 2 4

0 0 0 0 6 7 9 0 0

0 1 0 4 0 0 0 0 0

2 0 9 6 0 8 3 0 0

0 0 0 0 1 9 0 4 8

Input Sudoku board:

3 9 x | 7 8 x | x x x

x x 4 | 9 x 6 | 8 x 7

x x x | x x 3 | x 6 x

------+-------+-------

x x 8 | 2 4 x | x x x

7 3 1 | x x x | 6 2 4

x x x | x 6 7 | 9 x x

------+-------+-------

x 1 x | 4 x x | x x x

2 x 9 | 6 x 8 | 3 x x

x x x | x 1 9 | x 4 8

Final Sudoku board:

3 9 6 | 7 8 4 | 1 5 2

1 2 4 | 9 5 6 | 8 3 7

5 8 7 | 1 2 3 | 4 6 9

------+-------+-------

9 6 8 | 2 4 1 | 5 7 3

7 3 1 | 8 9 5 | 6 2 4

4 5 2 | 3 6 7 | 9 8 1

------+-------+-------

8 1 5 | 4 3 2 | 7 9 6

2 4 9 | 6 7 8 | 3 1 5

6 7 3 | 5 1 9 | 2 4 8

2_2:

4 0 9 0 0 0 0 0 0

0 2 0 4 0 0 0 0 6

6 0 0 2 3 0 1 0 0

5 9 0 3 0 0 0 7 0

0 0 0 0 4 0 0 5 0

0 8 0 0 0 2 0 9 1

0 0 1 0 2 4 0 0 8

7 0 0 0 0 8 0 4 0

0 0 0 0 0 0 7 0 5

Input Sudoku board:

4 x 9 | x x x | x x x

x 2 x | 4 x x | x x 6

6 x x | 2 3 x | 1 x x

------+-------+-------

5 9 x | 3 x x | x 7 x

x x x | x 4 x | x 5 x

x 8 x | x x 2 | x 9 1

------+-------+-------

x x 1 | x 2 4 | x x 8

7 x x | x x 8 | x 4 x

x x x | x x x | 7 x 5

Final Sudoku board:

4 3 9 | x x x | 5 2 7

1 2 8 | 4 x x | 9 3 6

6 7 5 | 2 3 9 | 1 8 4

------+-------+-------

5 9 x | 3 x x | x 7 2

2 1 x | x 4 x | x 5 3

3 8 x | x x 2 | x 9 1

------+-------+-------

9 5 1 | 7 2 4 | 3 6 8

7 6 3 | x x 8 | 2 4 9

8 4 2 | x x x | 7 1 5

2_3:

7 0 9 0 0 0 3 0 6

0 8 0 0 3 0 0 5 0

0 0 0 0 0 2 0 0 0

5 0 0 0 0 0 8 0 0

0 2 0 0 6 0 0 3 0

0 0 1 0 0 0 0 0 7

0 0 0 4 0 0 0 0 0

0 5 0 0 1 0 0 6 0

9 0 7 0 0 0 4 0 5

Input Sudoku board:

7 x 9 | x x x | 3 x 6

x 8 x | x 3 x | x 5 x

x x x | x x 2 | x x x

------+-------+-------

5 x x | x x x | 8 x x

x 2 x | x 6 x | x 3 x

x x 1 | x x x | x x 7

------+-------+-------

x x x | 4 x x | x x x

x 5 x | x 1 x | x 6 x

9 x 7 | x x x | 4 x 5

Final Sudoku board:

7 x 9 | x x x | 3 x 6

x 8 x | x 3 x | x 5 x

x x x | x x 2 | x x x

------+-------+-------

5 x x | x x x | 8 x x

x 2 x | x 6 x | x 3 x

x x 1 | x x x | x x 7

------+-------+-------

x x x | 4 x x | x x x

x 5 x | x 1 x | x 6 x

9 x 7 | x x x | 4 x 5

Problem 3: (C++) Word Mask

Write a C++ program that masks a word in multiple files. To mask a word in a line of text, we replace the word by a special

symbol * . For example, given a line of text:

The Theory of Everything is a film about the life of the theoretical physicist Stephen Hawking.

Masking the word the will result in the line:

The Theory of Everything is a film about *** life of *** theoretical physicist Stephen Hawking.

Note that the masking is case sensitive, and the length of the mask equals the length of the word that is being masked.

You are provided with a template program 3.cpp .

Input:

The program accepts command line argument as input. The command line of the program is given by:

<program_name> <word_to_mask> <file1> <file2> ...

E.g., if your program is named wordmask , then the following command at the command prompt

./wordmask abc t1.txt t2.txt

will ask your program ./wordmask to mask the word abc in the files t1.txt , t2.txt .

Command line arguments in C/C++ are implemented by having input parameters for the main() function:

int main(int argc, char* argv[])

Read the comments in the provided template to see the usage of the paramaters argc (an integer) and argv (an array

of C-strings).

The main() body has been completed for you, which means that command line argument parsing has been done for

you. But you should read the code and understand how it works, as you may need to deal with command line arguments

in your later courses too.

Output:

Your program will generate both screen output and file output.

Screen output: A line for each file specified in the command line arguments: first the filename, then the number of words

( n ) that have been masked in the file:

<filename>: <n>

or if there is any error accessing the file:

<filename>: file access error

File output: For each file specified in the command line arguments and can be successfully accessed, your program

should create a new file with all occurrences of the word <word_to_mask> being replaced by * .

If the input file is named <file> , then the corresponding output file should be named m<file> . Refer to the

sample test cases for examples.

Requirements:

You should start working from the 3.cpp provided.

Complete the function

int MaskWord(string word, string fileName, int &nMasked)

which

creates a new file with the same contents as the file named filename , except that all occurrences of word in the

file fileName are masked;

stores the number of words masked in nMasked

returns 0 if file operations (both accessing the input file and creating the output file) are successful and 1 if

otherwise.

Note:

The main() function has been completed for you, and you do not need to make any change to it. Read the code in

main() and understand what it does before you start working.

You may add your own functions wherever appropriate for better program modularity.

Sample Test Cases

Sample text files t1.txt , t2.txt , t3.txt , t4.txt are provided.

We show only the contents of t1.txt , t2.txt , t3.txt here:

t1.txt t2.txt t3.txt

Cab AbB CAB Ab CaB ABc aBb AB

cAb caB aBcAB CAB ABcAb AbcAb

aBCAB AB ABcAb aBCaB ABCAB Abb

aBC abC AbC ABCAB abCab ABC

aBCAB ABcAB AB cAb

ab abcab Ab abc aBCAB AbCAb abC

AbC ab abcab aBc aBc ab abcAB

Abc aBC ab abC ab aB AbCAB AbcaB

Ab ab ABc aBcab abC ABc AbCab ABcAb

app THe Elf DeEd keep SHe DEED

dEEd aPP Ab sheeP Cde THe sHe

ElF CDE sHe KeEP aB eLF An CaT

sHE hE KEeP he SHE dEED ab she

Commands entered by the users at the command line prompt ">" to run your program are shown in blue, assuming that your

program name is wordmask .

Note that since there is no user input from the standard input, here's how you should test your screen output against the

sample screen output (e.g., for test case 3_1) to check for correctness:

./wordmask AbC t1.txt t2.txt > myoutput.txt

diff myoutput.txt output3_1.txt

You should also test your file outputs against the sample file outputs for their correctness too.

3_1

./wordmask AbC t1.txt t2.txt

t1.txt: 1

t2.txt: 1

and two files mt1.txt and mt2.txt are created:

mt1.txt mt2.txt

Cab AbB CAB Ab CaB ABc aBb AB

cAb caB aBcAB CAB ABcAb AbcAb

aBCAB AB ABcAb aBCaB ABCAB Abb

aBC abC *** ABCAB abCab ABC

aBCAB ABcAB AB cAb

ab abcab Ab abc aBCAB AbCAb abC

*** ab abcab aBc aBc ab abcAB

Abc aBC ab abC ab aB AbCAB AbcaB

Ab ab ABc aBcab abC ABc AbCab ABcAb

3_2

./wordmask ab t1.txt t2.txt t3.txt

t1.txt: 0

t2.txt: 6

t3.txt: 1

and three files mt1.txt , mt2.txt and mt3.txt are created:

mt1.txt mt2.txt mt3.txt

Cab AbB CAB Ab CaB ABc aBb AB

cAb caB aBcAB CAB ABcAb AbcAb

aBCAB AB ABcAb aBCaB ABCAB Abb

aBC abC AbC ABCAB abCab ABC

aBCAB ABcAB AB cAb

** abcab Ab abc aBCAB AbCAb abC

AbC ** abcab aBc aBc ** abcAB

Abc aBC ** abC ** aB AbCAB AbcaB

Ab ** ABc aBcab abC ABc AbCab ABcAb

app THe Elf DeEd keep SHe DEED

dEEd aPP Ab sheeP Cde THe sHe

ElF CDE sHe KeEP aB eLF An CaT

sHE hE KEeP he SHE dEED ** she

3_3

./wordmask he t3.txt t4.txt t5.txt

t3.txt: 1

t4.txt: 3

t5.txt: file access error

and two files mt3.txt and mt4.txt are created.

Check the sample output files for the file contents.

Problem 4: (C) Luhn algorithm

The Luhn algorithm, also known as the "modulus 10" algorithm, is a simple checksum method to prevent simple transcription

errors for a sequence of digits. It is commonly used in distinguishing valid credit card numbers. Given an input code as a

string of digits, the algorithm works as follows:

1. Reverse the input string.

2. Sum the odd digits (i.e., first, third,... digits) in the reversed string to obtain a partial sum s1.

3. For every even digits (i.e., second, fourth, ... digits) in the reversed string, multiply the digit by 2

4. Obtain a partial sum s2 of the products in (3) with this rule: If a product in (3) is less than 10, just add the product to s2;

otherwise, add the sum of two digits in the product to s2.

5. If s1 + s2 is divisible by 10, then the input string of digits is a valid code.

Let's work out an example. Suppose the input string is 5255638118968609:

1. we first obtain the reversed string 9068698118365525

2. summing the odd digits, we have s1 = 9+6+6+8+1+3+5+2=40

3. the multiples of the even digits are 0, 16, 18, 2, 16, 12, 10, 10

4. summing the multiples of the even digits, we have

s2 = 0 + (1+6) + (1+8) + 2 + (1+6) + (1+2) + (1+0) + (1+0) = 30

5. since s1 + s2 = 70 which is divisible by 10, the input string is a valid code.

Write a C program to determine if an input string of digits is a valid code.

Input:

An input string of digits.

You may assume that the length of the input string is no more than 30 digits.

Output:

the first line displays the reversed string in step 1.

the second line displays the values s1 and s2, separated by a space.

the third line displays the string "valid" if the input is a valid string, or "invalid" if otherwise.

Requirement:

Use the command gcc -pedantic-errors -std=c11 4.c -o 4 to compile your program. (Or specify

-pedantic-errors -std=c11 as the compiler flags in the Atom editor.)

Sample Test Cases

User inputs are shown in blue.

4_1

5255638118968609

9068698118365525

40 30

valid

4_2

5255638118968608

8068698118365525

39 30

invalid