您好,欢迎来到三六零分类信息网!老站,搜索引擎当天收录,欢迎发信息
免费发信息
三六零分类信息网 > 延边分类信息网,免费分类信息发布

趣味Python-每周一题20170831-兑换零钱

2023/2/6 17:49:56发布53次查看
假设你手上有money这么多的钱,到货币兑换点,有面值为coins的list供你选择,money是int,coins也由int组成。问:能有多少种兑换方法?
如:有0元,有[2,5,7]可以换 ,能有0种方法换;
有5元,有[2,5]可以换,能有1种方法换;
有5元,有[]可以换,能有0种方法换;
有5元,有[1,2]可以换,能有3种方法换:(1,1,1,1,1),(1,1,1,2),(1,2,2)
验证示例
count_change(5,[1,2]) # 3
count_change(100, [5,3,7,11,2]) # 3022
count_change(1000, [5,3,7,2]) # 814044
代码(以下将先放最慢的代码,最后放快的)
这种方法最慢
def count_change(money,coins):
par = [money//i + 1 for i in coins]
f = lambda a,b:a*b
tol = reduce(f,par)
c = 0
for i in range(tol):
s = sum([coins[j]*((i//reduce(f,par[j+1:])%par[j]))
for j in range(len(coins)-1)])
s += coins[-1]*(i%par[-1])
if s == money:
c += 1
return c
这种方法模仿迷宫深度优先算法,但小于目标的实在不需要算,拖慢速度
def count_change3(money,coins):
coins.sort(reverse=true)
lenlst = len(coins)
solutions = []
subso = []
subso.append(coins.copy())
while subso:
while sum([i[-1] for i in subso]) = subso[-1][-1]])
temp = [i[-1] for i in subso]
if sum(temp) == money:
solutions.append(temp)
subso[-1].pop()
try:
while not subso[-1]:
subso.pop()
if subso:
if subso[-1]:
except indexerror:
continue
return len(solutions)
这种方法,利用整体思想,传参递归
def count_change(money, coins):
if money0 and not coins:
return count_change(money-coins[-1],coins) + count_change(money,coins[:-1])
这种方法直接建立缓存,算每种求和的换法总数
a = [1] + [0]*money
for c in coins:
a = [sum(a[:k+1][::-c]) for k in range(money+1)]
return a[-1]
延边分类信息网,免费分类信息发布

VIP推荐

免费发布信息,免费发布B2B信息网站平台 - 三六零分类信息网 沪ICP备09012988号-2
企业名录