COMP SCI

PYTHON 3

PROBLEM 2 For the sake of an exercise, we will implement a function that does a kind of slice. You must use recursion for this one. Your code is allowed to refer to list index L0] and also use slice notation L[1:] but no other slices. def take(n, L): 'Returns the list LI0:n."" return L[0]] take(n, L[1:]) print(take(4, [1,8,2,3,4,5])) Just knowing the minimum number of coins is not as useful as getting the actual list of coins. Next, write another version of the change function called giveChange that takes the same kind of input as change but returns a list whose first item is the minimum number of coins and whose second item is a list of the coins in that optimal solution. Here's an example >>>giveChange (48, [1, 5, 10, 25, 50]) [6, [25, 10, 10, 1, 1, 11 >>>giveChange (48, [1, 7, 24, 42]) 2, [24, 24]] >>>giveChange (35, [1, 3, 16, 30,50]) [3, [16, 16, 3]] The order in which the coins are presented in the input list doesn't really matter and, similarly, the order in which your solution reports the coins to use is also unimportant: In other words the solution [3, [16 16, 3] is the same to us as [3, [3, 16, 16 or [3, 116, 3, 161.All of these solutions use the same 3 coins after all! This problem may seem challenging at first, but keep in mind that once you establish that giveChange will always return a list of the form [numberOfCoins, listofcoins], you can modify your change function relatively modestly to get the giveChange function. First, your base cases must observe the convention and return such a list of the form [numberofCoins, listofCoins]. Then, when you call giveChange recursively, remember that it is returning a list of this form. Your function will need to pick apart that list to get at the number of coins and the list of coins in that solution Finally, after deciding whether the use-it or lose-it solution is better, you can prepare your list of the form [numberof Coins, listofCoins] and retum that list