这次作业是用C语言完成星球大战的程序

Algorithms 3027/3927 Assignment 1 v2
Introduction
Commander! We are under attack by alien flying saucers!
Each alien flying saucer shows up on the Earth Defence Grid as a y-coordinate (its height off the
ground), an `-coordinate (the leftmost side) and an r-coordinate (the rightmost side). All flying saucers
are 1 grid square high, but can be any number of grid squares wide.
0 1 2 3 4 5 6 7 98
Figure 1: Six flying saucers given by the data [ { `:0, r:2, y:0 }, { `:3, r:7, y:1 }, { `:2, r:3, y:2 }, { `:7,
r:9, y:2 }, { `:0, r:3, y:3 }, { `:8, r:9, y:4 } ]
To defend ourselves we can use our Earth Defence Laser Cannons. Each laser cannon can be positioned
at any x-coordinate and fires directly upwards. The laser beam is so powerful it will pierce through any
number of flying saucers, and destroy anything with which it comes into contact.
0 1 2 3 4 5 6 7 98
Figure 2: Three laser cannons positioned at 1, 3 and 8 are sufficient to destroy all six flying saucers. It is
not possible to destroy all the flying saucers with only two laser cannons. Notice there are multiple ways
to position three lasers to destroy all the flying saucers.
However, the Earth Defence Laser Cannons are extremely expensive and cannot be moved once put
in place. Your job as Earth Defence Commander is to determine where to position the cannons such that
every flying saucer is destroyed, while using as few cannons as possible. The flying saucers will not be
able to move before the cannons are set up and fired.
Specification
An instance of the Earth Defence problem consists of a list of n rectangles R1, . . . , Rn. For 1 ≤ i ≤ n,
the rectangle Ri represents the i-th saucer and is specified by a left coordinate `i
, a right coordinate
ri and an altitude yi
. Each rectangle has a height of 1. The coordinates and altitudes will always be
non-negative integers.
1
The Laser Cannons can only be placed at integer coordinates. A Laser Cannon placed at coordinate
x destroys a saucer represented by the rectangle Ri
if `i ≤ x ≤ ri
, i.e. the infinite vertical line drawn
through x intersects Ri
. For brevity, we say that x destroys Ri
. Note that the rectangles include their
boundary, so a line at x = 3 will intersect the rectangle { `: 0, r: 3, y: 5 }.
The goal is to determine the minimum number k of Laser Cannons needed to destroy all flying saucers
and the integer coordinates of the Laser Cannons.
Task 1: Find a counter-example to a bad greedy algorithm [20
marks]
A friend of yours (name redacted to preserve anonymity) claims that the following greedy algorithm solves
the problem:
1. Initalize C to be the empty list and S to be the list of saucers represented by rectangles R1, . . . , Rn
2. While S is not empty:
(a) Let x be the integer coordinate that destroys the most number of saucers in S
(b) Add x to C
(c) Remove from S the saucers destroyed by x
3. Return |C| and C as the solution
Your friend says that the algorithm is correct because “it destroys the most number of remaining saucers
at each step, so it is locally optimal and thus globally optimal.”
Your task is to find an input to the Earth Defence problem such that the above algorithm does not
return an optimal solution.
(a) Give a list of rectangles in the format as used in the above figures. You are encouraged to include
a diagram or picture of the rectangles. (Just rectangles, no need to draw actual saucers or aliens.)
(b) Give the coordinates of C in the order that they were added to C.
(c) Give an optimal solution to the problem.
Task 2: Design a correct greedy algorithm [60 marks]
In this task, you will design a greedy algorithm that correctly solves the Earth Defence problem.
(a) Description of how your algorithm works (“in plain English”).
(b) Prove that your algorithm returns an optimal solution.
(c) Prove an upper bound on the time complexity of your algorithm.