代写COMP20007、代写C++语言程序

日期：2023-04-07 10:03

Task 2: C Problem

Assignment 1

General

Task 1: Algorithmic

Design

Task 2: C Problem

Assignment Submission

Academic Honesty

Late Policy

Requirements: C

Programming

Programming Style

Mark Breakdown

Additional Support

Acknowledgements

Task 2: C Problem

Olivia's grandfather sent her a letter describing the great lost treasures he discovered decades ago while exploring

the Mystic Archipelago. To obscure his ndings, he stored the details of his treasure map in a hexagonal structure

like the one below.

The points in a array correspond to the points shown above. The same behaviour of odd and even columns

in a dierent order generalises to an map.

7 × 4

m × n

Part A.

Write a function in C,

struct point *getAdjacentPoints(struct map *m, struct point *p)

that returns all the adjacent points around an inputted point which would lie on the map.

These should be sorted rst by the rst coordinate, and then the second coordinate.

If the inputted point is not on the map, the point is considered to have no adjacent points.

Part B.

After decades of secrecy, Olivia's grandfather's letter revealed what each number corresponds to in his map.

If the value of the point is negative, it represents the depth of the ocean oor in metres.

If the value of the point is 0, it represents land without treasure.

If the value of the point is 100, it represents an airport.

If the value of the point is positive but not 100, it represents the value of that specic treasure.

Each bit of treasure corresponds to an artefact. Artefacts that belong to the same island are related, and so if you

nd multiple artefacts on the same island, they are worth much more than the sum of their parts. The total value

of artefacts on a specic island is given by this formula

f(x ,x , … ,x ) =1 2 n n × x ×1 x ×2 ? × x n

This means that if there is a treasure worth 20 on island 1, and island 2 has treasures worth 2, 3, 4, then the total

value that can be found is

20 + [3 × 2 × 3 × 4] = 92

This is because artefacts from dierent islands are unrelated and so you can only add the sum

of the value of islands.

Write a function

int mapValue(struct map *m)

That nds the total value of all the treasure found in a map. The map has points of sea, land and treasure

respectively, with an airport counting as land.

S,L,T

Describe the time complexity of the algorithm in terms of .S,L,T

Part C.

Olivia further nds out that her grandfather stored the locations of each treasure in a separate array. Olivia then

uses this information to make a better algorithm to nd the total value of a map. For islands with treasure,

represents the expected value of the number of treasure points on the island. The expected value of the size of

islands with treasure on the map is . The values of and are constants that represent the expected values

taken over every single map. Specic maps do not necessarily follow these constants.

N T

IS N T I S

(i) Briey describe how the new algorithm improves upon the above one. You may but do not have to use

pseudocode.

(ii) Find the best case time complexity of the new algorithm.

(iii) Find the worst case time complexity of the new algorithm.

(iv) Explain a reasonable denition to use for the average case of the new algorithm and nd its time complexity.

(v) Give an example of a map with at least treasure point, land point and sea point where your algorithm in

this question explores as many points in the previous question. Briey explain your answer.

1 1 1

Give each of the time complexities in terms of , , , , when appropriate. When calculating the time

complexities, you are seeing how the time complexity grows with respect to values , , .

S L T N T I S

S L T

Each answer only requires 1-2 sentences of brief justication.

Part D.

Olivia discovers that her grandfather was looking for the location of a mysterious treasure called The Star of

Alhambra. This is far more valuable than any of the previous treasures he mapped out and he narrowed down the

number of locations it could be. Olivia wants to be able to go from one place to another as quickly as possible to

check as many of these locations as she can. The amount of time it takes to move to an adjacent point is

determined by the current point you are on.

It takes minutes to move from a land point to an adjacent point. 5

It takes time to move from a point in the sea. 2 + ceil( )1000

depth2

It takes minutes to y from one airport to any other airport. where are the

x coordinates of the airports.

max(15, ∣x ?1 x ∣ ?2 2 85) x ,x 1 2

It takes minutes to move from an airport or treasure to an adjacent point (treat like land).5

Write a function

int minTime(struct map *m, struct point *start, struct point *end)

that nds the minimum amount of time from the start point to the end point.

If is the number of airports in the map, nd the worst case time complexity in terms of , , , . Briey

explain your algorithm and data structures used to justify your time complexity.

A S L T A

Part E.

Olivia nds some peculiar maps where any ocean has a depth of exactly . She strongly suspects that these

are the ones to contain The Star of Alhambra. Out of all these maps, she noticed that there were never more than

airports. All of these have a known location. Write a function:50m

5

int minTimeDry(struct map *m, struct point *start, struct point *end, struct point *airports, int numAirports

which nds the minimum distance from one point to another faster than the previous algorithm.

What is the worst case time complexity of this algorithm? To get full credit you must nd the algorithm with the

best time complexity.

TIP: If you think you've worked out the most ecient algorithm, but can't work out how to actually write it, check out the

printMap function.