= You have N cents and m possible coin denominations {S,..., Sm} (say S1 = 1...

 

Transcribed Image Text:

= You have N cents and m possible coin denominations {S₁,..., Sm} (say S1 = 1 cent, S₂ 2 cents, etc.). We want to know in how many ways we can break the N cents into combinations of coins. For example, let S₁ = 1, S₂ 5 and S3 = 10, and N = 10. Then, we have 4 options: (i) 1 coin of 10 cents, (ii) two coins of 5 cents each (iii) 5 coins of 1 cent and 1 coin of 5 cents (iv) 10 coins of one cent. If have only $₁ you 1 and S₂5 (i.e., you are not allowed to use the 10 cents coin) then you have only three options. In this example 75% of the outcomes do not use 10 cents. - - (a) Write a recursion of C(N, m) the number of ways to "build" N cents if you have the denom- inations {S₁,..., Sm}. Code the recursion. Hint 1: Split into combinations that use the denomination Sm and those that do not. Hint 2: Write C(N, m) as a sum C(x, m) + C(N, y), where you have to carefully choose the values x and y such that x ≤ N and y ≤ m. (b) With S₁ (c) What fraction of these uses only 1, 5 and 10 cents denominations? — 1, S2 = 5, S3 = 10, and S4 = 25, how many ways there are to change N = 213 ? (d) Repeat the same for multiple values of N and plot the result to the previous question as a function of N? = You have N cents and m possible coin denominations {S₁,..., Sm} (say S1 = 1 cent, S₂ 2 cents, etc.). We want to know in how many ways we can break the N cents into combinations of coins. For example, let S₁ = 1, S₂ 5 and S3 = 10, and N = 10. Then, we have 4 options: (i) 1 coin of 10 cents, (ii) two coins of 5 cents each (iii) 5 coins of 1 cent and 1 coin of 5 cents (iv) 10 coins of one cent. If have only $₁ you 1 and S₂5 (i.e., you are not allowed to use the 10 cents coin) then you have only three options. In this example 75% of the outcomes do not use 10 cents. - - (a) Write a recursion of C(N, m) the number of ways to "build" N cents if you have the denom- inations {S₁,..., Sm}. Code the recursion. Hint 1: Split into combinations that use the denomination Sm and those that do not. Hint 2: Write C(N, m) as a sum C(x, m) + C(N, y), where you have to carefully choose the values x and y such that x ≤ N and y ≤ m. (b) With S₁ (c) What fraction of these uses only 1, 5 and 10 cents denominations? — 1, S2 = 5, S3 = 10, and S4 = 25, how many ways there are to change N = 213 ? (d) Repeat the same for multiple values of N and plot the result to the previous question as a function of N?

Answer rating: 100% (QA)

a Recursion of CN m The number of ways to build N cents using denominations S1 Sm can be computed recursively as follows 1 If N is 0 there is only one ... View the full answer