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

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. 

3 

0 

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- 

1 

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.