Skip to content

Problem 4: Count change (200pts)

Problem

Denomination is a proper description of a currency amount, usually for coins or banknotes. For example, we have 1-Yuan coins and 100-Yuan bills in Chinese Yuan.

A currency system can be described by a special function that takes in an argument ith and returns the ith largest denomination in that currency system. For example, the following money function describes Chinese Yuan (100-Yuan, 50-Yuan, 20-Yuan, 10-Yuan, 5-Yuan and 1-Yuan). chinese_yuan(2) returns 50 as 50-Yuan is the second-largest denomination. chinese_yuan(1) returns 100 as 100-Yuan is the largest denomination.

When ith does not correspond to any denomination, money function returns None. For example, chinese_yuan(7) yields None since there are only 6 distinct denominations in Chinese Yuan.

面额是对货币金额的恰当描述，通常用于硬币或纸币。 例如，在中国人民币中，我们有 1 元硬币和 100 元纸币。

一个货币系统可以用一个特殊的函数来描述，该函数接受一个参数 ith 并返回该货币系统中第 ith 大的面额。 例如，下面的货币函数描述了中国人民币（100 元、50 元、20 元、10 元、5 元和 1 元）。 chinese_yuan(2) 返回 50，因为 50 元是第二大的面额。 chinese_yuan(1) 返回 100，因为 100 元是最大的面额。

当 ith 不对应任何面额时，货币函数返回 None。 例如，chinese_yuan(7) 返回 None，因为中国人民币中只有 6 种不同的面额。

def chinese_yuan(ith):
    if ith == 1:
        return 100
    if ith == 2:
        return 50
    if ith == 3:
        return 20
    if ith == 4:
        return 10
    if ith == 5:
        return 5
    if ith == 6:
        return 1

Given an amount of money total and a currency system, a set of banknotes (coins) makes change for total if sum of their values is exactly total. For example, the following sets make change for 15 Chinese Yuan:

  • 15*1-Yuan
  • 10*1-Yuan + 1*5-Yuan
  • 5*1-Yuan + 2*5-Yuan
  • 5*1-Yuan + 1*10-Yuan
  • 3*5-Yuan
  • 1*5-Yuan + 1*10-Yuan

Thus, there are 6 different ways to make change for 15 Chinese Yuan.

Write a recursive function count_change that takes a positive integer total and a money function money and returns the number of ways to make change for total under the currency system described by money.

给定一个货币总额 total 和一个货币系统，如果一组纸币（硬币）的面额总和恰好等于 total，那么这组纸币（硬币）就构成了 total 的找零组合。例如，以下集合构成了 15 中国人民币的找零组合：

  • 15 个 1 元
  • 10 个 1 元 + 1 个 5 元
  • 5 个 1 元 + 2 个 5 元
  • 5 个 1 元 + 1 个 10 元
  • 3 个 5 元
  • 1 个 5 元 + 1 个 10 元

因此，用中国人民币为 15 元找零共有 6 种不同的方法。

编写一个递归函数 count_change，它接受一个正整数 total 和一个货币函数 money，并返回在由 money 所描述的货币系统中为 total 找零的方法数量。

def count_change(total, money):
    """Return the number of ways to make change for total,
    under the currency system described by money.

    >>> def chinese_yuan(ith):
    ...     if ith == 1:
    ...         return 100
    ...     if ith == 2:
    ...         return 50
    ...     if ith == 3:
    ...         return 20
    ...     if ith == 4:
    ...         return 10
    ...     if ith == 5:
    ...         return 5
    ...     if ith == 6:
    ...         return 1
    >>> def us_cent(ith):
    ...     if ith == 1:
    ...         return 25
    ...     if ith == 2:
    ...         return 10
    ...     if ith == 3:
    ...         return 5
    ...     if ith == 4:
    ...         return 1
    >>> count_change(15, chinese_yuan)
    6
    >>> count_change(49, chinese_yuan)
    44
    >>> count_change(49, us_cent)
    39
    >>> count_change(49, lambda x: 2 ** (6 - x) if x <= 6 else None)
    692
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(HW_SOURCE_FILE, 'count_change', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"

Hints

  • Hint: Refer to the implementation of count_partitions for an example of how to count the ways to sum up to a total with smaller parts. If you need to keep track of more than one value across recursive calls, consider writing a helper function and pass around the intermediate values as the arguments of the helper function.

  • 请参阅 count_partitions 的 实现，了解如何计算用较小的部分相加得到总和的方法数。如果你需要在递归调用中跟踪多个值，请考虑编写一个辅助函数，并将中间值作为辅助函数的参数传递。

  • 你可能需要一个辅助函数来实现递归，增加的参数可以是 ith。

Solutions

目标是用给定的币种凑出所需的金额。

对每一个币值，我们都需要做出一个选择：

  1. 不使用这个币值，那么跳转到下一个币值。注意判断还是否存在下一种币值。
  2. 使用这个币值，那么我们剩余要凑的总金额会减小。

把这两种情况所有的方法数加起来，这样便开始了递归。

为了记录我们当前使用的币值，最好使用一个辅助函数，同时记录剩余的金额。

注意判断币值是否存在可以使用 if money(ith) is None。

def count_change(total, money):
    def helper(total, ith):
        # 当正好凑齐时，计入这个方法
        if total == 0:
            return 1
        # 当凑出的金额超过总金额，或是已经用了所有的币值，我们可以放弃这个方法
        if total < 0 or money(ith) is None:
            return 0
        # 总方法数 = (不使用当前币种的方法数) + (至少使用一个当前币种的方法数)
        return helper(total, ith + 1) + helper(total - money(ith), ith)
    # 从第一种币值开始，计算全部方法数
    return helper(total, 1)