Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

HW 6 - More Recursion

Making Change

At this point in the semester you should be able to attempt a HW without st arter code.

This Homework will give you more practice on coming up with recursive solutions whic h will help you work with Grapsh/Networks and Trees.

Imagine that you just got a job working for a company that builds electronic cash      registers and the software that controls them. The cash registers are used all around the world, in countries with many different coin systems.

Next, imagine that we are given a list of the coin types in a given country. For example, in the U.S. the coin types are:

and in Europe they are:

But in the Kingdom of Shmorbodia, the coin types are:

In general, the coin system could be anything, except that there is always a 1-unit coin (penny). In these examples, we gave the denominations f rom smallest to largest, but that's not always necessarily the case. There's nothing about use-it-or- lose-it that depends on the order of the coins.

Here's the problem: given an amount of money and a list of coin types, we would like to fi nd the smallest number of coins that makes up that amount of money. For example, in the U.S. system, if we want to make 48 cents, we give out 1 quarter, 2 dimes, and 3 pennies. That solution uses 6 coins, whic h is the best we can do for this case. Making 48 cents in the Shmorbodian system, however, is different . Giving out  a 42-cent coin—albeit tempting—will force us to give the remaining balance with 6 pennies, using a tot al of 7 coins. We could do better by simply giving two 24-cent coins.

Your fi rst task is to write a function called c hange(amount, coins), where amount is a non-negative integer indicating the amount of c hange to be made and coins is a list of coin values. The function should return a non-negative integer indicating the minimum number of coins required to make up the given amount .

Here is an example of this function in action:

In the last case, the function returns the special number "inf", meaning infi nity, to indicate that c hange can't be made for that amount (because there is no 1-unit coin). See below for more on this case.

A few notes and tips…

Not surprisingly, the secret to all happiness is to use the use-it-or-lose-it recursion strategy.

Second, you may want to use the built-in function min (x, y), whic h returns the smaller of its two arguments.

Third, in the event that c hange is confronted with a problem for whic h there is no    solution, returning an infi nite value is an appropriate way to indicate that there is no number of coins that would work. This happens, for example, when we are asked to make change for some positive amount of money but there are no coins in the list .   What is infi nity in Python? In c lass, we saw one way to do this: First, import the math package:

this way...

...then you would access infi nity with math .inf . Finally, if you don't import the math

package at all, you can still get infi nity in this slightly weird way: float('inf').

Giving Change

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, whic h takes the same arguments as change but returns a list whose fi rst member is the minimum number of coins and whose second member is a list of the coins in that optimal solution. We sometimes call such a list a "care package" because it packages up all the information you need to know about a given solution, including  the information needed to use that solution in developing a more complex one! Here's an example:

The order in whic h the coin values are presented in the original list doesn't matter, and similarly, the order in whic h your solution reports the coins to use is also

unimport ant : In other words the solution is the same to us as

[3 ,   [3 ,  16 ,  16]  ] or [3 ,   [16 ,  3 ,  16]] . After all, all of these solutions use the same three coins!

Here are a few observations to keep in mind. First, while it may be tempting to have

change f unction, this is

function.

Note that                      will always return a list of the form [ numberOfCoins,

listOfCoins]. So, if your original              function returned 0, for example, then your

new                      function would probably return                instead to indicate that

there are zero coins of c hange and the list of coins is the empty list!

Now, use your              function as a guide to write your                      function, but

keep in mind that every time              would have returned a number (a number of

coins), your new                      function will return a list of the form [ numberOfCoins,

listOfCoins]. You will have to "t ake apart" that list so that you can work with its individual components, and then put it back together to get your fi nal result .

Submit

Submit your file as `hw6.py