A set of coins makes change for n if the sum of the values of the coins is n. For example, if you have 1- cent, 2-cent and 4-cent coins, the following sets make change for 7: . 71-cent coins 5 1-cent, 1 2-cent coins. 31-cent, 2 2-cent coins 31-cent, 1 4-cent coins 11-cent, 3 2-cent coins 11-cent, 1 2-cent, 1 4-cent coins Thus, there are 6 ways to make change for 7. Write a function count_change that takes a positive integer n and a list of the coin denominations and returns the number of ways to make change for n using these coins (Hint: You will need to use tree recursion):
A set of coins makes change for n if the sum of the values of the coins is n. For example, if you have 1- cent, 2-cent and 4-cent coins, the following sets make change for 7: . 71-cent coins 5 1-cent, 1 2-cent coins. 31-cent, 2 2-cent coins 31-cent, 1 4-cent coins 11-cent, 3 2-cent coins 11-cent, 1 2-cent, 1 4-cent coins Thus, there are 6 ways to make change for 7. Write a function count_change that takes a positive integer n and a list of the coin denominations and returns the number of ways to make change for n using these coins (Hint: You will need to use tree recursion):
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
![A set of coins makes change for n if the sum of the values of the coins is n. For example, if you have 1-
cent, 2-cent and 4-cent coins, the following sets make change for 7:
• 7 1-cent coins
. 51-cent, 1 2-cent coins
3 1-cent, 2 2-cent coins
3 1-cent, 1 4-cent coins
.
11-cent, 3 2-cent coins
. 1 1-cent, 1 2-cent, 1 4-cent coins
Thus, there are 6 ways to make change for 7. Write a function count_change that takes a positive integer
n and a list of the coin denominations and returns the number of ways to make change for n using these
coins (Hint: You will need to use tree recursion):
def count_change (amount, denominations):
"""Returns the number of ways to make change for amount.
>>> denominations = [50, 25, 10, 5, 1]
>>> count_change (7, denominations).
2
>>> count_change (100, denominations)
292
>>> denominations = [16, 8, 4, 2, 11
>>> count_change (7, denominations)
6
>>> count_change (10, denominations)
14
>>> count_change (20, denominations)
60
||||||
"*** YOUR CODE HERE ***"
Ĵ](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fc32a25d1-aced-4632-8199-60cb873673c0%2Fb6de69a9-4740-427b-ba37-9442f77b2c96%2Frbpqfmn_processed.jpeg&w=3840&q=75)
Transcribed Image Text:A set of coins makes change for n if the sum of the values of the coins is n. For example, if you have 1-
cent, 2-cent and 4-cent coins, the following sets make change for 7:
• 7 1-cent coins
. 51-cent, 1 2-cent coins
3 1-cent, 2 2-cent coins
3 1-cent, 1 4-cent coins
.
11-cent, 3 2-cent coins
. 1 1-cent, 1 2-cent, 1 4-cent coins
Thus, there are 6 ways to make change for 7. Write a function count_change that takes a positive integer
n and a list of the coin denominations and returns the number of ways to make change for n using these
coins (Hint: You will need to use tree recursion):
def count_change (amount, denominations):
"""Returns the number of ways to make change for amount.
>>> denominations = [50, 25, 10, 5, 1]
>>> count_change (7, denominations).
2
>>> count_change (100, denominations)
292
>>> denominations = [16, 8, 4, 2, 11
>>> count_change (7, denominations)
6
>>> count_change (10, denominations)
14
>>> count_change (20, denominations)
60
||||||
"*** YOUR CODE HERE ***"
Ĵ
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education