python辅导 | CS 602 Algorithm Design and Implementation

python算法设计与实现

CS 602
Algorithm Design and Implementation
Assignment 2
[Question 1] Metal Melter
A metal recycling company often needs to melt metal blocks of the same type but possibly
different sizes together. Every step, a machine, called metal melter, takes two blocks of the same
type from a pool and puts the melted block back to the pool. The melting processes cost energy,
which is equal to the sum of the weight of the two blocks in the unit of kilojoule. Given a pool of
metal blocks, the machine operator can choose any sequence to melt the blocks and put the
melted block back to the pool, until there is only one block left for each type in the pool. For
example, if a pool of steel blocks of weight 1kg, 2kg and 4kg is given, the operator can choose to
melt 1kg and 2kg first, or to melt 1kg and 4kg first, or to melt 2kg and 4kg first. If he melts 1kg
and 2kg first, 3 kilojoules are spent to produce a 3kg block, and then melts 3kg and 4kg together,
which costs 7 kilojoules. A total of 3 + 7 = 10 kilojoules is spent on this whole process. If he
starts with melting 2kg and 4kg first, the machine spends 6 kilojoules in the first step, and 7
kilojoules in the second step, which gives 13 kilojoules in total. The company would like to
minimize the energy spent in the melting process, the first option is thus chosen. However, they
do not know how to decide on the melting sequence and need your help.
Implement an algorithm with appropriate data structure for the function metal_melter.
Please also state and justify the time complexity of your algorithm as comments in your code.
Test inputs begin with the number of lines. Each line contains a list of integer pairs, the types and
weights of metal blocks separated by ‘:’. The length of each list is between 2 and 5000, weights
are at most 400, and the type indicator of the blocks is between 1 and 50. For each list, output
one single integer indicating the minimum possible amount of energy to spend in kilojoules. You
may import Python libraries which are commonly used, but you are not supposed to ask what the
right library is, as this question tests you on choosing the appropriate data structure.
Sample Input
2
1:2 1:4 1:1
2:6 2:5 1:2 1:4 2:4 2:7
Sample Output
10
50
[Question 2] Mirror a Binary Tree into a Binary Search Tree
In this question, you are asked to convert a binary tree to a binary search tree with the mirrored
structure. A mirrored binary tree of a binary tree is defined as follow: (1) the mirrored binary tree
of the empty tree is the empty tree; (2) the left subtree from its root in a mirrored binary tree is a
mirrored binary tree of its right subtree in the original tree and its right subtree in a mirrored
binary tree is a mirrored binary tree of its left subtree in the original tree. The mirrored binary
search tree of binary tree t is a mirrored binary tree of t and it is a binary search tree.
Please implement the conversion from a binary tree to the mirrored binary search tree. Test
inputs begin with the number of lines below. Each line describes a binary tree by a list of tree
nodes with values at itself, its left child and its right child, separated by ‘:’. Letter x represents a
null node, so a tree node with two x is a leaf node. The sequence of tree nodes is arbitrary. For
example, ‘0:x:x -1:1:-2 -2:0:x 1:x:x’ represents a 4-nodes binary tree rooted at -1, the left child is
1 and the right child is -2, where node 1 is a leaf node. For each binary tree, output the mirrored
binary search tree in pre-order traversal separated by space, ‘0 -2 -1 1’ for the above example.
Sample code is provided in the file A2Q1.py. You need to modify the function mirror_BST.
The maximum of tree height is 100 and the maximum number of nodes in a binary tree is
1,000,000. Values in the tree nodes are integers between -2
31 and 231
-1, and they are distinct.
Please state and justify the time complexity of your algorithm in comments.
Sample Input
Please refer to the file A2Q2.in .
Sample Output
Please refer to the file A2Q2.out .
Running python skeleton with sample input:
1. Open “Anaconda Prompt”
2. Go to the directory where you put the file A2Q1.py and A2Q1.in, using command cd
3. Run command python A2Q1.py < A2Q1.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 A2Q1.py < my_own_test.in
5. Same applies to Question 2, so you may run python A2Q2.py < A2Q2.in