辅导CS220-Assignment 4解析Python语言程序

- 首页 >> Java编程
CS220 Semester 1 2020 
Assignment 4 (traversal and optimisation) 
Due date June 10, 2020, 10pm 
100 Marks in total 
This assignment requires you to submit programs in Python that you have written yourself 
to the automarker, http://www.cs.auckland.ac.nz/automated-marker. Your imple- 
mentation must be from first principles and cannot use an existing library methods that 
might solve the problem (eg graph search algorithms etc). You can use libraries for stan- 
dard implementations of data structures such as queues, stacks and priority queues. 
The automarker runs on a Linux box. Read the automarker help and FAQ for more 
details. 
Please submit only Python source code (.py extensions only). 
1. Directed girth of a digraph 30 Marks 
For a digraph G, the length of the shortest cycle is called the directed girth of the 
graph. If the digraph has no cycle then the girth is undefined, and we will say it has 
girth 0. Your task is to determine the directed girth of each input digraph. 
Input format: described below under the heading, “Digraph input format”. 
Output format: Output will be just one integer per line sent to the console. For 
the example input given below we would output the following two integers denoting 
the directed girth of the two digraphs, using 0 to indicate the digraph has no cycle. 
2. Tree and cross arcs in a DFS 30 Marks 
For a given set of digraphs, write a program that performs DFS on each digraph 
starting at node 0 and prints out the total number of tree arcs and cross arcs resulting 
from the traversal. Use our standard convention that when there is a choice of white 
or grey nodes, the one with the lowest index should be chosen. 
Input format: described below under the heading, “Digraph input format”. 
Output format: For each input digraph, print out a line with the number of tree 
arcs and the number of cross arcs separated by a comma. 
For the example input shown below, the output would be 
Digraph input format: A sequence of one or more digraphs is taken from the keyboard 
(sys.stdin). Each graph is represented by an adjacency list. The first line is an integer n in- 
dicating the order of the graph. This is followed by n white space separated lists of adjacen- 
cies for nodes labeled 0 to n - 1. The lists are sorted. The input will be terminated by a line 
consisting of one zero (0). This line should not be processed. The sample input below shows 
two digraphs, the first has node set {0, 1, 2, 3} and arc set {(0, 1), (0, 3), (1, 2), (1, 3), (2, 0)}, 
the second has node set {0, 1, 2} and arc set {(0, 1), (0, 2), (2, 1)}. 
3. Optimisation 40 Marks 
A frog needs to navigate its way from its current position to its next meal through 
a dangerous landscape. To do so, it leaps from boulder to boulder, but it can jump 
at most 1m. Your aim is to find the length of the shortest path to get the frog to its 
next meal using only boulders. 
The landscape is a n × n square (units are cm) with boulders at exact positions 
given by coordinates (x, y) where 0 ≤ x, y ≤ n. Boulders are scattered across the 
landscape. Use Euclidean distance to calculate the distance between boulders. 
Input format: The input is taken from the keyboard (e.g. by sys.stdin) as multiple 
lines of comma separated integers. Each line has 2p + 1 numbers where p ≥ 2. The 
first number on each line is the size of the landscape, n. 
The following 2p numbers give locations of p boulders, so the jth boulder is at 
(2j, 2j + 1). 
The first position listed on each line is the frog’s current position, the final position 
listed is the target boulder where the frog will find its next meal. 
For example: 
100,0,0,0,100,100,100 
1000,20.892,986,602,138.97,206.2,10.44 
200,25,25,10,1,50,25,140,30 
Output format: For each line of input, output a single number to the console 
which is the length of the shortest path from the origin town to the desitination 
town. Use str.format to give this value to 2 decimal places. Precisely, format 
x using ’{:.2f}’.format(x). Do not use any other rounding throughout your 
algorithm. If the destination town is unreachable from the origin, output -1. 
For the example input above, output would be: 
Marking 
The maximum number of submissions for each problem is fixed at 10. 
Each problem has four test cases associated with it worth one quarter of the marks for 
that problem. Some of the test cases will be large to test for speed. You get full marks if 
you pass all test cases. 
站长地图