用Python代写三个算法，解决实际的问题。
Objectives
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 the ability to:
- Implement algorithms for sorting in Python.
- Decompose code into functions in Python.
- Implement simple recursive algorithms in Python.
- Read from text files using Python.
- Manipulate lists using basic operations.
Submission Procedure
- Put you name and student ID in a comment at the start of each file in your solution.
- Save your files into a zip file called yourFirstName yourLastName.zip
- Submit your zip file containing your solution to Moodle.
- Your assignment will not be accepted unless it is a readable zip file.
Important Note
Please ensure that you have read and understood the college’s policies on
plagiarism and collusion available. You will be required to agree to these
policies when you submit your assignment.
Marks
This assignment has a total of 40 marks and contributes to 15% of your final
mark. Late submission will have 5% off the total assignment marks per day
(including weekends) deducted from your assignment mark.
In the case of this Assignment, this means that a late assignment will lose 2
marks for each day (including weekends). Assignments submitted 7 days after
the due date will normally not be accepted.
Marking Criteria
Task 1
Part A
- (a) File read in correctly
- (b) Merge sort implemented correctly
- (c) Rankings printed correctly
- (d) Code is readable (including meaningful variable names and non-trivial comments on code)
- (e) Code is appropriately decomposed
Part B
- (a) File read in correctly
- (b) Merge sort implemented correctly
- (c) Rankings printed correctly
- (d) Code is readable (including meaningful variable names and non-trivial comments on code)
- (e) Code is appropriately decomposed
Task 2
- (a) File read in correctly
- (b) Maximum spanning tree found
- (c) Spanning tree printed correctly
- (d) Code is readable (including meaningful variable names and non-trivial comments on code)
- (e) Code is appropriately decomposed
Task 3
Part A
- (a) Recursive function(s) implemented correctly
- (b) Mathematical function(s) implemented correctly
- (c) Code is readable (including meaningful variable names and non-trivial comments on code)
- (d) Code is appropriately decomposed
Part B
- (a) Report conclusions and quality
Task 1
For this year’s Olympic games, as always, the ranking of the teams is given by
the number of medals that they win in the various events. The number of medals
that each team won is stored in a file with one team per line.
Each line contains a team’s name, followed by the number of gold, silver and
bronze medals they won. The values on each line are separated by commas. An
example of the format is shown below.
Canada (CAN),1,5,12
Indonesia (INA),0,1,1
Poland (POL),2,2,6
Part A
For this part, you are to write a Python program to sort the teams by the
number of gold medals that they won. Perform this sort using Merge sort. The
program should ask the user for a filename containing the medal tally and read
the file in. It should then sort the teams by their number of gold medals and
finally print the teams in their sorted order along with their rank. Note that
multiple teams can have the same rank if they have the same number of medals.
For example, given a file containing the above tally, the program could print:
Sorted according to the number of gold medals
1: Poland (POL)
2: Canada (CAN)
3: Indonesia (INA)
Part B
In this part, write a Python program similar to the one from Part A but sort
by the total medal count instead. So instead of sorting by the number of gold
medals that each team won, this time it should be sorted by the total number
of medals (gold, silver and bronze) that the team won.
For this part, your program might print the following:
Sorted according to the total number of the medals
1: Canada (CAN)
1: Poland (POL)
2: Indonesia (INA)
Task 2
Previously in this unit, we have discussed finding minimum spanning trees
using a variety of methods. In this task, we will be finding maximum spanning
trees, that is spanning trees with the highest possible weight.
Create a Python program which finds a maximum spanning tree of a given graph.
Your program will ask the user for a filename and read a graph, stored as an
edge list, from that file. It will then compute a maximal spanning tree from
that graph and print the edges in the tree along with its weight. For example:
The file containing the following lines:
0 1 1
0 4 8
0 5 9
1 2 17
1 4 6
2 3 2
3 4 9
4 5 3
2 4 12
For example: If the file testGraph.txt contains the edges and weights of the
graph (see figure 1), your program might do the following:
This is the edges of the spanning tree
[[0,5],[0,4],[4,2],[2,1],[4,3]]
The weight of the maximum spanning tree is: 55
Task 3
A combination is a way of selecting k elements from a set of n elements. The
total number of ways of doing this.
Part A
For this task, you are to attempt to verify the correctness of this identity.
Do this by implementing both the left-hand and right-hand sides of the
equation as functions in Python.
Using these two functions, create a program which takes values for x and n and
prints the result of both the left-hand and right-hand sides of the identity
for those values.
Your program should include at least one non-trivial recursive function. You
must not use the math package and must write your own function to compute.
Part B
Using your program from Part A, compare the results for both functions for a
variety of values of both x and n. Choose at least 10 combinations of values
and present your results in a table. Include this table in a short report
(about 2 paragraphs) and discuss whether your results indicate that the
identity is true.
