0

我必须编写一个使用递归生成列表的代码，但列表中的最后一项必须为空。这是我的代码，我需要它来生成与它实际生成的内容。

def coin_change(avail_change, total_cents):
    if avail_change == []:
        return []
    if total_cents // avail_change[0] >= 1:
        first = total_cents // avail_change[0]
        first_list = [avail_change[0], first]
        return [first_list, coin_change(avail_change[1:], (total_cents - (avail_change[0] * first)))]
    else:
        return coin_change(avail_change[1:], total_cents)

结果：

coin_change([50,5,1],108) => [[50,2],[5,1],[1,3]]
expected [[50, 2], [5, 1], [1, 3]], saw [[50, 2], [[5, 1], [[1, 3], []]]]

我需要让列表结束，[1,3]但我不知道该怎么做。

4

4 回答 4

1

当你使用递归时，首先考虑你的基本情况是什么，以及它是如何与前面的调用相结合的。在这个问题中，如果你这样做了，return [first_list, ...那么你就是在嵌套结果。取而代之的是，您必须在同一个列表中插入新结果。

def coin_change(avail_change, total_cents):
    if not avail_change:
        return []
    else:
        first = total_cents // avail_change[0]
        result = coin_change(avail_change[1:], (total_cents % avail_change[0]))
        if first > 0:
            result.insert(0, [avail_change[0], first])
        return result

print coin_change([50,5,1],108) # [[50, 2], [5, 1], [1, 3]]
于 2013-03-17T20:52:53.450 回答
0

您为每个递归调用返回一个列表，因此结果是越来越嵌套的列表之一。

您还应该返回二元组而不是列表。列表旨在可变且非固定长度，但您的（面额，计数）对都不是。

另外，只是为了好玩， 的输出是coin_change([3,2],16)什么，您期望它是什么？

于 2013-03-17T20:48:01.247 回答
0 
first_list = []


def coin_change(avail_change, total_cents):
    if not avail_change:
        return []

    if total_cents // avail_change[0] >= 1:
        first = total_cents // avail_change[0]
        first_list.append([avail_change[0], first])
        coin_change(avail_change[1:], (total_cents - (avail_change[0] * first)))

    else:
        coin_change(avail_change[1:], total_cents)

    return first_list

x = coin_change([50, 5, 1], 108)
print x

结果：
[[50, 2], [5, 1], [1, 3]] 如你所愿

x = coin_change([ ], 108) 打印 x

输出 [ ]

于 2013-03-17T21:08:55.977 回答
0

这可能会有所帮助：

coins = []
def coin_change(avail_change, total_cents):
    if avail_change == []:
        raise Exception()
    if total_cents // avail_change[0] >= 1:
        first = total_cents // avail_change[0]
        first_list = [avail_change[0], first]
        coins.append(first_list)
        try:
            return coin_change(avail_change[1:], (total_cents - (avail_change[0] * first)))
        except:
            return coins
    else:
        try:
            return coin_change(avail_change[1:], total_cents)
        except:
            return coins

结果：

>>> coin_change ([50,5,1], 108)
[[50, 2], [5, 1], [1, 3]]
于 2013-03-17T22:17:41.157 回答