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

jerryxjr1220 · 发表于 2017-9-18 14:22:28

本帖最后由 jerryxjr1220 于 2017-9-24 22:35 编辑

第三届鱼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 · 发表于 2017-9-18 16:22:05

SixPy · 发表于 2017-9-18 16:51:12

from itertools import combinations_with_replacement as comb_rpl
def changes(n, ls):
        cmb = {x for i in range(n//max(ls)-1, n//min(ls)+1)
                 for x in comb_rpl(ls,i) if sum(x)==n}
        return len(cmb),cmb

print(changes(50,[5,6,7,8,9]))

(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 · 发表于 2017-9-18 16:55:17

>>> changes(40,[3,5,7,9])
(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 · 发表于 2017-9-18 17:21:05

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

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

SixPy · 发表于 2017-9-18 17:38:54

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

我是来凑热闹的~

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

DFYNING · 发表于 2017-9-18 20:45:05

本帖最后由 DFYNING 于 2017-9-18 20:50 编辑

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

def isset(i): 
   try : 
     len(i) 
   except : 
     return  1 
   else : 
     return 0
def sum(chargetable,charges):
    money=0
    for i in range(len(chargetable)):
        
        money+=chargetable[i]*charges[i]
    return money

def diedai(i,charges,chargetable=None):
    global n
    if    isset(chargetable):
        chargetable=[0*x for x in charges]
        
    if sum(chargetable,charges)<sums and i <len(chargetable):
        chargetable[i]=chargetable[i]+1
        
        diedai(i,charges,chargetable)
        chargetable[i]=chargetable[i]-1
        if i+1<=len(chargetable):
            diedai(i+1,charges,chargetable)
    if sum(chargetable,charges)==sums:
        n+=1
        
        
        
n=0

sums=40    #使用时更改这两个数据
charges=[3,5,7,9]
    
diedai(0,charges)
print(n)

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

gunjang · 发表于 2017-9-18 23:34:18

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

import sys
sys.setrecursionlimit(100000)

def getways(leftmoney, maxcoinindex, coins):
        if leftmoney == 0:
                return 1
        while leftmoney < coins[maxcoinindex]:
                maxcoinindex -= 1
                if maxcoinindex < 0:
                        return 0

        if (maxcoinindex == 0):
                if leftmoney % coins[maxcoinindex] == 0:        
                        return 1
                else:
                        return 0

        r = 0
        currcoin = coins[maxcoinindex]
        for i in range(leftmoney//currcoin, -1, -1):
                r += getways(leftmoney-currcoin*i, maxcoinindex-1, coins)
        return r

def changes(n, coins):  
        coins.sort()
        return getways(n, len(coins)-1, coins)                

print(changes(4,[1,2])) #3
print(changes(10,[2,3,5])) #4
print(changes(10,[1,2,5])) #10
print(changes(20,[3,4,5])) #6
print(changes(25,[2,3,4,5])) #44
print(changes(50,[5,6,7,8,9])) #56
print(changes(12,[4,7])) #0
print(changes(40,[3,5,7,9]))

jerryxjr1220 · 发表于 2017-9-19 07:06:02

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

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

gunjang · 发表于 2017-9-19 22:42:48

本帖最后由 gunjang 于 2017-9-19 22:45 编辑

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

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

dp[i][sum] = 用前i种硬币构成sum 的所有组合数
dp[i][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[i][sum], 我们发现第i行的值全部依赖与i-1行的值，所以我们可以逐行求解该数组。如果前0种硬币要组成sum，我们规定为dp[0][sum] = 0.
什么回溯递归，弱爆了。。

SixPy · 发表于 2017-9-20 10:49:01

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

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

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

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

gunjang · 发表于 2017-9-20 11:21:54

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

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

gunjang · 发表于 2017-9-21 11:36:54

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

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

def changes(n, coins):
        if coins[0] != 1:
                dp = np.zeros((n+1), dtype=np.uint64)
                for j in range(0, n+1, coins[0]):
                        dp[j] = 1
        else:
                dp = np.ones((n+1), dtype=np.uint64)
        #print(dp)

        for i in range(1, len(coins)-1):
                for j in range(coins[i], n+1):
                        dp[j] = dp[j]+dp[j-coins[i]]
        if len(coins) > 1:
                for j in range(n%coins[-1] + coins[-1] , n+1, coins[-1]):
                        dp[j] = dp[j]+dp[j-coins[-1]]
        return dp[n]

gunjang · 发表于 2017-9-21 11:37:31

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

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

def changes(n, coins):
        if coins[0] != 1:
                dp = np.zeros((n+1), dtype=np.uint64)
                for j in range(0, n+1, coins[0]):
                        dp[j] = 1
        else:
                dp = np.ones((n+1), dtype=np.uint64)
        #print(dp)

        for i in range(1, len(coins)-1):
                for j in range(coins[i], n+1):
                        dp[j] = dp[j]+dp[j-coins[i]]
        if len(coins) > 1:
                for j in range(n%coins[-1] + coins[-1] , n+1, coins[-1]):
                        dp[j] = dp[j]+dp[j-coins[-1]]
        return dp[n]

小剑剑 · 发表于 2017-9-23 17:23:56

def change(money,array):
    array=list(set(array))
    li=[int (not bool(i%array[0])) for i in range(money+1)]
    t=1
    l=len(array)
    while t<l:
        li=[sum([li[i] for i in range(j,-1,-1*array[t])]) for j in range(money+1)]
        t+=1
    return li[money]

账号		自动登录	找回密码
密码			立即注册

[技术交流] 鱼C论坛Python精英挑战赛（第三季03期）

本帖被以下淘专辑推荐:

评分

评分