辅导案例-FIT1045/53

FIT1045/53 Algorithmic Problem Solving – Workshop 10. Objectives The objectives of this workshop are: • To understand the uses of stacks. • To practice using backtracking to solve problems. MARKS: You must follow all restrictions outlined to receive any marks. Assuming restrictions are followed, marks for this workshop will be determined by the tester. Preparation Revise backtracking and stacks, as discussed in the lectures. Task 0 Download test files and create Python file Name Python file FIT1045 workshop10.py. Task 1: Using Stacks Write a function reduce(stack) that takes as input a stack of integers and returns the length of a reduction of the stack. To reduce the stack, you may remove pairs of adjacent numbers as they occur (they need not be adjacent in original list). For example, calling reduce([5,3,4,2,2,4,5]) would return 3 because of the following operations: • [5,3,4,2,2,4,5] remove the two 2s • [5,3,4,4,5] remove the two 4s • [5,3,5] nothing else can be removed, return the length of the stack You must only use stack operations in this task (i.e. when manipulating the list, you may use pop() and append()). Task 2: Backtracking In the lectures you were given the following code: def solutions(completed, options, partial=[]): #function code from FIT1045 Lecture 17, slide 42 if completed(partial): return [partial] else: res = [] for o in options(partial): augmented = partial+[o] res += solutions(completed, options, augmented) return res 1 def backtracking_task(x): def options(partial): … def completed(partial): … return solutions(completed, options, starting_partial) This code provides a framework for many (although not all) of the backtracking problems you will see in this unit; however, you may not fully understand everything it does. Ensure you understand what each line of code is doing before you implement it. Remember, if you use code from the lectures you must cite it. It is sufficient to include a comment such as #code for < function > adapted from Lecture #, slide #. Part A – Palindromic Bitlists Write a function palindrome binary(n) which returns a list of bitlists of length n, where every bitlist is a palindrome. The returned list of bitlists must be in lexicographical order (think about the order of your options). You must use backtracking to solve this problem (i.e. do not use brute force). Part B – All Paths Write a function all paths(M, u, v) which takes as input an adjacency matrix of a graph, M, and two vertices u, v and returns a list of all paths from u to v in M. A path is a list of vertices. Note that a path cannot use the same vertex twice, but two different paths can use some of the same vertices. The returned list of paths must be in lexicographical order. You must use backtracking to solve this problem (i.e. do not use brute force). Part C – Stairs Write a function stairs(staircase) which takes information regarding a staircase, and returns the number of different ways it is possible to climb the staircase. The function must: • take a bitlist of length ≥ 2 representing a staircase as input. • the first and last elements of the staircase are always 1, as they represent the start and finish points. • elements in staircase that are not the first and last may be 0 or 1, where 0 represents an unsafe stair, and 1 a safe stair. • it is possible to climb the staircase by jumping one step, two steps, or three steps; but it is not possible to jump the same number of steps twice in a row. Example: calling stairs([1,1,0,1,1]) returns 3 as it is possible to jump start-first-third-final, start-first- final, or start-third-final. Calling stairs([1,0,1,0,1]) returns 0 as it is not possible to climb the staircase, given the restrictions. You must use backtracking to solve this problem (i.e. do not use brute force). [Extension] Task 3: Converting Numbers Write a function convert(a, b, c) which takes three positive integers, a, b, and c, and returns the fewest number of operations needed to convert a to b. There are three permitted operations: • a -= 1 • a -= 2 • a *= c Example: calling convert(3,20,2) returns 4 as a can be converted to b using the following (minimum) series of operations : • a = a*2 • a = a-1 2 • a = a*2 • a = a*2 thus, a == 20 == b This problem can be solved using backtracking. However, you will find that if you try to use the backtracking framework given to you in lectures, you will always get a stack-overflow error (think about why this might be by drawing out the trace tree). You will need to come up with a different way of utilising the strengths of backtracking. 3