莫纳什大学FIT1045Assignment3课业解析

欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top

莫纳什大学FIT1045Assignment3课业解析

题意:

分为三个Task。 Task1:这是一个排序任务,将每个数列集合的第一个作为枢轴,将原集合划分成小于、等于、大于枢轴的分布。要求是只在原始集合上面进行改变,且只有O(n)的复杂度。 Task2:任务是制作一个数独游戏,分为五个步骤。1.读取游戏网格文件,进行输出。2.根据数独规则检查插入位置是否有效。3.在第r行进行输入,如果r行中已经有了这个数字,则返回原始的网格游戏网格,否则返回插入了该值的网格(可能会有多个位置能插入该数字)。4.向网格中输入数字,输出所有匹配的结果。5.输入文本形式保存的游戏,输出正确的数独结果。 Task3:1.一条街道上相邻的住户不会同时购买商品,找到这条街上的最大的营业额。2.按照汉堡包的设定,判断一个输入是不是真的汉堡包。

 解析:

任务一可以设置几个指针表示三种数应该插入的位置,这样遍历一次数组就能够让它们处在正确的位置。任务二需要处理一个多维数组,判断同一行同一列的数字是否相同,同时还有一个文件读入的问题,将保存在文本中的数独游戏载入后输出正确的数独结果。任务三第一问可以采取动态规划,第二问是一个字符匹配的问题,任务可以考虑是三种括号的匹配问题(左括号只能匹配对应括号的右括号)。 

 涉及知识点:数组、字符处理。

更多可加微信讨论

微信号Ssss_970521

pdf

FIT1045 Algorithms and programming in Python, S2-2019
Assignment 3 (value 20%)
Due: Sunday 20th October 2019, 11:55 pm.
Objectives
The objectives of this assignment are:
• To demonstrate the ability to implement algorithms using basic data structures and operations on them.
• To gain experience in designing an algorithm for a given problem description and implementing that
algorithm in Python.
• To demonstrate an understanding of complexity, and to the ability to implement algorithms of a given
complexity.
Submission Procedure
1. Save your files into a zip file called yourStudentID yourFirstName yourLastName.zip
2. Submit your zip file containing your solution to Moodle.
3. Your assignment will not be accepted unless it is a readable zip file.
Important Note: Please ensure that you have read and understood the university’s policies on plagiarism
and collusion available at http://www.monash.edu.au/students/policies/academic-integrity.html. You
will be required to agree to these policies when you submit your assignment.
A common mistake students make is to use Google to find solutions to the questions. Once you have seen a
solution it is often difficult to come up with your own version. The best way to avoid making this mistake is
to avoid using Google. You have been given all the tools you need in workshops. If you find you are stuck, feel
free to ask for assistance on Moodle, ensuring that you do not post your code.
Marks: This assignment will be marked both by the correctness of your code and by an interview with
your lab demonstrator, to assess your understanding. This means that although the quality of your code
(commenting, decomposition, good variable names etc.) will not be marked directly, it will help to write clean
code so that it is easier for you to understand and explain.
This assignment has a total of 20 marks and contributes to 20% of your final mark. For each day an assignment
is late, the maximum achievable mark is reduced by 20% of the total. For example, if the assignment is late by
3 days (including weekends), the highest achievable mark is 70% of 20, which is 14. Assignments submitted 7
days after the due date will normally not be accepted.
Detailed marking guides can be found at the end of each task. Marks are subtracted when you are unable to
explain your code via a code walk-through in the assessment interview. Readable code is the basis of a
convincing code walk-through.
1
Task 1: Ternary Sorts (4 Marks)
Create a Python module called ternary.py. Within this module implement the following task. You may not
import any other libraries or modules.
Task: Ternary Partition (4 Marks)
Write a function ternary partition(lst) that partitions an unsorted list into three sections: smaller than
pivot, equal to pivot, larger than pivot.
Input: an unsorted list containing one or more integers.
Output: a pair of integers, where the first integer is the index of the final position of the pivot, and the second
integer is the index of the first element that is larger than the pivot. The pivot should be the element in
the 0th position in the original list. To receive full marks the original list must be partitioned; however,
the list is not returned.
Examples
a) Let lst1=[3]. Calling ternary partition(lst1) returns (0,1), as after calling function lst1=[3], thus
the pivot section starts at 0 and ends at 1 (exclusive).
b) Let lst2=[3,2,2,5,6,3,1,3]. Calling ternary partition(lst2) returns (3,6), as after calling function
lst2==[2,2,1,3,3,3,5,6] (or an approximation of this depending on the specifics of the implementation),
thus the pivot section starts at 3 and ends at 6 (exclusive).
c) Let lst3=[1,2,3]. Calling ternary partition(lst3) returns (0,1), as after calling function lst3==[1,2,3]
(or an approximation of this depending on the specifics of the implementation), thus the pivot section starts
at 0 and ends at 1 (exclusive).
To receive full marks, this function must have a complexity of O(N), where N=len(lst). This means sorting
the list then finding the pivot’s location in the list is not a viable solution.
Marking Guide (total 4 marks)
Marks are given for the correct behavior of ternary partition:
(a) 1 mark for an implementation that does not change the original list and without a complexity of O(N);
(b) 3 marks for an implementation that does not change the original list and has a best and worst-case
complexity of O(N);
(c) 4 marks for an implementation that changes the given list to reflect the partitioning (the list is changed
’in place’) and that has a best and worst-case complexity of O(N).
Note: marks will be deducted for including print statements or for including function calls outside of function
definitions.
2
Task 2: Sudoku (10 Marks)
Sudoku is a logic-based combinatorial number-placement puzzle. The objective is to fill a x2 ∗ x2 grid with
digits so that each column, each row, and each of the x × x subgrids that compose the grid contain all of the
digits from 1 to x2. (For instance, a 9 ∗ 9 grid would contain nine 3 ∗ 3 subgrids.) The puzzle setter provides a
partially completed grid, which for a well-posed puzzle has a single solution.1
(a) An exemplary Sudoku puzzle ... (b) ... and its solution
Create a Python module called sudoku.py. Within this module implement the following five tasks. You are
encouraged to decompose the given tasks into additional functions. You may import deepcopy from copy. You
may not import any other libraries or modules.
To assist with your implementation of the following tasks, you may use the following function subgrid values.
This function takes a n×n sudoku grid, a row coordinate, and a column coordinate, and returns a list containing
the n values of the subgrid that the item at the coordinates belongs to.
def subgrid_values(grid, row, col):
val = []
#get dimension of inner box
n = int(len(grid)**(0.5))
#get starting row and starting col
r = (row//n)*n
c = (col//n)*n
for i in range(r, r+n):
for j in range(c, c+n):
val.append(grid[i][j])
return val
Part A: Get Grid (1 Mark)
Write a function grid from file(file name) that reads in a file containing a sudoku grid and returns the
contents of the file as a Python-readable table.
Input: a file name file name, where the file contains n lines, and each line contains n entries separated by
commas. Each entry will either be a positive integer, or the letter ‘x’.
Output: a table represented as a nested list, where each entry in the orignal file is an element in the table,
and all numbers have been converted to integers.
Examples
a) Calling grid from file(‘gridA.txt’) returns:
[ [‘x’,‘x’,1,‘x’],
[4,‘x’,‘x’,‘x’],
[‘x’,‘x’,‘x’,2],
[‘x’,3,‘x’,‘x’] ]
b) Calling grid from file(‘gridB.txt’) returns:
1Description adapted from Wikipedia. Read more here: https://en.wikipedia.org/wiki/Sudoku.
3
[ [1,‘x’,9,‘x’,‘x’,‘x’,‘x’,6,‘x’],
[8,4,‘x’,‘x’,1,‘x’,‘x’,7,5],
[‘x’,‘x’,2,‘x’,‘x’,3,‘x’,‘x’,4],
[‘x’,‘x’,8,3,2,1,‘x’,4,7],
[‘x’,‘x’,5,‘x’,‘x’,‘x’,6,‘x’,‘x’],
[4,2,‘x’,6,9,5,8,‘x’,‘x’],
[7,‘x’,‘x’,1,‘x’,‘x’,4,‘x’,‘x’],
[6,9,‘x’,‘x’,8,‘x’,‘x’,5,3],
[‘x’,5,‘x’,‘x’,‘x’,‘x’,7,‘x’,9] ]
Part B: Valid Entry (1 Mark)
Write a function valid entry(grid, num, r, c) that determines whether a particular value can be entered
at a particular location in a valid grid, while maintaining validity.
Input: a nested list grid, that represents an n × n sudoku grid; each item in the inner list is either an integer
(example 13), or the string ‘x’; a positive integer num, where 0 < num ≤ n; and two non-negative integers
r and c that represent the row and column that num will be inserted, where 0 ≤ r; c < n. You may assume
grid[r][c]==‘x’.
Output: a boolean True if the insertion is valid; otherwise False. For the insertion to be valid, it must result
in a grid that does not contain duplicate numbers in any row, any column, or any subgrid.
Examples
grid = [ [1,‘x’,‘x’,‘x’],
[‘x’,‘x’,‘x’,‘x’],
[‘x’,‘x’,1,‘x’],
[‘x’,‘x’,‘x’,‘x’] ]
a) Calling valid entry(grid, 1,1,3) returns True.
b) Calling valid entry(grid, 1,0,3) returns False, because there would be two 1s in row 0.
c) Calling valid entry(grid, 1,1,2) returns False, because there would be two 1s in column 2.
d) Calling valid entry(grid, 1,3,3) returns False, because there would be two 1s in the bottom left 2 ∗ 2
subgrid.
Part C: Enter Number In Row (2 Marks)
Write a function grids augmented in row(grid,num,r) that returns the complete list of valid augmented
grids, where each grid contains num in row r.
Input: a nested list grid, that represents a valid n × n sudoku grid; each item in the inner list is either an
integer (example 27), or the string ‘x’; a positive integer num, where 0 < num ≤ n; and a non-negative
integer r, where 0 ≤ r < n.
Output: a nested list containing all augmented sudoku grids such that each grid is valid, and each grid
contains num in row r. If num is in row r in the original grid, return a list containing the original grid. If
there is no way to augment the given grid to create a valid grid where num is in row r, return an empty
list.
Remember that you may import deepcopy from copy.
Examples
lite_grid = [ [1,‘x’,‘x’,‘x’],
[‘x’,‘x’,‘x’,‘x’],
[‘x’,‘x’,‘x’,‘x’],
[‘x’,2,‘x’,‘x’] ]
full_grid = [ [2,‘x’,‘x’,‘x’],
[‘x’,3,2,4],
[‘x’,‘x’,4,2],
4
[1,2,3,‘x’] ]
grid_A = [ [‘x’,‘x’,1,‘x’],
[4,‘x’,‘x’,‘x’],
[‘x’,‘x’,‘x’,2],
[‘x’,3,‘x’,‘x’] ]
a) Calling grids augmented in row(lite grid,1,0) returns:
[
#note there is already a 1 in row 0, so returns list containing original grid
[ [1,‘x’,‘x’,‘x’],
[‘x’,‘x’,‘x’,‘x’],
[‘x’,‘x’,‘x’,‘x’],
[‘x’,2,‘x’,‘x’] ]
]
b) Calling grids augmented in row(lite grid,1,1) returns:
[
[ [1,‘x’,‘x’,‘x’],
[‘x’,‘x’,1,‘x’], #note there is now a 1 in row 1
[‘x’,‘x’,‘x’,‘x’],
[‘x’,2,‘x’,‘x’] ],
[ [1,‘x’,‘x’,‘x’],
[‘x’,‘x’,‘x’,1], #note there is now a 1 in row 1
[‘x’,‘x’,‘x’,‘x’],
[‘x’,2,‘x’,‘x’] ]
]
c) Calling grids augmented in row(full grid,1,1) returns [], because there is no valid way to insert a 1 in
row 1 of full grid.
d) Calling grids augmented in row(grid A,1,2) returns:
[
[ [‘x’,‘x’,1,‘x’],
[4,‘x’,‘x’,‘x’],
[1,‘x’,‘x’,2], #note there is now a 1 in row 2
[‘x’,3,‘x’,‘x’] ] ,
[ [‘x’,‘x’,1,‘x’],
[4,‘x’,‘x’,‘x’],
[‘x’,1,‘x’,2], #note there is now a 1 in row 2
[‘x’,3,‘x’,‘x’] ]
]
Part D: Enter Number (3 Marks)
Write a function grids augmented with number(grid,num) that returns a list of valid n × n grids, where each
grid contains n nums. (I.e. if given a 9 ∗ 9 grid, and num = 3, each grid returned must contain nine 3’s.)
Input: a nested list grid, that represents a valid n × n sudoku grid; each item in the inner list is either an
integer (example 13), or the string ‘x’; and a positive integer num, where 0 < num ≤ n.
Output: a nested list containing all valid sudoku grids where each grid contains n nums. If there is no way to
augment the given grid to create a valid sudoku grid containing n nums, return an empty list.
5
Examples
a) Calling grids augmented with number(lite grid,1) returns:
[
#note there are now 1s in every row, column, and inner square in both grids
[ [1,‘x’,‘x’,‘x’],
[‘x’,‘x’,1,‘x’],
[‘x’,1,‘x’,‘x’],
[‘x’,2,‘x’,1] ] ,
[ [1,‘x’,‘x’,‘x’],
[‘x’,‘x’,‘x’,1],
[‘x’,1,‘x’,‘x’],
[‘x’,2,1,‘x’] ]
]
b) Calling grids augmented with number(full grid,1) returns [], because there is no valid way to modify
full grid so that it contains four 1s.
c) Calling grids augmented with number(grid A,1) returns:
[
[ [‘x’,‘x’,1,‘x’],
[4,1,‘x’,‘x’],
[1,‘x’,‘x’,2],
[‘x’,3,‘x’,1] ]
]
Part E: Solve Sudoku (3 Marks)
Write a function solve sudoku(file name) that finds the solution for the given sudoku.
Input: a file name file name, where the file contains n lines, and each line contains n entries separated by
commas. Each entry will either be a positive integer, or the letter ‘x’.
Output: a nested list representing a completed sudoku grid. You may assume the file given will always contain
exactly one valid solution.
Note: you may find the functions that you are required to write in parts C and D useful in solving part E;
however, you may find it more natural to solve part E using an alternative approach. If this is the case, note
that you are not required to use parts C and D for your solution to part E.
Examples
a) Calling solve sudoku(‘gridA.txt’) returns:
[ [3,2,1,4],
[4,1,2,3],
[1,4,3,2],
[2,3,4,1] ]
b) Calling solve sudoku(‘gridB.txt’) returns:
[ [1, 3, 9, 5, 7, 4, 2, 6, 8],
[8, 4, 6, 9, 1, 2, 3, 7, 5],
[5, 7, 2, 8, 6, 3, 9, 1, 4],
[9, 6, 8, 3, 2, 1, 5, 4, 7],
[3, 1, 5, 7, 4, 8, 6, 9, 2],
[4, 2, 7, 6, 9, 5, 8, 3, 1],
[7, 8, 3, 1, 5, 9, 4, 2, 6],
[6, 9, 4, 2, 8, 7, 1, 5, 3],
[2, 5, 1, 4, 3, 6, 7, 8, 9] ]
6
Marking Guide (total 10 marks)
Marks are given for the correct behavior of the different functions:
(a) 1 mark for grid from file.
(b) 1 mark for valid entry.
(c) 2 marks for grids augmented in row.
(d) 3 marks for grids augmented with number.
(e) 3 marks for solve sudoku.
Note: marks will be deducted for including print statements or for including function calls outside of function
definitions.
7
Task 3: Jobs (6 Marks)
Create a Python module called jobs.py. Within this module implement the following two tasks. You may not
import any other libraries or modules.
Part A: Salesperson (3 Marks)
You are an unscrupulous salesperson who sells devices that allow a household to use their neighbours’ wi-fi for
free. Due to the nature of the product you sell, it is never possible to sell to neighbours. Every day you find a
new street at which to sell your devices. You are very good at your job, and know from market research exactly
how much each household would be willing to pay.
Write a function max sales(street) that finds the maximum amount of sales you can make for a given
street.
Input: a list street of non-negative integers that represents the street you are visiting; each integer represents
the amount of money the ith household would be willing to pay; the ith household is neighbours to the
ith - 1 and ith + 1 household. The first and last household are not neighbours.
Output: an integer that is the maximum amount of sales you can expect to make on that street.
Examples
a) Calling max sales([2,3,10,5,6,0,4,12,6]) returns 30, because you could sell to the first, third, fifth, and
eighth house on the street, thus making a sale of 2 + 10 + 6 + 12 = 30.
b) Calling max sales([]) returns 0, because you cannot make any sales when selling to a street with no houses.
Part B: Burgerperson (3 Marks)
Your sales business was shutdown by the IEEE and you have had to get a job at a hip burger joint. This burger
joint is different from most - the only ingredient used in the burgers is bread. Your job is to check the bread
stacks made in the kitchen are actually burgers.
For a bread stack to be a burger it must follow two rules: first, any open piece of bread must be followed
by a matching closing piece of bread; second, any open-close pair may contain a stack of bread between them,
provided the stack is also a burger. There are three different kinds of bread: brioche (open brioche is ‘ob’,
closed is ‘cb’), wholemeal (‘ow’, ‘cw’), and rye (‘or’, ‘cr’).
Write a function is burger(breads) that determines whether a stack of bread is a burger.
Input: a non-empty list of strings breads that represents the bread stack you are checking; the possible strings
are: ‘ob’, ‘cb’, ‘ow’, ‘cw’, ‘or’, ‘cr’.
Output: a boolean, True if the bread stack is a burger; otherwise False. A bread stack is a burger if each
open piece of bread is followed by a matching closed piece of bread, and there is either nothing between
the opening and closing bread, or there is one or more burgers between the opening and closing bread.
Examples
a) Calling is burger([‘ob’]) returns False, because the opening brioche does not have a closing brioche.
b) Calling is burger([‘ob’,‘cb’]) returns True.
c) Calling is burger([‘ob’,‘or’,‘cb’]) returns False, because the brioche bun does not contain a valid
burger.
d) Calling is burger([‘ob’,‘or’,‘cr’,‘cb’]) returns True.
e) Calling is burger([‘ob’,‘or’,‘cb’,‘cr’]) returns False, because the brioche bun does not contain a
valid burger, and the rye bun does not contain a valid burger.
f) Calling is burger([‘ob’,‘or’,‘cr’,‘ob’,‘cb’,‘cb’]) returns True.
g) Calling is burger([‘or’,‘cr’,‘ob’,‘cb’]) returns True.
8
Marking Guide (total 6 marks)
Marks are given for the correct behavior of the different functions:
(a) 3 marks for max sales.
(b) 3 marks for is burger.
Note: marks will be deducted for including print statements or for including function calls outside of function
definitions.
9  


51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: abby12468