这是一篇来自澳洲的作业3的python代写

Learning Outcomes

This assignment achieves the Learning Outcomes of:

• 1) Analyse general problem solving strategies and algorithmic paradigms, and apply them to solving new problems;

• 2) Prove correctness of programs, analyse their space and time complexities;
• 3) Compare and contrast various abstract data types and use them appropriately;
• 4) Develop and implement algorithms to solve computational problems.

In addition, you will develop the following employability skills:

• Text comprehension.
• Designing test cases.
• Ability to follow specififications precisely.

Assignment timeline

In order to be successful in this assessment, the following steps are provided as a suggestion.

This is an approach which will be useful to you both in future units, and in industry.

Planning

1. Read the assignment specifification as soon as possible and write out a list of questions you have about it.

2. Clarify these questions. You can go to a consultation, talk to your tutor, discuss the tasks with friends or ask in the forums.

3. As soon as possible, start thinking about the problems in the assignment.

• It is strongly recommended that you do not write code until you have a solid feeling for how the problem works and how you will solve it.

4. Writing down small examples and solving them by hand is an excellent tool for coming to a better understanding of the problem.

• As you are doing this, you will also get a feel for the kinds of edge cases your code will have to deal with.

5. Write down a high-level description of the algorithm you will use.
6. Determine the complexity of your algorithm idea, ensuring it meets the requirements.

Implementing

1. Think of test cases that you can use to check if your algorithm works.

• Use the edge cases you found during the previous phase to inspire your test cases.
• It is also a good idea to generate large random test cases.
• Sharing test cases is allowed, as it is not helping solve the assignment.

2. Code up your algorithm (remember decomposition and comments), and test it on the tests you have thought of.

3. Try to break your code. Think of what kinds of inputs you could be presented with which your code might not be able to handle.

• Large inputs
• Small inputs
• Inputs with strange properties
• What if everything is the same?
• What if everything is difffferent?
• etc…

Before submission

• Make sure that the input/output format of your code matches the specifification.
• Make sure your fifilenames match the specifification.
• Make sure your functions are named correctly and take the correct inputs.
• Make sure you zip your fifiles correctly (if required).

Documentation

For this assignment (and all assignments in this unit) you are required to document and comment your code appropriately. Part of the marks of each question are for documentation. This documentation/commenting must consist of (but is not limited to):

• For each function, high-level description of that function. This should be a two or three sentence explanation of what this function does and the approach undertaken within the function.

• For each function, specify what the input to the function is, and what output the function produces or returns (if appropriate).

• For each function, the appropriate Big-O or Big-Θ time and space complexity of that function, in terms of the input size. Make sure you specify what the variables involved in your complexity refer to. Remember that the complexity of a function includes the complexity of any function calls it makes.

• Within functions, comments where appropriate. Generally speaking, you would comment complicated lines of code (which you should try to minimise) or a large block of code which performs a clear and distinct task (often blocks like this are good candidates to be their own functions!).

A suggested function documentation layout would be as follows:

def my_function(argv1, argv2):

“””

High level description about the functiona and the approach you have undertaken.

:Input:

argv1:

argv2:

:Output, return or postcondition:

:Time complexity:

:Aux space complexity:

“””

# Write your codes here.

1 Sharing the Meals

(10 marks)

You and your 4 housemates eat breakfast and dinner together every day, and share the load of preparing the meals.

Now it is time for preparing the schedule of who is responsible for preparing each meal in the next n days (numbered 0, 1, . . . , n − 1). Ideally, the fifive of you would like to divide the task in such a way that each meal is assigned to one person, no person is assigned to prepare both meals of the same day, and each person is assigned to exactly 2n/5 meals (so that the load is perfectly distributed among you).

However, there are some complications:

• Perhaps, 2n/5 is not an integer number.
• You all have busy schedules and only have time availability to prepare meals on specific times.

To solve the problem, you initially collected the data about the time availability of each person.

The fifive persons will be numbered 0, 1, 2, 3, 4. You get as input a list of lists availability.

For a person numbered j and day numbered i, availability[i][j] is equal to:

• 0, if that person has neither time availability to prepare the breakfast nor the dinner during that day.

• 1, if that person only has time availability to prepare the breakfast during that day.
• 2, if that person only has time availability to prepare the dinner during that day.
• 3, if that person has time availability to prepare either the breakfast or the dinner during that day.

After some conversations, you agree that a perfect allocation might not be possible, and someone might have to prepare more meals than others. Moreover, you realised that you might have to order some meals from a restaurant. Nevertheless, you want to achieve a fair distribution and not order many meals from restaurants, so you agreed on the following constraints:

• Every meal is either allocated to exactly one person or ordered from a restaurant.
• A person is only allocated to a meal for which s/he has time availability to prepare.
• Every person should be allocated to at least b 0.36nc and at most d 0.44ne meals.
• No more than b 0.1nc meals should be ordered from restaurants.
• No person is allocated to both meals of a day. There are no restrictions on ordering both meals of a day if the other constraints are satisfified.

As the computer scientist in the house, your housemates asked you to design a program to do the allocation. And your housemates are fifine with any allocation you give to them (even if it favours you) as long as it satisfy the constraints above!

To solve this problem, you should write a function allocate(availability) that returns:

• None (i.e., Python NoneType), if an allocation that satisfy all constraints does not exist.
• Otherwise, it returns (breakfast, dinner), where lists breakfast and dinner specify a valid allocation. breakfast[i] = j if person numbered j is allocated to prepare breakfast on day i, otherwise breakfast[i] = 5 to denote that the breakfast will be ordered from a restaurant on that day. Similarly, dinner[i] = j if person numbered j is allocated to prepare dinner on day i, otherwise dinner[i] = 5 to denote that the dinner will be ordered from a restaurant on that day.

1.1 Example

Consider the following example in which the function returns one valid allocation for the specifified input.

# Example

availability = [[2, 0, 2, 1, 2], [3, 3, 1, 0, 0],

[0, 1, 0, 3, 0], [0, 0, 2, 0, 3],

[1, 0, 0, 2, 1], [0, 0, 3, 0, 2],

[0, 2, 0, 1, 0], [1, 3, 3, 2, 0],

[0, 0, 1, 2, 1], [2, 0, 0, 3, 0]]

>>> allocate(availability)

([3, 2, 1, 4, 0, 2, 3, 2, 2, 3], [4, 0, 3, 2, 5, 4, 1, 1, 3, 0])

Note that are other possible allocations for this specifific input. It is fifine to return any of the allocations that satisfy all constraints! For the curious ones: in every valid solution for this example there is one meal that is ordered from a restaurant.