a) Consider the coins 1, 5, 10, 25 and an integer x. We want to find the least n

Question

a) Consider the coins 1, 5, 10, 25 and an integer x. We want to find the least number of coins of the type above whose sum is x. For example for x = 67, the solution 25, 25, 10, 5, 1, 1 is the best answer and the minimum number of coins is 6. Consider the following method. Let x be the number to be exchanged. If x=0, we stop. Otherwise as long as x>= 25, take a 25 coin and add to the solution and set x=x-25. Then as long as 25>x>=10, add a coin of 10 to the solution and set x=x-10. Then as long as 10>x>=5, add a coin of 5 to the solution and set x=x-5. And finally if x<5, add x coins of 1 to the solution and x=x-1. Show that this strategy always gives the least number of coins for any x. And what if the coins are 11, 5, 1. Would the strategy work also?

Explanation / Answer

Yes

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.