# Python代写 | CS 602 Algorithm Design and Implementation

这个Assignment是用Python设计一个硬币找零的算法并编码实现

CS 602

Algorithm Design and Implementation

Assignment 3

[Question 1] Number of ways to make a change

There circulate m kinds of coins in the state of Temapura with denomination of 𝑑1, 𝑑2, … , 𝑑𝑚 in

cents. For example, given coin denominations {1, 2, 5}, the ways to make up n = 7 cents are {1,

1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 2, 1}, {5, 2}, {2, 1, 2, 1, 1}, {1, 5, 1}, {2, 2, 1, 2}, so there are 6 ways

to make up 7 cents. Note that the sequence of coins in each set does not matter, so each set is

considered one way to make up 7 cents. In this question, you are to compute the number of ways

to make a change of n cents given a set of denominations with unlimited supplies.

Inputs begin with a number indicating the number of test cases below. Each test consists of two

lines, where the first line describes the set of denominations and the second line describes the

sequence of changes to be computed. The denominations are all distinct between 1 and 99 both

inclusive, and there are at most 10 denominations in the set. Denominations always contain 1 cent

to ensure all changes can be made. The sequence of changes has a maximum length of 1000, and

the changes are between 1 and 1000. For each test case, output the number of ways to make the

change in the same sequence as the changes are given.

Sample code is provided in the file A3Q1.py. You need to modify the function

num_ways_to_change.

There will be 8 testcases with 1 mark each. The remaining 2 marks are awarded with the correct

justification of the time complexity of your algorithm.

Sample Input

3

1 2 5

7 8 3 8 6 10 6

1 5 4 3

29 25 4 30 20 11 20 9 10

1 5 7 9 3

30 13 20 8 12 10 25 23 13 21 22

Sample Output

6 7 2 7 5 10 5

123 86 3 134 51 14 51 10 12

138 16 45 6 14 10 82 65 16 52 58

[Question 2] Unloading from ships

The state of Temapura is one of the busiest ports for the last 20 years. To keep its competitiveness,

the efficiency of operations is a big concern from the management of the port authority. You are

hired by the management to study how to efficiently unload containers from a ship. Let us make

some simple assumptions:

1. There are multiple stacks of containers on one ship, these stacks are lined up with fixed

distance in between.

2. There are a fixed number of cranes assigned to each ship to unload all containers from a

ship.

3. The cranes can never cross their arms.

4. It takes 2 minutes to unload one container from the stack that is aligned to the crane, for

every stack further from the aligned stack, the crane will take extra 2 minutes to unload.

For example, if a crane is aligned to stack 3, it takes 2 minutes to unload one container in

stack 3, and 6 minutes to unload one container in stack 5 since stack 5 is 2 stacks away

from stack 3.

5. The cranes can move left or right, but it can only stop at the aligned positions or a position

right in the middle of two neighboring stacks. In the second case, to unload from the two

nearest stacks takes 1 extra minute. For example, if a crane is stopped right in the middle

of stack 3 and 4, it takes 3 minutes to unload a container from either stack 3 or stack 4, and

5 minutes to unload a container from either stack 2 or stack 5.

As shown in the picture, the left crane takes charge of 4 stacks of containers and stopped right in

the middle of stack 2 and stack 3. The right crane takes charge of the remaining 6 stacks, and

stopped at the aligned position of stack 7.

Inputs begin with a number indicating the number of lines below. Each line begins with the number

of cranes assigned to the ship, and followed by the number of containers in each stack on a ship.

You need to output the minimum amount of time to unload all containers from the ship in minutes.

Sample code is provided in the file A3Q2.py. You need to modify the function

minimum_duration.

There will be 8 testcases with 1 mark each. The remaining 2 marks are awarded with the correct

justification of the time complexity of your algorithm.

Sample Input

1

2 10 10 7 5 5 9 7 8 10 7

Sample Output

180

Running python skeleton with sample input:

1. Open “Anaconda Prompt”

2. Go to the directory where you put the file A3Q1.py and A3Q1.in, using command cd

3. Run command python A3Q1.py < A3Q1.in

4. You may want to create a test input called my_own_test.in to design a test case for your

own program, the command would then be python A3Q1.py < my_own_test.in

5. Same applies to Question 2, so you may run python A3Q2.py < A3Q2.in