C代写:ENGGEN131 Mining Part1

代写C语言基础作业,完成十个小任务。

Introduction

Welcome to the final project for the ENGGEN131 course!

You have ten tasks to solve. For each task there is a problem description, and you must write one function to solve that problem. You may, of course, define other functions which these required functions call upon.

Do your very best, but don’t worry if you cannot complete every function. You will get credit for every task that you solve (and you may get partial credit for tasks solved partially).

This must be addressed somewhere so we may as well get it out of the way - this is an individual project. You do not need to complete all of the tasks, but the tasks you do complete should be an accurate reflection of your capability. You may discuss ideas in general with other students, but writing code must be done by yourself. No exceptions. You must not give any other student a copy of your code in any form - and you must not receive code from any other student in any form. There are absolutely NO EXCEPTIONS to this rule.

Please follow this advice while working on this project - the penalties for plagiarism (which include your name being recorded on the misconduct register for the duration of your degree, and/or a period of suspension from Engineering) are simply not worth the risk.

Understanding the project files

There are three files that you will be working with when you are developing your solutions to the project tasks. The most important of these three files is project.c. This is the source file that you will submit for marking. Please note the following:

  • project.c is a source file that ONLY CONTAINS FUNCTION DEFINITIONS
  • there is no main() function defined in project.c (and you must not add one)
  • a separate program, test_program.c, containing a main() function has been provided to you to help you test the function definitions you write in project.c

The diagram below illustrates the relationship between the three files.

The blue shaded regions in the above diagram indicate where you should write code when you are working on the project. There are three simple rules to keep in mind:

  • You MUST NOT write any code in project.h (the header file)
  • You MUST write implementations for the functions defined in project.c
  • You SHOULD write additional test code in test_program.c to thoroughly test the code you write in project.c

Getting started

To begin, download the file called ProjectResources.zip from Canvas. There are three files in this archive:

project.c

This is the source file that you will ultimately submit. In this source file you will find the ten functions that you should complete. Initially each function contains an incorrect implementation which you should delete and then correct. You may add other functions to this source file as you need. You must not place a main() function in this source file. This is the only file that you will submit for marking.

project.h

This is the header file that contains the prototype declarations for the ten functions you have to write. You must not edit this header file in any way. Both source files (project.c and test_program.c) include this header file, and the automated marking program will use the provided definition of project.h. Modifying this header file in any way will be an error.

test_program.c

This is the source file that contains the main() function. This file has been provided to you to help you test the functions that you write. In this file, you should create some example inputs and then call the functions that you have defined inside the project.c source file. Some simple examples have been included in this file to show you how this can be done.

Place these three source files in an empty folder.

You might like to start by looking at the project.c source file. In this source file you will find ten function definitions, however they are all implemented incorrectly. The prototype declarations are as follows:

1
2
3
4
5
6
7
8
9
10
int DivisorOfThree(int a, int b, int c);
double AverageSheep(int *counts);
void Emphasise(char* word);
int PrimeFactors(int n, int *factors);
void ConnectTwo(int maze[10][10]);
void DayTrader(int *prices, int numPrices, int *bestRun, int *bestRunIndex);
void Compress(int *input, int *output);
void AddOne(char *input, char *output);
void Histogram(char *result, int *values, int numValues);
void GoldRush(int *results, int rows, int cols, int map[MAX_MAP_SIZE][MAX_MAP_SIZE], int bonus);

You need to modify and correct the definitions of these ten functions.

Next, you should run the program in test_program.c. To do this, you will need to compile both source files. For example, from the Visual Studio Developer Command Prompt, you could type:

cl /W4 project.c test\_program.c

Or, simply:

cl /W4 *.c

You should see no warning messages generated when the code compiles.

If you run the program, you should see the following output:

Welcome to the minimal test program for Project Two.
This test program provides an absolute minimal set of test cases that you can use to automatically test the functions you have defined for the project. Failing any of these tests is an indication that there is an error in your implementation. However, because this is a minimal set of tests, passing all of them is no guarantee that your functions are defined correctly. It is up to you to test your code more thoroughly, but hopefully this template will be a useful guide for you.
Good luck!

Task One:   DivisorOfThree() - not yet implemented
Task Two:   AverageSheep()   - not yet implemented
Task Three: Emphasise()      - not yet implemented
Task Four:  PrimeFactors()   - not yet implemented
Task Five:  ConnectTwo()     - not yet implemented
Task Six:   DayTrader()      - not yet implemented
Task Seven: Compress()       - not yet implemented
Task Eight: AddOne()         - not yet implemented
Task Nine:  Histogram()      - not yet implemented
Task Ten:   GoldRush()       - not yet implemented

Notice that initially the output from each test function is:

not yet implemented

When you attempt to implement each function, you will get feedback on whether the function passes or fails the basic tests that are provided. There are three basic tests provided for each function (although you should create more tests of your own!). Therefore, ideally, you want to see this output for each function:

PASS PASS PASS

ENGGEN 131, Semester Two, 2017
-5-

What to submit

You must not modify project.h, although you can modify test_program.c. You will not be submitting either of these files.

You must only submit ONE source file - project.c - for this project. This source file will be marked by a separate automated marking program which will call your functions with many different inputs and check that they produce the correct outputs.

Testing

Part of the challenge of this project is to test your functions carefully with a range of different inputs. It is very important that your functions will never cause the marking program to crash or freeze regardless of the input. If the marking program halts, you cannot earn any marks for the corresponding function. There are three common scenarios that will cause the program to crash and which you must avoid:

  • Dividing by zero
  • Accessing memory that you shouldn’t (such as invalid array indices)
  • Infinite loops

Using functions from the standard library

The project.h header file already includes <stdio.h> and <string.h>. You may not use any other functions from the standard library. If you want some functionality, you must code it!

Marking

When you submit project.c for the Style marking deadline (Sunday 22nd October), this file will be marked for style (use of commenting, consistent indentation, good use of additional “helper” functions rather than placing all of the logic in the required functions, etc.) Your code style will be assessed and marked by a teaching assistant.

When you submit project.c for the Correctness marking deadline (Friday 27th October), this file will be marked by a program that calls your functions with lots of different input values. This program will check that your function definitions return the expected outputs for many possible inputs. Your mark will essentially be the total number of these tests that are successful, across all ten tasks.

Some tasks are harder than others. If you are unable to complete a task, that is fine - just complete the tasks that you are able to. However, please do not delete any of the ten functions from the project.c source file. You can simply leave the initial code in the function definition if you choose not to implement it. All ten required functions must be present in the project.c file you submit for marking.

Never crash

There is one thing that you must pay important attention to. Your functions must never cause the testing program to crash. If they do, your will forfeit the marks for that task. This is your responsibility to check. There are three common situations that you must avoid:

  • Never divide by zero
  • Never access any memory location that you shouldn’t (such as an invalid array access)
  • Never have an infinite loop that causes the program to halt

You must guard against these very carefully - regardless of the input values that are passed to your functions. Think very carefully about every array access that you make. In particular, a common error is forgetting to initialise a variable (in which case it will store a “garbage” value), and then using that variable to access a particular index of an array. You cannot be sure what the “garbage” value will be, and it may cause the program to crash.

Array allocation

If you need to declare an array in any of your function definitions (for Tasks 1-9), you can make use of this constant from project.h:

1
#define MAX_ARRAY_SIZE 1000

If you need to declare a 2-dimensional array in Task 10), you can make use of this constant from project.h:

1
#define MAX_MAP_SIZE 100

Comments

You will see in the template project.c source file that on the line above each function definition there is a place-holder comment of the form: / Your comment goes here/

You must replace these place-holders with your own comments, written in your own words. For each function, you must briefly describe the problem that your function is trying to solve (in some sense, this will be a paraphrasing and summarising of the project task description). You must also briefly describe the algorithm that you used in your implementation for each task. You need to communicate your ideas clearly - this is a very important skill. Other than this, try to keep commenting within functions to a minimum.

Task One: “No remainders”

The greatest common divisor (or GCD) of a set of numbers is the largest positive integer that divides all numbers in the set without remainder. Define a function called DivisorOfThree() that is passed three integer inputs. The function must return the GCD of these three numbers. If any of the input numbers is less than or equal to zero, then the function must return -1.

Function prototype declaration

1
int DivisorOfThree(int a, int b, int c)

Assumptions

You cannot assume the inputs are positive. If any input is negative, or equal to zero, then the function must return -1.

Example

1
2
3
printf("GCD = %d\n", DivisorOfThree(1288, 759, 1173));
printf("GCD = %d\n", DivisorOfThree(760, 1960, 2720));
printf("GCD = %d\n", DivisorOfThree(100, 0, 1000000));

Expected output

GCD = 23
GCD = 40
GCD = -1

Task Two: “Counting sheep”

A device has been installed on a gate to count the number of sheep that pass by every hour. The owner of the farm wants to compute the average number of sheep passing each hour. The device provides data in the form of an array, where each element in the array is the number of sheep that were counted in a one hour period. However, the device is not perfectly reliable and sometimes if fails. In such cases, the value -1 will appear in the data rather than an accurate hourly reading. You should ignore these erroneous values when calculating the average. A special value, 9999, is inserted at the end of the list of data values to indicate that there is no more data to process.

Define a function called AverageSheep() that is passed one input: an array of integers containing the count data. The function must calculate the average of all values in the array up to, but excluding, the value 9999 (which indicates the end of the data sequence). You should also ignore any values equal to -1 when performing your calculation. If there are no valid values with which to compute the average, then the function should return 0.0.

Function prototype declaration

1
double AverageSheep(int *counts)

Assumptions

You can assume the array will contain the value 9999 (to indicate the end of the data).

This special value, 9999, may appear anywhere (for example, it may be the first value in the array). If there are no valid data values with which to compute the average, then the function should return 0.0.

Example

1
2
3
4
5
6
7
8
9
int sheep1[MAX_ARRAY_SIZE] = {25, 12, 18, 19, 9999};
int sheep2[MAX_ARRAY_SIZE] = {-1, 25, 12, 18, -1, 9999};
int sheep3[MAX_ARRAY_SIZE] = {-1, 22, 9999, -1, 25, 12};
int sheep4[MAX_ARRAY_SIZE] = {-1, -1, 9999, -1, 25, 12}

printf("Average = %f\n", AverageSheep(sheep1));
printf("Average = %f\n", AverageSheep(sheep2));
printf("Average = %f\n", AverageSheep(sheep3));
printf("Average = %f\n", AverageSheep(sheep4));

Expected output

Average = 18.500000
Average = 18.333333
Average = 22.000000
Average = 0.000000

Task Three: “Emphasise”

Sometimes people use two underscore characters to emphasise certain words within a sentence. For example, consider the following sentence:

This is a _really_ fun project!

In this case, the two underscore characters are used to emphasise the word “really”. Another way that this emphasis could have occurred is using capital letters (instead of the underscore characters):

This is a REALLY fun project!

The advantage of this second approach is that the string is shorter - it uses two fewer characters! Define a function called Emphasise() that is passed one string input. The string will contain exactly two underscore characters. The function should modify the input string by converting all alphabetic characters (i.e. ‘a’-‘z’) between the two underscore characters to upper case. In addition, the underscore characters should no longer appear in the resulting string.

Function prototype declaration:

1
void Emphasise(char* word)

Assumptions

You can assume there will be exactly two underscore characters somewhere in the input string. Only lowercase alphabetic characters (‘a’-‘z’) should be capitalized.

Example

1
2
3
4
5
6
7
8
9
10
11
char wordsA[MAX_ARRAY_SIZE] = "this is a _good_ question!";
char wordsB[MAX_ARRAY_SIZE] = "It is _over 9000_!";
char wordsC[MAX_ARRAY_SIZE] = "_Nothing to see here_";

Emphasise(wordsA);
Emphasise(wordsB);
Emphasise(wordsC);

printf("%s\n", wordsA);
printf("%s\n", wordsB);
printf("%s\n", wordsC);

Expected output

this is a GOOD question!
It is OVER 9000!
NOTHING TO SEE HERE

Task Four: “Prime factors”

The prime factors of a positive integer are the prime numbers that divide that integer exactly. The prime factorisation of a positive integer is a list of all of the integer’s prime factors. For example, the prime factorisation of 234 is: 2, 3, 3 and 13. Every integer has a unique prime factorisation.

Define a function called PrimeFactors() that is passed two inputs: an integer and an array of integers. The function should compute the prime factorisation of the first input, and store each of the prime factors (in increasing order) in consecutive elements of the array. The function should return the number of factors.

Function prototype declaration

1
int PrimeFactors(int n, int *factors)

Assumptions

You can assume the integer input, n, is greater than or equal to 2.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int numFactors, i;
int factors[MAX_ARRAY_SIZE];

printf("Factors of 567: ");
numFactors = PrimeFactors(567, factors);
for (i = 0; i < numFactors; i++) {
printf("%d ", factors[i]);
}

printf("\nFactors of 5678901: ");
numFactors = PrimeFactors(5678901, factors);
for (i = 0; i < numFactors; i++) {
printf("%d ", factors[i]);
}

Expected output

Factors of 567: 3 3 3 3 7
Factors of 5678901: 3 3 17 37117