首页 » algorithm辅导 » Python辅导 | MCD4710 Assignment 2 Algorithms and Programming

Python辅导 | MCD4710 Assignment 2 Algorithms and Programming

为给定问题描述设计算法的经验,并在Python 3中实现这些算法.

MCD4710 Assignment 2 (10%)
MCD4710 Introduction to Algorithms and Programming
Objectives
Due: Thursday, September 5, 2019, 5:00 pm – Week 10
The objectives of this assignment are:
• To gain experience in designing algorithms for a given problem description and implementing those algorithms in Python 3.
• To demonstrate your understanding of:
– how to implement recursive algorithms in Python. – how to decompose code into functions in Python. – how to read from text files using Python.
– how to manipulate lists using basic operations.
– brute-force approaches to problems Submission Procedure
1. CreateasinglepythonfilecontainingallyoursolutionswithyournameandstudentIDascomments. 2. SaveyourfileintoazipfilecalledYourStudentID.zip
3. SubmityourzipfilecontainingyoursolutiontoMoodle.
4. Yourassignmentwillnotbeacceptedunlessitisareadablezipfile.
Important Notes:
1. Pleaseensurethatyouhavereadandunderstoodtheuniversity’spoliciesonplagiarismandcollusion available at https://www.monashcollege.edu.au/ data/assets/pdf_file/0010/17101/dip-assessment- policy.pdf. You will be required to agree to these policies when you submit your assignment.
2. Yourcodewillbecheckedagainstotherstudents’workandcodeavailableonlinebyadvancedplagiarism detection systems. Do not take the risk, make sure your work is your own.
3. Where it would simplify the problem you may not use built-in Python functions or libraries (e.g. using list.sort() or sorted()). Remember that this is an assignment focusing on algorithms and programming.
4. Yourprogramwillbecheckedagainstanumberoftestcases.Donotforgettoincludecommentsinyourcode explaining your algorithm. If your implementations have bugs, you may still get some marks based on how close your algorithm is to the correct algorithm. This is made difficult if code is poorlydocumented.
5. Foreachtask,youneedtowriteaprogramthatproperlydecomposestheproblem.Youwilllearnfunctionsand decomposition in Week 3.
Marks: This assignment has a total of 70 marks and contributes to 10% of your final mark. Late submission will have 10% off the total assignment marks per day (including weekends) deducted from your assignment mark. Assignments submitted 7 days after the due date will normally not be accepted.
1

Marking Criteria:
Total: 70 marks
A. menu (5 marks)
B. Game logic (25 marks)
C. brute-force approach (30 marks)
D. decomposition, variable names and documentation (10 marks)
Assignment code interview
Each student will be interviewed during a lab session regarding their submission to gauge your personal understanding of your Assignment code. The purpose of this is to ensure that you have completed the code yourself and that you understand the code submitted. Your assignment mark will be scaled according to the responses provided.
Interview Rubric
0
The student cannot answer even the simplest of questions There is no sign of preparation
They probably haven’t seen the code before
0.25
There is some evidence the student has seen the code
The answer to a least one question contained some correct points
But it’s clear they cannot engage in a knowledgeable discussion about the code
0.5
The student seems underprepared
Answers are long winded and only partly correct
They seem to be trying to work out the code as they read it
They seem to be trying to remember something they were told but now can’t remember However they clearly know something about the code
With prompting they fail to improve on a partial or incorrect answer
0.75
The student seems reasonably well prepared
Questions are answered correctly for the most part but the speed and/or confidence they are answered with is not 100%
With prompting they can add a partially correct answer or correct an incorrect answer
1
The student is fully prepared
All questions were answered quickly and confidently
It’s absolutely clear that the student has performed all of the coding themselves.
2

Background:
In this assignment, you are required to write a program for the game Minesweeper. The game starts with a grid of unmarked squares. The game is played by asking the user to either step on one of these squares to reveal its content or flag that square as a mine. If a square containing a mine is revealed, the player loses the game otherwise a number is displayed in the square, indicating how many adjacent squares contain mines. If no mines are adjacent, then all adjacent squares will be revealed. The player uses the numbers displayed in the squares to deduce the contents of other squares, and may either safely reveal each square or flag the squares containing a mine, as shown below:
Note: The size of the board will never be greater than 10 x 10 and the number of mines squares will be less than the size2.
3

Task 1: Create a menu (5 marks)
Create a menu with the following options which you will use for the remaining tasks.
1- Read board (from assignment one)
2- New board (from assignment one)
3- Mine Count (from assignment one)
4- Play
5- Brute force
6- Quit
Note: The board size in this assignment can take any value between 2 and 10 inclusive.
Task 2: Game logic (25 marks)
This task is about programming the game logic. You will need two new boards, userBoard and mineBoard.
The game begins with an empty list of lists, userBoard that tracks all the users’ play entries. The second board, mineBoard, contains all the mines and the mine count as completed in assignment 1.
Part A: Check Function (5 marks)
Write a function check(userBoard, mineBoard) that takes userBoard and mineBoard and checks if the user
wins, loses or is still playing . If userBoard contains an ‘x’, when compared to mineBoard, the player loses. To determine if a player wins we need to check if all empty squares have been revealed in the userBoard. If neither of the two cases above happened, then the user still playing. The function should return -1 if the user loses, 1 if the user wins and 0 if still playing.
Part B: Play (20 marks)
In this task you are required to write a function play(userBoard, mineBoard,row,col) that would take the row
and col as input from the user and update userBoard with what is present at that location, a number 0-8 or an ‘x’. Use check(userBoard, mineBoard) from Part A to update the user of their play progress.
Bonus (5 Marks): If the revealed square has 0 mines surrounding it then the function will recursively call itself for all the neighbouring squares. By doing so an entire region of contiguous empty squares will be revealed.
Example 1:
What would you like to do?
1- Read board
2- New board
3- Mine count
4- Play
5- Brute force
6- Quit
?2
board size from 2 to 10: 2
number of mines less than size^2: 1
0| | |
1| | |
|0|1|
What would you like to do?
1- Read board
2- New board
3- Mine count
4- Play
5- Brute force
6- Quit
?4
4

row: 0 col: 0
0|1| |
1| | |
|0|1|
row: 0
col: 1
0|1|1|
1| | |
|0|1|
row: 1
col: 0
0|1|1|
1|1| |
|0|1|
you win
0|1|1|
1|1|x|
|0|1|
Example 2:
What would you like to do?
1- Read board
2- New board
3- Mine count
4- Play
5- Brute force
6- Quit
?2
board size from 2 to 10: 3
number of mines less than size^2: 3
0| | | |
1| | | |
2| | | |
|0|1|2|
What would you like to do?
1- Read board
2- New board
3- Mine count
4- Play
5- Brute force
6- Quit
?4
row: 0
col: 0
0|x| | |
1| | | |
2| | | |
|0|1|2|
you lose
0|x|1|0|
1|2|3|2|
2|1|x|x|
|0|1|2|
5

Task 3: Brute-force (30 marks)
This task is about applying the brute-force approach to find a solution for minesweeper.
PartA: Chosenapproach(5marks)
In a separate word or pdf document, prepare a written discussion of the manner in which you intend to apply brute-force to this problem. Be sure to respond to the following in your discussion
1. how each individual possible solution is represented
2. the complexity of your brute force algorithm
3. how you can be certain it will give you the correct solution
Part B: Implementation (25 marks)
Prepare a python function bruteForce(mineBoard) which has mineBoard as input. The function will generate all possible solutions based on extracting the number of mines and size of the board from mineBoard and then starting with an empty board, will each time generate and check if there is a correct answer. The function will display each possibility until the first correct solution is found.
Example 1
What would you like to do?
1- Read board
2- New board
3- Mine count
4- Play
5- Brute force
6- Quit
?2
board size from 2 to 10: 3
number of mines less than size^2: 5
0| | | |
1| | | |
2| | | |
|0|1|2|
What would you like to do?
1- Read board
2- New board
3- Mine count
4- Play
5- Brute force
6- Quit
?5
==>
0|x|x|x|
1|x|x| |
2| | | |
|0|1|2|
> Incorrect
==>
0|x|x|x|
1|x| |x|
2| | | |
|0|1|2|
> Incorrect
6

==>
0|x|x|x|
1|x| | |
2|x| | |
|0|1|2|
> Incorrect
==>
0|x|x|x|
1|x| | |
2| |x| |
|0|1|2|
> Incorrect
==>
0|x|x|x|
1|x| | |
2| | |x|
|0|1|2|
> Incorrect
==>
0|x|x|x|
1| |x|x|
2| | | |
|0|1|2|
> Incorrect
==>
0|x|x|x|
1| |x| |
2|x| | |
|0|1|2|
> correct
What would you like to do?
1- Read board
2- New board
3- Mine count
4- Play
5- Brute force
6- Quit
?3
0|x|x|x|
1|4|x|3|
2|x|2|1|
|0|1|2|
Example 2
What would you like to do?
1- Read board
2- New board
3- Mine count
4- Play
5- Brute force
6- Quit
7

?2
board size from 2 to 10: 2
number of mines less than size^2: 2
0| | |
1| | |
|0|1|
What would you like to do?
1- Read board
2- New board
3- Mine count
4- Play
5- Brute force
6- Quit
?5
==>
0|x|x|
1| | |
|0|1|
> Incorrect
==>
0|x| |
1|x| |
|0|1|
> Incorrect
==>
0|x| |
1| |x|
|0|1|
> Incorrect
==>
0| |x|
1|x| |
|0|1|
> Incorrect
==>
0| |x|
1| |x|
|0|1|
> correct
What would you like to do?
1- Read board
2- New board
3- Mine count
4- Play
5- Brute force
6- Quit
?3
0|2|x|
1|2|x|
|0|1|
8

What would you like to do?
1- Read board
2- New board
3- Mine count
4- Play
5- Brute force
6- Quit
?
Task 4: Decomposition, Variable names and Code Documentation(10 marks)
Marks will be allocated for good use of variable names, code documentations and proper decomposition.
9


程序辅导定制C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


本网站支持 Alipay WeChatPay PayPal等支付方式

E-mail: vipdue@outlook.com  微信号:vipnxx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank

发表评论

您的电子邮箱地址不会被公开。