代写ENGG1330、Python设计编程代做

日期：2025-04-03 09:20

ENGG1330 Computer Programming I Assignment

Page 1 of 12

ENGG 1330 Computer Programming I (24-25 Semester 2)

Programming Assignment

Due date: 9:30am, 30-Apr-2025 (Wed)

Important notes

• The purpose of the programming assignment is to assess your ability to implement

solu5ons for problems using knowledge learnt from this course. Only Python built-in

features are sufficient to solve problems in this assignment. It is unnecessary to import

any modules to do this assignment. Zero mark will be given to programs that import

any modules. If you are unsure, feel free to contact us for clarifica5on.

• While programming style is not graded, you are highly recommended to use func5ons

to factor your program, write clear and 5dy codes, e.g., descrip5ve comments, concise

and clear naming, appropriate spacing.

Submission

• Virtual Programming Lab (VPL) will be set up for submission and tes5ng. Only the last

submission will be used for assessment.

• Your program outputs must conform with the required formats, such as spacing and

alignment in order to pass the test cases. If you are unsure about the requirements, feel

free to contact us for clarifica5on.

• A few public test cases are provided in VPLs for checking whether your programs meet

the basic requirements. You are encouraged to test the robustness of your programs by

crea5ng more test cases on your own. Your programs will be assessed with another

set of private test cases.

• 20% will be deducted from the final mark for every 24-hour aOer the submission due

date. Do not submit any program aOer the due date if your work is final. Any

submission aOer the due date will be regarded as late submission.

Plagiarism

• Confirmed plagiarism cases (detected by the system) will get zero mark and subject to

disciplinary ac5ons. The penalty applies to the source provider(s) as well. In other

words, students who submit same/highly similar programs will all get zero mark.

Students have full responsibility to protect their programs from being accessed by

others.

• Every year in the past, several students had found engaged in plagiarism. They all got

zero mark for the assignment and a warning leWer issued by the Department Head.

Questions

• If you have any ques5ons about the requirements of a programming problem, please

send email to the corresponding author.

ENGG1330 Computer Programming I Assignment

Page 2 of 12

Programming Problem 1: Student Informa5on System [20%]

(author: LI Jiaqi, email: lijq@eee.hku.hk)

Write a program that gets the name of a student file, reads the file and performs the

following user commands. The program should con5nue to prompt for commands un5l the

user quits the program.

Input SpecificaIon

• The user commands and parameters, if any, are separated by a space with no space

at the end.

• The user commands and parameters are case-insensi5ve, i.e., the program should

accept both uppercase and lowercase.

• The order of records in the student file is random.

• Each line in the student file represents a student record.

• Each student record consists of the following four values separated by a comma ','

and all the values are valid and conform with the following format.

o Student ID: unique 8-digit number

o Name: First name (first character capitalized) followed by last name (first

character capitalized) aOer a space, <20 characters

o Major: a single string in uppercase, <5 characters

o GPA: a floa5ng point number in 1 decimal place

Output SpecificaIon

• In case of valid command with non-empty result, output the result.

• In case of empty result, print "Empty result".

• In case of invalid command, print "Invalid command".

User Commands and Output DescripIons

Command and

parameters

Example Descrip5on

AV [major] AV Calculate and print the average GPA in 2 decimal places of

all students in the file.

AV CE Calculate and print the average GPA in 2 decimal places of

all CE students.

CN [major] CN Count and print the numbers of students in the file.

CN CE Count and print the numbers of CE students.

LI [major] [gpa] LI List informa5on of all students in the file in table format*.

LI CE List informa5on all CE students in table format*.

LI CE 3.0 List informa5on all CE students with GPA>=3.0 in table

format*.

* Table format:

• Number of columns: 4

• Number of rows: number of the students in the result

• Column 1: Student ID, width: 10, leO-aligned

• Column 2: Student name, width: 20, right-aligned

• Column 3: Major, width: 5, right-aligned

ENGG1330 Computer Programming I Assignment

Page 3 of 12

• Column 4: GPA, width: 5, right-aligned

• The students are listed in alphabe5cal order of the last name

and then the first name.

QU QU Print "Program terminated" and quit the system.

Samples

ENGG1330 Computer Programming I Assignment

Page 4 of 12

Programming Problem 2: Mark and Recapture [20%]

(author: LIN Xuehong, email: u3011238@connect.hku.hk)

To find out the number of animals in an area (popula5on), it is imprac5cal to count every

individual. A method called "mark and recapture" is commonly used to es5mate an animal

popula5on's size. A por5on of the popula5on is captured, marked, and released. Later,

another por5on will be captured and the number of marked individuals within the sample is

counted. Since the number of marked individuals within the second sample should be

propor5onal to the number of marked individuals in the whole popula5on, an es5mate of

the total popula5on size can be obtained by dividing the number of marked individuals by

the propor5on of marked individuals in the second sample.

Formally, the popula5on size is es5mated as follows. Let

n = Number of animals marked in the first sample

K = Number of animals captured in the second sample

k = Number of recaptured animals that were marked

The es5mated popula5on size is N = n * K / k

Write a program to input the following three lists.

• A list of animals marked in the first sample

• A list of animals captured in the second sample

• A list indica5ng which of the corresponding recaptured animals in the second sample

were marked where a '1' is marked and a '0' is not marked

AOer doing the calcula5on, the program outputs the es5mated popula5on size for each of

the animals, one animal on a line in alphabe5cal order of animal's name. If there are any

animals of which their popula5on size cannot be es5mated in the case of n=0 or k=0 or k>n,

the program outputs a list of these animals in alphabe5cal order. If the number of marks in

the last list does not match the number of animals in the second sample, output "Invalid

data".

Format

• Names of animals in the input lists are case insensi5ve.

• Names of animals in the output are in uppercase.

• Items in a list are separated by a space with no space at the end

Samples

ENGG1330 Computer Programming I Assignment

Page 5 of 12

Choose ANY TWO out of the remaining THREE programming

problems. Note that they carry different marks according to the

level of difficulty and the maximum mark of the whole assignment

is bounded by 100%.

Programming Problem 3: Hit the Bricks [25%]

(author: LIN Xuehong, email: u3011238@connect.hku.hk)

Write a program to hit a brick ceiling. The brick ceiling is represented by a 2D array of

integers ranging from 0 to 4, where a '0' means no brick and a posi5ve integer is the weight

of the brick. A hit at the ceiling is represented by a pair of row number and column number

where row number starts from 1 at the top and column number starts from 1 on the leO.

Ini5ally, all bricks on the input ceiling are safe, i.e., no brick will fall without a hit. Also, all

bricks on edges of the ceiling must be safe, i.e., bricks on edges never fall even when there is

a hit. If a hit is at a brick not on an edge, the brick will fall. The remaining bricks can s5ll

s5ck on the ceiling if one of the following condi5ons holds, otherwise, they will also fall.

• The brick is on the edge.

• The number of adjacent bricks (above, below, leO and right) is greater than or equal

to the weight of the brick.

The program inputs the following numbers.

• Number of rows on the ceiling

• Number of columns on the ceiling

• The ceiling before hit, which is represented by weights of bricks, entered row by row,

and weights in each row are separated by a space with no space at the end

• A list of hits, where each hit is represented by a pair of row number and column

number, separated by a comma ',' and hits are separated by a space with no space at

the end

The program outputs the ceiling aOer each hit, which is represented by weights of bricks,

printed row by row, and weights in each row are separated by a space with no space at the

end.

ENGG1330 Computer Programming I Assignment

Page 6 of 12

Samples

Explana5on of the samples:

• AOer the first hit (4,3), the ceiling remains no change because the brick is on the

edge.

• AOer the second hit (3,3),

o the brick at (3,3) falls

• AOer the third hit (2,3),

o the brick at (2,3) falls

o the brick at (2,2) also falls because the number of adjacent bricks of the brick

at (2,2) drops to 2 and becomes less than the weight of the brick at (2,2),

which is 3.

If a colon ':' appears at the

end of a line, there is no

space aOer the colon.

ENGG1330 Computer Programming I Assignment

Page 7 of 12

Programming Problem 4: Arithme5c Expression Validator [30%]

(author: LIN Mingxian, email: mingxianlin@connect.hku.hk)

Write a program to validate an input arithme5c expression containing only the following

elements.

• Variables

• Natural numbers (posi5ve integers)

• Arithme5c operators: addi5on (+), subtrac5on (-), mul5plica5on (*) and division (/)

• Parentheses: ()

Requirements:

• Valid expressions

o Output "Valid: [operator sequence]", where the operator sequence is a list of

operators in execu5on order, separated by a space, with no space at the end.

o Special case:

§ No operator is present (e.g., single variable, number): output "Valid:

None".

• Invalid expressions

o Output "Invalid: [index]", where the index, star5ng from 0, indicates the

posi5on of the first invalid token in the input expression.

o A token refers to an individual element in the input expression such as a

variable, a number, an operator, an open parenthesis or a closing parenthesis.

o Special cases:

§ Empty parentheses, (): index indicates the posi5on of the closing

parenthesis.

§ Unclosed parentheses: output "Invalid: -1"

§ Trailing operator, an operator appears at the end of the input

expression: output "Invalid: -1"

• Valida5on rules

o Variable naming:

§ Variables must follow Python naming rules

§ Start with a leWer or underscore (_), followed by alphanumeric

characters or underscores.

§ Cannot be a Python reserved keyword as shown the following list.

['False', 'None', 'True', 'and', 'as', 'assert', 'async', 'await', 'break',

'class', 'con5nue', 'def', 'del', 'elif', 'else', 'except', 'finally', 'for',

'from', 'global', 'if', 'import', 'in', 'is', 'lambda', 'nonlocal', 'not', 'or',

'pass', 'raise', 'Output', 'try', 'while', 'with', 'yield']

o Operator placement:

§ Must be placed between two operands.

§ Operators cannot be consecu5ve.

o Parentheses:

§ All parentheses must be properly balanced and non-empty.

ENGG1330 Computer Programming I Assignment

Page 8 of 12

Your choices of difficulty

You may choose to ignore parentheses in the input arithmetic expression. In more

than half of the test cases, the input expressions do not contain parentheses. So, a correct

program that can validate arithmetic expressions without parentheses can still get more

than half of the marks in this problem.

Samples

• Valid Expressions

• Invalid expressions

o Invalid variable names

o Invalid operator placements

o Invalid parentheses

ENGG1330 Computer Programming I Assignment

Page 9 of 12

Programming Problem 5: Maze Solving with Backtracking Op5miza5on [35%]

(author: LIANG Shuang, email: sliang57@connect.hku.hk)

Background

The backtracking mechanism is a systematic algorithmic paradigm used to solve constraint

satisfaction and combinatorial optimization problems. In this problem, you will implement

backtracking mechanism to solve maze problems.

Part 0: Import Main Program

The following main program is given and embedded in VPL. So, you do not need to

include the code of the main program in your uploaded file. You must name your

uploaded file as "a5.py" and the function names must be the same as the ones required by

this problem. You must put this line of code, import a5_main, in the first line of your

uploaded program to allow your program to access the code in the main program.

ENGG1330 Computer Programming I Assignment

Page 10 of 12

The main program performs the following tasks.

• Ask user to enter the maze filename.

• Call the function load_maze() to load the maze structure.

• Print the maze returned by the function load_maze().

• Print the start and end coordinates returned by the function load_maze().

• Call the function backtracking() to solve the maze.

• Print the path returned by the function backtracking().

• In case of no solution, print "No solution exists!".

Note that the coordinates of a point refers to the row number star5ng from 0 at the top and

the column number star5ng from 0 on the leO, i.e., the coordinates of the top-leO corner of

a maze is (0,0).

Part 1: Load the Maze

Write the function load_maze(file_path) to load the maze structure from the input

text file.

The maze file contains the following elements:

• Walls: Represented by “*”

• Paths: Represented by “.”

• Start Point: Represented by “S”

• End Point: Represented by “T”

The function has to do the following tasks.

• Read the input text file.

• Convert the start point, the paths, and the end point to 0, and the walls to 1.

• Store the maze in a 2D list.

• Return the 2D list, the coordinates of the start point and end point.

Structure of the Function load_maze

def load_maze(file_path): """

Loads the maze structure from the input text file and converts it into a 2D

list.

Args:

file_path (str): Path to the maze text file.

Returns:

maze (list): 2D list representing the maze, where each item in the list is a

sub-list representing a row of the maze.

start (tuple): Coordinates of the start point.

end (tuple): Coordinates of the end point.

"""

# Complete your code here.

return maze, start, end

ENGG1330 Computer Programming I Assignment

Page 11 of 12

Part 2: Solving the Maze by Backtracking Mechanism

Write the function backtracking(maze, start, end) to implement backtracking

mechanism to solve mazes. Backtracking is an algorithmic technique for solving problems

by exploring potential paths and undoing (backtracking) steps when a dead-end is

encountered.

ImplementaIon Details

(1) Use a stack to record the player’s movement history. The stack allows backtracking by

popping the most recent posi5on when a dead-end is reached. In your func5on, the stack

records the state of every move consis5ng of three components: (posi5on, path, remaining

direc5ons).

position: coordinates (x, y) of the current posi5on

path: list of coordinates visited so far

remaining_directions: direc5ons yet to explore at this posi5on

(2) Use a list visited to store the posi5ons visited so far.

(3) Define directions as [(0, 1), (1, 0), (0, -1), (-1, 0)] (right, down, leO, up). For each

posi5on, try all direc5ons in reverse order, i.e., try up first, and then try leO next and so on

so forth.

(4) Define condi5onal statements to check whether a move is valid. A move is valid if:

A) The new posi5on is within the maze boundaries.

B) The new posi5on is on the path.

C) The new posi5on is not visited.

(5) If a valid move is found:

A) Move to the new posi5on.

B) Push the new state (posi5on, path, remaining direc5ons) to the stack.

(6) If no valid moves remain (dead-end encountered):

A) Remove the current posi5on from visited to allow revisi5ng to explore other

poten5al paths.

B) Pop the stack to trace back.

(7) Termina5on condi5ons:

A) Success: return the path if the current posi5on matches the end point.

B) No path found: Return None if the stack is empty.

Structure of the Function backtracking

def backtracking(maze, start, end):

# Complete your code here

while stack:

# Complete your code here

if current == end:

return path

# Complete your code here

return None

stack = [(position, path, remaining_directions), ...]

ENGG1330 Computer Programming I Assignment

Page 12 of 12

Important Note

Your program has to comply with the requirements and implementa5on details s5pulated in

this problem in order to find the expected path using backtracking. Even if your program can

find an alterna5ve path, it cannot pass the test cases.

Samples

Explanation of the first 3 steps

• At Step 0, the current posi5on is at the start point (0,4), the path consists of the start

point (0,4) and the direc5ons yet to explore consists of all direc5ons.

• At Step 1, the current posi5on is at (1,4) aOer trying up, leO and down at (0,4).

• At Step 2, the current posi5on is at (2,4) aOer trying up, leO and down at (1,4).

• At Step 3, the current posi5on is at (2,5) aOer trying up, leO, down and right at (2,4).

Step stack (posi'on, path, remaining direc'ons) from top to bo6om visited