python递归做1元钱换零钱

给定足够的 5角，2角，1角，5分，2分，1分这六种零钱,将1元(100)换成零钱,一共有多少种换法?

def split(n,j):
	v=[50,20,10,5,2,1]
	if n<0:
		return 0
	if n==0:
		return 1
	if j<0:
		return 0
	return split(n,j-1)+split(n-v[j],j)

 

执行：

>>> split(100,5)
4562
>>> 

 

    可以看到具体方案的方法：

def split(n,j,result):
	v=[50,20,10,5,2,1]
	if n<0:
		return 0
	if n==0:
		print "方案："+result
		return 1
	if j<0:
		return 0
	return split(n,j-1,result)+split(n-v[j],j,result+str(v[j])+"|")

执行（以1角为例）：

>>> split(10,5,"")
方案：10|
方案：5|5|
方案：2|2|2|2|2|
方案：1|2|2|5|
方案：1|1|2|2|2|2|
方案：1|1|1|2|5|
方案：1|1|1|1|2|2|2|
方案：1|1|1|1|1|5|
方案：1|1|1|1|1|1|2|2|
方案：1|1|1|1|1|1|1|1|2|
方案：1|1|1|1|1|1|1|1|1|1|
11
>>>

  

 

over

评论

1 楼 wenxiang_tune 2009-09-04