鱼C论坛Python精英挑战赛（第三季03期）

jerryxjr1220

第三届鱼C论坛精英挑战赛开赛咯！为了增加趣味性，本届比赛增加了“新玩法”-- “押宝玩法”，“竞猜玩法”和“擂主玩法”。

规则：

1. 押宝玩法：进入“押宝”竞猜帖，购买主题（5鱼币）参与“押宝”，最终“押宝”获胜者将平分奖池的奖金并额外获取10鱼币奖励。猜错者将不返还“押宝”的鱼币。若本届比赛无人“押宝”成功，奖金将累计到下次比赛。

2. 竞猜玩法：直接在比赛帖的下方进行投票，凡事“竞赛”获胜者，将奖励5鱼币。竞猜无门槛，人人都可以参与。竞猜以后，请在本帖留个言，方便领取奖励。

3. 擂主玩法：上一期挑战成功的鱼油成为挑战赛的擂主，擂主有优先权提议下一期的赛题，一届挑战赛共分5期，同一届中当擂主最长的鱼油有额外奖励。

本期擂主：小剑剑

本期赛题的题型由小剑剑优先选择：算法题


题目：找零钱

小明有一张4元面值的货币，如果兑换成1元和2元面值的零钱的话，有：
（1,1,1,1），（1,1,2），（2,2）这样3种方式。

同理，小明有一张10元面值的货币，如果兑换成2元,3元和5元面值的零钱的话，有：
（2,2,2,2,2），（2,2,3,3），（2,3,5），（5,5）这样4种方式。

请设计一个函数changes(n, [a,b,c...]), 输出n面值的钞票兑换成[a,b,c...]面值的零钱的话，一共有多少种方式。
假设零钱面值的货币数量足够多。
def changes(n, [a,b,c...]):
    "Your code here"
    return how many methods of the changes

测试数据：
changes(4,[1,2]) #3
changes(10,[2,3,5]) #4
changes(10,[1,2,5]) #10
changes(20,[3,4,5]) #6
changes(25,[2,3,4,5]) #44
changes(50,[5,6,7,8,9]) #56
changes(10,[4,7]) #0

要求：

程序运算正确，执行效率最高的即为获胜者。

竞猜：
changes(40,[3,5,7,9]) 输出为多少？

比赛截止日期：9月23日24时，竞猜和押宝截止日期为9月22日

@小甲鱼 @冬雪雪冬 @～风介～ @SixPy

SixPy

SixPy

1. from itertools import combinations_with_replacement as comb_rpl
   
2. def changes(n, ls):
   
3.         cmb = {x for i in range(n//max(ls)-1, n//min(ls)+1)
   
4.                  for x in comb_rpl(ls,i) if sum(x)==n}
   
5.         return len(cmb),cmb
   
6. 
   
7. print(changes(50,[5,6,7,8,9]))
   

复制代码

1. 
   
2. (56, {(7, 7, 9, 9, 9, 9), (5, 5, 5, 6, 6, 7, 8, 8), (5, 5, 6, 6, 7, 7, 7, 7), (6, 6, 6, 6, 6, 6, 6, 8), (5, 7, 7, 7, 8, 8, 8), (5, 5, 5, 6, 6, 6, 8, 9), (5, 6, 7, 7, 7, 9, 9), (5, 5, 5, 5, 6, 7, 8, 9), (5, 5, 6, 6, 6, 7, 7, 8), (5, 5, 5, 5, 5, 6, 6, 6, 7), (5, 6, 6, 6, 9, 9, 9), (5, 5, 6, 8, 8, 9, 9), (5, 7, 7, 7, 7, 8, 9), (5, 5, 5, 8, 9, 9, 9), (6, 6, 6, 7, 7, 9, 9), (5, 5, 6, 6, 6, 6, 8, 8), (7, 8, 8, 9, 9, 9), (5, 5, 5, 5, 5, 5, 5, 7, 8), (5, 5, 7, 8, 8, 8, 9), (6, 6, 7, 7, 8, 8, 8), (5, 6, 6, 6, 6, 7, 7, 7), (6, 7, 7, 7, 7, 7, 9), (6, 6, 6, 6, 6, 6, 7, 7), (5, 6, 7, 7, 8, 8, 9), (5, 5, 5, 5, 5, 5, 6, 6, 8), (6, 7, 7, 7, 7, 8, 8), (5, 5, 5, 5, 6, 8, 8, 8), (5, 5, 5, 5, 6, 6, 9, 9), (5, 6, 6, 6, 6, 6, 6, 9), (6, 6, 6, 6, 8, 9, 9), (5, 5, 7, 7, 8, 9, 9), (5, 5, 5, 5, 5, 7, 9, 9), (6, 6, 7, 7, 7, 8, 9), (5, 6, 6, 7, 8, 9, 9), (7, 7, 7, 7, 7, 7, 8), (8, 8, 8, 8, 9, 9), (5, 5, 8, 8, 8, 8, 8), (5, 9, 9, 9, 9, 9), (5, 6, 6, 6, 6, 6, 7, 8), (5, 5, 5, 5, 5, 8, 8, 9), (5, 5, 5, 5, 6, 6, 6, 6, 6), (5, 5, 5, 5, 7, 7, 7, 9), (5, 5, 5, 5, 5, 5, 5, 5, 5, 5), (6, 6, 6, 8, 8, 8, 8), (5, 5, 5, 5, 5, 5, 6, 7, 7), (5, 5, 5, 5, 7, 7, 8, 8), (5, 5, 6, 7, 9, 9, 9), (6, 6, 6, 7, 8, 8, 9), (5, 5, 5, 5, 5, 5, 5, 6, 9), (6, 8, 9, 9, 9, 9), (5, 5, 5, 6, 6, 7, 7, 9), (5, 5, 5, 7, 7, 7, 7, 7), (5, 6, 7, 8, 8, 8, 8), (5, 5, 5, 6, 7, 7, 7, 8), (5, 5, 6, 6, 6, 6, 7, 9), (5, 6, 6, 8, 8, 8, 9)})
   

复制代码

SixPy

1. >>> changes(40,[3,5,7,9])
   
2. (24, {(3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 5), (3, 5, 5, 9, 9, 9), (3, 3, 3, 3, 5, 5, 9, 9), (3, 5, 5, 5, 5, 5, 5, 7), (3, 3, 3, 3, 3, 5, 5, 5, 5, 5), (3, 7, 7, 7, 7, 9), (3, 3, 3, 3, 3, 3, 3, 3, 7, 9), (3, 3, 3, 3, 3, 3, 3, 5, 5, 9), (3, 3, 7, 9, 9, 9), (3, 5, 7, 7, 9, 9), (3, 3, 3, 3, 5, 7, 7, 9), (3, 3, 3, 3, 3, 3, 5, 5, 5, 7), (5, 5, 5, 5, 5, 5, 5, 5), (3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 7), (3, 3, 3, 5, 5, 7, 7, 7), (3, 3, 5, 5, 5, 5, 5, 9), (3, 3, 3, 3, 7, 7, 7, 7), (3, 3, 3, 3, 3, 7, 9, 9), (5, 7, 7, 7, 7, 7), (3, 3, 3, 5, 5, 5, 7, 9), (5, 5, 5, 7, 9, 9), (3, 3, 5, 5, 5, 5, 7, 7), (5, 5, 7, 7, 7, 9), (3, 3, 3, 3, 3, 3, 3, 5, 7, 7)})

复制代码

jerryxjr1220

SixPy 发表于 2017-9-18 16:55

结果应该是对的，但是穷举的话，效率可能是问题，看看其他参赛者的答案。

SixPy

jerryxjr1220 发表于 2017-9-18 17:21
结果应该是对的，但是穷举的话，效率可能是问题，看看其他参赛者的答案。

我是来凑热闹的~

凑数算法，这一类的动态规划题目，好像没有特别高效的实现方式
但可以利用并行算法来提高速度。

DFYNING

新手报到
由于使用迭代  数字大了会很慢   (比较粗糙 见谅)

1. def isset(i):
   
2.    try :
   
3.      len(i)
   
4.    except :
   
5.      return  1
   
6.    else :
   
7.      return 0
   
8. def sum(chargetable,charges):
   
9.     money=0
   
10.     for i in range(len(chargetable)):
    
11.         
    
12.         money+=chargetable[i]*charges[i]
    
13.     return money
    
14. 
    
15. def diedai(i,charges,chargetable=None):
    
16.     global n
    
17.     if    isset(chargetable):
    
18.         chargetable=[0*x for x in charges]
    
19.         
    
20.     if sum(chargetable,charges)<sums and i <len(chargetable):
    
21.         chargetable[i]=chargetable[i]+1
    
22.         
    
23.         diedai(i,charges,chargetable)
    
24.         chargetable[i]=chargetable[i]-1
    
25.         if i+1<=len(chargetable):
    
26.             diedai(i+1,charges,chargetable)
    
27.     if sum(chargetable,charges)==sums:
    
28.         n+=1
    
29.         
    
30.         
    
31.         
    
32. n=0
    
33. 
    
34. sums=40    #使用时更改这两个数据
    
35. charges=[3,5,7,9]
    
36.    
    
37. diedai(0,charges)
    
38. print(n)

复制代码

结果：
50 [5,6,7,8,9]    #56

gunjang

最后的测试结果应该是1吧
changes(12,[4,7])=1,12=4,4,4
逻辑很简单，但是使用递归肯定效率不高的

1. import sys
   
2. sys.setrecursionlimit(100000)
   
3. 
   
4. def getways(leftmoney, maxcoinindex, coins):
   
5.         if leftmoney == 0:
   
6.                 return 1
   
7.         while leftmoney < coins[maxcoinindex]:
   
8.                 maxcoinindex -= 1
   
9.                 if maxcoinindex < 0:
   
10.                         return 0
    
11. 
    
12.         if (maxcoinindex == 0):
    
13.                 if leftmoney % coins[maxcoinindex] == 0:       
    
14.                         return 1
    
15.                 else:
    
16.                         return 0
    
17. 
    
18.         r = 0
    
19.         currcoin = coins[maxcoinindex]
    
20.         for i in range(leftmoney//currcoin, -1, -1):
    
21.                 r += getways(leftmoney-currcoin*i, maxcoinindex-1, coins)
    
22.         return r
    
23. 
    
24. def changes(n, coins):  
    
25.         coins.sort()
    
26.         return getways(n, len(coins)-1, coins)               
    
27. 
    
28. print(changes(4,[1,2])) #3
    
29. print(changes(10,[2,3,5])) #4
    
30. print(changes(10,[1,2,5])) #10
    
31. print(changes(20,[3,4,5])) #6
    
32. print(changes(25,[2,3,4,5])) #44
    
33. print(changes(50,[5,6,7,8,9])) #56
    
34. print(changes(12,[4,7])) #0
    
35. print(changes(40,[3,5,7,9]))

复制代码

jerryxjr1220

gunjang 发表于 2017-9-18 23:34
最后的测试结果应该是1吧
changes(12,[4,7])=1,12=4,4,4
逻辑很简单，但是使用递归肯定效率不高的

是我抄错了，应该是changes(10,[4,7]) #0

gunjang

妖风阵阵，网上的优化算法，改成python代码

1. import numpy as np
   
2. import time
   
3. def changes(n, coins):
   
4.         dp = np.zeros((n+1), dtype=np.int64)
   
5.         dp[0] = 1
   
6.         for i in range(len(coins)):
   
7.                 for j in range(coins[i], n+1):
   
8.                         dp[j] = dp[j]+dp[j-coins[i]]
   
9.         return dp[n]
   
10. print(changes(4,[1,2])) #3
    
11. print(changes(10,[2,3,5])) #4
    
12. print(changes(10,[1,2,5])) #10
    
13. print(changes(20,[3,4,5])) #6
    
14. print(changes(25,[2,3,4,5])) #44
    
15. print(changes(50,[5,6,7,8,9])) #56
    
16. print(changes(10,[4,7])) #0
    
17. print(changes(40,[3,5,7,9])) #24

复制代码

dp[sum] = 用前i种硬币构成sum 的所有组合数
dp[sum] = dp[i-1][sum - 0*Vm] + dp[i-1][sum - 1*Vm]+ dp[i-1][sum - 2*Vm] + ... + dp[i-1][sum - K*Vm]; 其中K = sum / Vm
如果我们用二位数组表示dp[sum], 我们发现第i行的值全部依赖与i-1行的值，所以我们可以逐行求解该数组。如果前0种硬币要组成sum，我们规定为dp[0][sum] = 0.
什么回溯递归，弱爆了。。

SixPy

gunjang 发表于 2017-9-19 22:42
妖风阵阵，网上的优化算法，改成python代码

dp[sum] = 用前i种硬币构成sum 的所有组合数

你这个没必要用 numpy
而且，你的算法里也没利用到np的特性。
简化一下：

1. def changes(n, coins):
   
2.         dp = [1]+[0]*n
   
3.         for c in  coins :
   
4.                 for j in range(c, n+1):
   
5.                         dp[j] = dp[j]+dp[j-c]
   
6.         return dp[n],dp
   
7.    
   
8. print(changes(50,[5,6,7,8,9])) #56

复制代码

gunjang

SixPy 发表于 2017-9-20 10:49
你这个没必要用 numpy
而且，你的算法里也没利用到np的特性。
简化一下：

是的，当n比较大的时候，速度会快点

gunjang

gunjang 发表于 2017-9-20 11:21
是的，当n比较大的时候，速度会快点

代码变复杂点，但是速度更快了----其实针对的都是n比较大，coins的项目比较多的情况
仔细看了代码，就是递归算法中的尾递归优化
最后一个循环（coins[-1]）没必要整体都求，和n相关的求下就好了

1. def changes(n, coins):
   
2.         if coins[0] != 1:
   
3.                 dp = np.zeros((n+1), dtype=np.uint64)
   
4.                 for j in range(0, n+1, coins[0]):
   
5.                         dp[j] = 1
   
6.         else:
   
7.                 dp = np.ones((n+1), dtype=np.uint64)
   
8.         #print(dp)
   
9. 
   
10.         for i in range(1, len(coins)-1):
    
11.                 for j in range(coins[i], n+1):
    
12.                         dp[j] = dp[j]+dp[j-coins[i]]
    
13.         if len(coins) > 1:
    
14.                 for j in range(n%coins[-1] + coins[-1] , n+1, coins[-1]):
    
15.                         dp[j] = dp[j]+dp[j-coins[-1]]
    
16.         return dp[n]

复制代码

gunjang

gunjang 发表于 2017-9-20 11:21
是的，当n比较大的时候，速度会快点

代码变复杂点，但是速度更快了----其实针对的都是n比较大，coins的项目比较多的情况
仔细看了代码，就是递归算法中的尾递归优化
最后一个循环（coins[-1]）没必要整体都求，和n相关的求下就好了

1. def changes(n, coins):
   
2.         if coins[0] != 1:
   
3.                 dp = np.zeros((n+1), dtype=np.uint64)
   
4.                 for j in range(0, n+1, coins[0]):
   
5.                         dp[j] = 1
   
6.         else:
   
7.                 dp = np.ones((n+1), dtype=np.uint64)
   
8.         #print(dp)
   
9. 
   
10.         for i in range(1, len(coins)-1):
    
11.                 for j in range(coins[i], n+1):
    
12.                         dp[j] = dp[j]+dp[j-coins[i]]
    
13.         if len(coins) > 1:
    
14.                 for j in range(n%coins[-1] + coins[-1] , n+1, coins[-1]):
    
15.                         dp[j] = dp[j]+dp[j-coins[-1]]
    
16.         return dp[n]
    

复制代码

小剑剑

1. def change(money,array):
   
2.     array=list(set(array))
   
3.     li=[int (not bool(i%array[0])) for i in range(money+1)]
   
4.     t=1
   
5.     l=len(array)
   
6.     while t<l:
   
7.         li=[sum([li[i] for i in range(j,-1,-1*array[t])]) for j in range(money+1)]
   
8.         t+=1
   
9.     return li[money]

复制代码