代写C语言基础作业，完成十个小任务。
Task Five: “Connect Two”
For this task you need to calculate the shortest path between two points on a
grid. The starting location will be labelled ‘1’ and the destination location
will be labelled ‘2’. The shortest path will initially follow a diagonal (if
necessary) followed by a vertical or horizontal path (if necessary).
Define a function called ConnectTwo() which is passed one input: a
2-dimensional array (10 rows and 10 columns) of integers. This 2-dimensional
array represents a map. All elements in the array will be equal to zero,
except for the starting location (which has the value 1) and the ending
location (which has the value 2). Your function should determine the shortest
path between these two locations and then modify the array by setting each
element on the path to the value 3. The starting and ending locations should
remain unchanged. The diagram below illustrates this (the input map is on the
left, and the resulting modified map is on the right):
Element 1 represents the starting location and element 2 represents the
destination
Function prototype declaration
void ConnectTwo(int maze[10][10])
—|—
Assumptions
You can assume the input array dimensions are always 10x10, and that every
element is initialised to zero except for the starting and ending locations
(which will be initialised to 1 and 2 respectively).
Example
int i, j;
int map[10][10] = {
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 2, 0, 0, 0, 0, 0, 0}
};
ConnectTwo(map);
printf("\n");
for (i = 0; i < 10; i++) {
for (j = 0; j < 10; j++) {
printf("%d", map[i][j]);
}
printf("\n");
}
—|—
Expected output
Task Six: “The Wolf of Wall Street”
Your friend is trying to make money on the share market and has asked you to
help them analyse the price data for a number of stocks they are looking at.
In particular, they are interested in finding “runs” in the data, where a run
consists of an increasing sequence of prices (moving left to right). For
example, consider the data below which shows 10 prices changing over time:
123, 120, 118, 119, 121, 126, 127, 130, 129, 132
The longest “run” in this sequence of data values begins with the value 118.
Starting with the value 118, the next 5 values are in strictly increasing
order (119, 121, 126, 127, 130). The length of this “run” is therefore 5. Your
friend wants you to write a program which takes a sequence of prices as input
and calculates two things: where the longest “run” begins in the data and the
length of the longest “run”.
Define a function called DayTrader() which takes four inputs: an array of
integers representing the price information, the length of the array (i.e. the
number of prices), and two integer pointers which you should use to store the
calculated output values. The first pointer records the address where you
should store the length of the best “run”, and the second pointer records the
address where you should store the index position of the start of the “run”.
Function prototype declaration
void DayTrader(int *prices, int numPrices, int *bestRun, int *bestRunIndex)
—|—
Assumptions
You can assume that the array will contain at least one price (i.e. the length
of the array will be greater than 0).
Runs only consist of strictly increasing values (two consecutive equal values
do not constitute a “run”)
If there are two or more “runs” of the same length in the array, then you must
return the smallest index position (i.e. left most value) when reporting the
start of the run (i.e. the bestRunIndex)
Example
int pricesA[15] = {59, 60, 55, 23, 42, 44, 48, 50, 43, 45, 43, 44, 47, 51, 52};
int pricesB[10] = {1, 2, 3, 3, 3, 4, 3, 4, 5, 6};
int pricesC[10] = {123, 120, 118, 119, 121, 126, 127, 130, 129, 132};
int bestRun, bestRunIndex;
DayTrader(pricesA, 15, &bestRun, &bestRunIndex);
printf("Best run = %d, best run index = %d\n", bestRun, bestRunIndex);
DayTrader(pricesB, 10, &bestRun, &bestRunIndex);
printf("Best run = %d, best run index = %d\n", bestRun, bestRunIndex);
DayTrader(pricesC, 10, &bestRun, &bestRunIndex);
printf("Best run = %d, best run index = %d\n", bestRun, bestRunIndex);
—|—
Expected output
Best run = 4, best run index = 3
Best run = 3, best run index = 6
Best run = 5, best run index = 2
Task Seven: “Compression”
Compression is an important technique for reducing the amount of space
required to store information. This is of particular importance when large
amounts of data need to be transmitted from one place to another. Define a
function called Compress() which implements a basic compression algorithm. The
input data to be compressed is represented simply as an array of positive
integers. The end of the input data is indicated by the special value -1.
Compress the data by counting how many times a value is repeated
consecutively. You can then represent that data value with two values: the
number of repetitions of the value and the value itself. For example, if the
data consists of eight “10”s: 10, 10, 10, 10, 10, 10, 10, 10 then this can be
represented in compressed form as just two values: 8, 10.
Of course, this algorithm is not very effective if values aren’t repeated
consecutively in the data. In the worst case, when there is no repetition, the
compressed data will be double the size of the original data! You should store
the compressed data in the second input to the function, which is also an
array of integers. Don’t forget to place the value -1 at the end of the
compressed data!
Function prototype declaration
void Compress(int *input, int *output)
—|—
Assumptions
The input array will always contain the special value -1 (indicating the end
of the data).
The input array will consist of at least one value to be compressed (i.e.
before the -1).
Ensure that you add the value -1 to the end of the compressed data in the
output array.
Example
int input[MAX_ARRAY_SIZE] = {7,7,7,7,7,3,4,4,4,7,0,0,0,0,0,0,0,0,0,0,0,0,-1};
int output[MAX_ARRAY_SIZE];
int i;
Compress(input, output);
i = 0;
while (output[i] != -1) {
printf("%d ", output[i]);
i++;
}
—|—
Expected output:
5 7 1 3 3 4 1 7 12 0
Task Eight: “Arbitrary Incrementing”
In C, the int type is limited to (typically) 32 bits. The following example,
where 1 is added to the largest positive integer value, illustrates integer
overflow:
int value = 2147483647;
int result = value + 1;
printf(“%d + 1 = %d”, value, result);
—|—
In this case, the output would be:
2147483647 + 1 = -2147483648
If we want to represent arbitrarily large integers, then we could use an array
where each element in the array represents a digit in the number. In fact, we
could use strings for this purpose, and have the characters in the string
represent the digits. We could then define special functions to perform
arithmetic. As an example, consider the following code:
char value[MAX_ARRAY_SIZE] = “2147483647”;
char output[MAX_ARRAY_SIZE];
AddOne(value, output);
printf(“%s + 1 = %s”, value, output);
—|—
In this case, we use the string “2147483647” to represent a large integer
value. The AddOne() function is then used to compute a new string where the
characters represent the integer that is one larger than the original. The
output from the code above is:
2147483647 + 1 = 2147483648
This apparently solves the integer overflow problem! However, there are some
downsides arithmetic performed in this way is much slower than using the int
type.
We can now perform this basic arithmetic on really large numbers:
char value[MAX_ARRAY_SIZE] = “123456789123456789123456789”;
char output[MAX_ARRAY_SIZE];
AddOne(value, output);
printf(“%s + 1 = %s”, value, output);
—|—
and the output is:
123456789123456789123456789 + 1 = 123456789123456789123456790
For this task, you should define the AddOne() function.
The AddOne() function takes two inputs: the first is a string (i.e. an array
of characters) which represents an arbitrarily large number. The second is
also a string into which you should store the output of the function. The
output is a string which represents the number one larger than the input
number.
Function prototype declaration
void AddOne(char *input, char *output)
—|—
Assumptions
You can assume that the input string represents a valid positive integer
(greater than or equal to 1).
You cannot assume that the length of the output string will equal the length
of the input string - for example, this will clearly not be the case if all of
the characters in the input string are equal to ‘9’.
Example
AddOne("12345", output);
printf("Result = %s\n", output);
AddOne("9999999999999", output);
printf("Result = %s\n", output);
AddOne("1999999999999", output);
printf("Result = %s\n", output);
—|—
Expected output
Result = 12346
Result = 10000000000000
Result = 2000000000000
Task Nine: “Textual histogram”
Let’s say that we have the following 6 data values representing frequencies of
some measurement:
3, 1, 2, 0, 4, 1
and we now would like to plot these on a histogram. We could do this easily
using many graphical plotting programs such as Excel:
We could also represent the same data using a textual representation, where
the bars are represented by “X” characters:
X
X X
X X X
XXX XX
And to make this look a little nicer, we could surround the bars with a border
of ‘*’ characters:
********
* X *
* X *
*X X *
*X X X *
*X X X *
XXX XX
********
Define a function called Histogram() that takes an array of integers
representing the data to be plotted, and generates a string (representing the
histogram) in precisely the format described above. Please take note of the
following:
- each line of text in the string ends with a new line (‘\n’) except for the very last line
- there must be no extra space characters anywhere at the beginning or end of a line
The Histogram() function should take three input values. The second and third
input values represent the data to be plotted. This is stored as an array of
integers, and the number of elements in the array. The first input to the
function is the string into which you should store the resulting histogram.
Function prototype declaration
void Histogram(char *result, int *values, int numValues);
—|—
Assumptions
You can assume the input array will consist of at least one value greater than
0.
Example
int values1[10] = {1, 0, 3, 1, 2, 4, 5, 6, 2, 2};
int values2[3] = {1, 0, 1};
char formatted[MAX_ARRAY_SIZE];
char example[MAX\_ARRAY\_SIZE] = "*****\n*X X*\n*****";
Histogram(formatted, values1, 10);
printf("%s\n\n", formatted);
Histogram(formatted, values2, 3);
printf("%s\n", formatted);
if (strcmp(example, formatted) == 0) {
printf("This matches EXACTLY and is correct");
}
—|—
Expected output
************
* X *
* XX *
* XXX *
* X XXX *
* X XXXXXX*
*X XXXXXXXX*
************
*****
*X X*
*****
This matches EXACTLY and is correct
Task Ten: “Gold Rush!”
The year is 1849 and you have just arrived in California to make your fortune
in the gold rush. You have your pick axe, your kerosene lamp, a box of
dynamite and your laptop. You need to stake your claim over the land that
contains the largest gold deposits. You have access to a number of prospecting
maps (which are grid based) which contain information about the quality of the
gold deposits in the land. Fortunately, this data is digitized so you can
easily read it into your program as a 2dimensional array.
The values (which are digits between 0 and 9) in each cell of the map
represent the type of minerals present in the corresponding locations. The
value 0 indicates that there are no deposits of any value at the location, and
values between 1 and 8 indicate various kinds of common minerals which are of
little interest to you. The value you are interested in is the value 9 as this
represents the presence of gold! To help you quickly determine which maps are
most promising, you want to write a program to compute how much gold (i.e.
cells with a value of 9) is present in a given map.
You also want to compute one other value - that is, how much pure gold is
present in the map. A cell contains pure gold if it contains gold and if all
eight of the cells directly adjacent to it (in any direction: up, down, left,
right or any diagonal) also contain gold. By this definition, cells on the
border of the map cannot contain pure gold.
The 15 x 15 map shown above contains 4 separate regions of gold (which are not
connected to each other). The table below illustrates these four regions. In
the column labelled “Prospecting map”, the map is shown and cells containing
gold are highlighted in bold. Cells containing pure gold are also underlined.
In the column labelled “Region”, the four non-connected regions are shown on
separate rows. The column labelled “Gold” shows how much gold is contained in
the region and the column labelled “Pure gold” shows the amount of pure gold
Define a function called GoldRush() that takes five inputs:
- A one-dimensional array of integers, called results, into which you will store the results computed by your function
- An integer, called rows, which indicates how many rows are present in the map
- An integer, called cols, which indicates how many columns are present in the map
- A two-dimensional array of integers, called map, which contains the map data
- An integer called bonus which is only used if you have attempted the bonus tasks described later (for this task, this input will always have the value 0)
This function should compute the total amount of gold in the map, and the
total amount of pure gold in the map. Using the example map shown above, the
total amount of gold is 39 and the total amount of pure gold is 3.
The function is void (i.e. it does not return a value). To return the results
that you have computed, you should use the results array (the first input to
the function). You should store the total amount of gold in results[0] and the
amount of pure gold in results[1].
Function prototype declaration
void GoldRush(int *results, int rows, int cols, int map[MAX_MAP_SIZE][MAX_MAP_SIZE], int bonus);
—|—
Assumptions
You can assume the map will have at least two rows and two columns, and will
have no more than MAX_MAP_SIZE rows and MAX_MAP_SIZE columns
Example
int i, j;
int results[MAX_ARRAY_SIZE];
int map[MAX_MAP_SIZE][MAX_MAP_SIZE] = {
{1,2,2,0,0,0,0,0,0,0,0,0,0,0,0},
{0,4,3,0,0,0,0,9,9,8,0,0,0,0,0},
{0,2,0,3,3,0,0,9,9,0,0,0,0,0,0},
{0,0,0,0,0,4,6,9,9,6,0,0,0,0,0},
{0,0,0,0,0,0,9,0,8,0,0,6,0,0,0},
{0,0,9,9,9,9,0,0,0,0,7,7,8,8,0},
{0,0,9,9,9,9,0,0,0,0,0,7,0,0,0},
{0,0,9,9,9,9,0,1,1,1,2,2,2,2,2},
{0,0,0,9,9,0,0,0,0,0,0,0,0,3,0},
{0,0,0,4,4,0,0,0,0,0,0,0,5,6,0},
{0,0,0,0,9,9,9,0,0,9,0,0,0,5,0},
{0,0,1,2,9,9,9,0,0,0,9,0,0,4,2},
{0,0,0,0,9,9,9,0,0,0,9,9,9,0,0},
{9,9,0,0,0,0,1,0,0,0,0,9,0,0,0},
{9,0,0,0,0,0,2,2,0,0,0,0,0,0,0}
};
GoldRush(results, 15, 15, map, 0);
printf("Searching for gold!\n");
printf(" Total gold = %d\n", results[0]);
printf(" Pure gold = %d\n", results[1]);
—|—
Expected output
Searching for gold!
Total gold = 39
Pure gold = 3
Bonus Task I: “Gold regions”
The last input to the GoldRush() function is an integer called bonus. For Task
Ten, described above, this input will always be 0. For the first bonus task,
the value of this input will be set to 1.
For the first bonus task, you should count the total amount of gold present in
each non-connected region of gold on the map. You should report your results
by storing them in the results array, in decreasing order (so the largest
region of gold is reported first). Once you have stored the results for each
region, in consecutive elements of the array, you must then store the value 0
in the next element of the array to indicate there are no more results.
Example
int i, j;
int results[MAX_ARRAY_SIZE];
int map[MAX_MAP_SIZE][MAX_MAP_SIZE] = {
{1,2,2,0,0,0,0,0,0,0,0,0,0,0,0},
{0,4,3,0,0,0,0,9,9,8,0,0,0,0,0},
{0,2,0,3,3,0,0,9,9,0,0,0,0,0,0},
{0,0,0,0,0,4,6,9,9,6,0,0,0,0,0},
{0,0,0,0,0,0,9,0,8,0,0,6,0,0,0},
{0,0,9,9,9,9,0,0,0,0,7,7,8,8,0},
{0,0,9,9,9,9,0,0,0,0,0,7,0,0,0},
{0,0,9,9,9,9,0,1,1,1,2,2,2,2,2},
{0,0,0,9,9,0,0,0,0,0,0,0,0,3,0},
{0,0,0,4,4,0,0,0,0,0,0,0,5,6,0},
{0,0,0,0,9,9,9,0,0,9,0,0,0,5,0},
{0,0,1,2,9,9,9,0,0,0,9,0,0,4,2},
{0,0,0,0,9,9,9,0,0,0,9,9,9,0,0},
{9,9,0,0,0,0,1,0,0,0,0,9,0,0,0},
{9,0,0,0,0,0,2,2,0,0,0,0,0,0,0}
};
GoldRush(results, 15, 15, map, 1);
printf("Searching for gold!\n");
printf(" Total gold regions = ");
i = 0;
while (results[i] != 0) {
printf("%d ", results[i]);
i++;
}
—|—
Expected output
Searching for gold!
Total gold regions = 21 9 6 3
Bonus Task II: “Pure gold”
The last input to the GoldRush() function is an integer called bonus. For the
second bonus task, the value of this input will be set to 2.
For the second bonus task, you should count the total amount of pure gold
present in each nonconnected region of gold on the map. You should report your
results by storing them in the results array, in decreasing order (so the
largest region of pure gold is reported first). Once you have stored the
results for each region, in consecutive elements of the array, you must then
store the value 0 in the next element of the array to indicate there are no
more results.
Example
int i, j;
int results[MAX_ARRAY_SIZE];
int map[MAX_MAP_SIZE][MAX_MAP_SIZE] = {
{1,2,2,0,0,0,0,0,0,0,0,0,0,0,0},
{0,4,3,0,0,0,0,9,9,8,0,0,0,0,0},
{0,2,0,3,3,0,0,9,9,0,0,0,0,0,0},
{0,0,0,0,0,4,6,9,9,6,0,0,0,0,0},
{0,0,0,0,0,0,9,0,8,0,0,6,0,0,0},
{0,0,9,9,9,9,0,0,0,0,7,7,8,8,0},
{0,0,9,9,9,9,0,0,0,0,0,7,0,0,0},
{0,0,9,9,9,9,0,1,1,1,2,2,2,2,2},
{0,0,0,9,9,0,0,0,0,0,0,0,0,3,0},
{0,0,0,4,4,0,0,0,0,0,0,0,5,6,0},
{0,0,0,0,9,9,9,0,0,9,0,0,0,5,0},
{0,0,1,2,9,9,9,0,0,0,9,0,0,4,2},
{0,0,0,0,9,9,9,0,0,0,9,9,9,0,0},
{9,9,0,0,0,0,1,0,0,0,0,9,0,0,0},
{9,0,0,0,0,0,2,2,0,0,0,0,0,0,0}
};
GoldRush(results, 15, 15, map, 2);
printf("Searching for gold!\n");
printf(" Total pure gold regions = ");
i = 0;
while (results[i] != 0) {
printf("%d ", results[i]);
i++;
}
—|—
Expected output
Searching for gold!
Total pure gold regions = 2 1
