Skip to content

Problem 3.3: Count Coins Tree (200 pts)

Problem

Nolan wants to help his friends learn tree recursion! They don't really understand all the recursive calls and how they work, so Nolan decides to generate a tree to show the recursive calls in a tree recursion. As a demonstration, he picks the count_coins problem, which is a simplified version of count_change problem in hw03. The following code is his implementation of count_coins problem.

Nolan 想帮助他的朋友学习树递归！他们不太理解所有的递归调用以及它们是如何工作的，所以 Nolan 决定生成一个树来展示树递归中的递归调用。作为演示，他选择了 count_coins 问题，这是 hw03 中 count_change 问题的简化版本。以下是他对 count_coins 问题的实现。

def count_coins(total, denominations):
    """
    Given a positive integer `total`, and a list of denominations,
    a group of coins make change for `total` if the sum of them is `total` 
    and each coin is an element in `denominations`.
    The function `count_coins` returns the number of such groups. 
    """
    if total == 0:
        return 1
    if total < 0:
        return 0
    if len(denominations) == 0:
        return 0
    without_current = count_coins(total, denominations[1:])
    with_current = count_coins(total - denominations[0], denominations)
    return without_current + with_current

Implement count_coins_tree, which takes in a non-negative integer total and a list denominations, and returns a tree representing the recursive calls of count_coins.

Since the recursive tree is usually huge, Nolan decides to include only the recursive calls that eventually lead to a valid way of making change.

The leaves of tree count_coins_tree(15, [1, 5, 10, 25]) are listed below:

  • 15 1-cent coins
  • 10 1-cent, 1 5-cent coins
  • 5 1-cent, 2 5-cent coins
  • 5 1-cent, 1 10-cent coins
  • 3 5-cent coins
  • 1 5-cent, 1 10-cent coin

Note: The label of the tree should be a string.

实现 count_coins_tree，它接受一个非负整数 total 和一个列表 denominations，并返回一个树，表示 count_coins 的递归调用。

由于递归树通常很大，Nolan 决定只包含最终导致有效找零方式的递归调用。

树 count_coins_tree(15, [1, 5, 10, 25]) 的叶子如下：

  • 15 个 1 美分硬币
  • 10 个 1 美分、1 个 5 美分硬币
  • 5 个 1 美分、2 个 5 美分硬币
  • 5 个 1 美分、1 个 10 美分硬币
  • 3 个 5 美分硬币
  • 1 个 5 美分、1 个 10 美分硬币

注意：树的标签应该是一个字符串。

def count_coins_tree(total, denominations):
    """
    >>> count_coins_tree(1, []) # Return None since there is no way to make change with empty denominations
    >>> t = count_coins_tree(3, [1, 2]) 
    >>> print(t) # 2 ways to make change for 3 cents
    3, [1, 2]
      2, [1, 2]
        2, [2]
          1
        1, [1, 2]
          1
    >>> # 6 ways to make change for 15 cents
    >>> t = count_coins_tree(15, [1, 5, 10, 25]) 
    >>> print(t)
    15, [1, 5, 10, 25]
      15, [5, 10, 25]
        10, [5, 10, 25]
          10, [10, 25]
            1
          5, [5, 10, 25]
            1
      14, [1, 5, 10, 25]
        13, [1, 5, 10, 25]
          12, [1, 5, 10, 25]
            11, [1, 5, 10, 25]
              10, [1, 5, 10, 25]
                10, [5, 10, 25]
                  10, [10, 25]
                    1
                  5, [5, 10, 25]
                    1
                9, [1, 5, 10, 25]
                  8, [1, 5, 10, 25]
                    7, [1, 5, 10, 25]
                      6, [1, 5, 10, 25]
                        5, [1, 5, 10, 25]
                          5, [5, 10, 25]
                            1
                          4, [1, 5, 10, 25]
                            3, [1, 5, 10, 25]
                              2, [1, 5, 10, 25]
                                1, [1, 5, 10, 25]
                                  1
    """
    "*** YOUR CODE HERE ***"

Hints

Hint1: The implementation of count_coins_tree will follow a similar logic to count_coins defined above.

Hint2: Return None if it's no way to make change, but do not include None in the tree.

  • count_coins_tree 的实现将遵循上面定义的 count_coins 的类似逻辑。

  • 如果没有找零方式，则返回 None，但不要在树中包含 None。