' For the sake of an exercise, we will implement a function that does a kind...

 

Transcribed Image Text:

' 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 L[0] and also use slice notation L[1:] but no other slices. def take(n, L): 'Returns the list L[0: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, 501) [6, [25, 10, 10, 1, 1, 11] >>> giveChange (48, [1, 7, 24, 42)) 12, [24, 2411 >> givechange (35, [1, 3, 16, 30, 50]) 13, (16, 16, 311 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, 31] is the same to us as [3, [3, 16, 16] ] or [3, [16, 3, 16] 1. 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 fom. 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 (numberofCoins, listofcoins] and retum that list. ' 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 L[0] and also use slice notation L[1:] but no other slices. def take(n, L): 'Returns the list L[0: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, 501) [6, [25, 10, 10, 1, 1, 11] >>> giveChange (48, [1, 7, 24, 42)) 12, [24, 2411 >> givechange (35, [1, 3, 16, 30, 50]) 13, (16, 16, 311 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, 31] is the same to us as [3, [3, 16, 16] ] or [3, [16, 3, 16] 1. 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 fom. 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 (numberofCoins, listofcoins] and retum that list.

Answer rating: 100% (QA)

Consider an Example In 1 giveChange48 15102550 Out1 6 251010111 In 2 giveChange48 172442 Out 2 2 242... View the full answer