[已解决]生成器 兑换硬币

蛋炒饭妖妖

使用生成器 yield有如下一个例子。两个yield有点理不清楚程序前后关系了。
求大神分析一下过程。
PS：我能看的懂得添加了注释

1. def make_change(amount,coins=[1,5,10,25],hand=None):
   
2.     #如果已经开始了一个组合，则不做变动，否则将hand列表化
   
3.     hand=[] if hand is None else hand
   
4.      #若当前组合方式已完成，返回组合方式hand
   
5.     if amount==0:
   
6.         yield hand
   
7.     #从硬币序列中拿硬币
   
8.     for coin in coins:
   
9.         #确保硬币面额不会大于总额，但是后面这个判断看不懂
   
10.         if coin >amount or (len(hand)>0 and hand[-1]<coin):
    
11.             continue
    
12.         #这里递归和生成器就完全乱了
    
13.         for result in make_change(amount-coin ,coins=coins,hand=hand+[coin]):
    
14.             yield result
    
15. 
    
16. for way in make_change(100,coins=[10,25,50]):
    
17.     print way

复制代码

求解答~~

最佳答案

月排行榜 / 总排行榜

jackie-L

2016-12-28 16:27:39

1. def make_change(amount,coins=[1,5,10,25],hand=None):
   
2.     # 如果手里有硬币就不变，否则为空手
   
3.     hand=[] if hand is None else hand
   
4.      # 需要组合的钱的总数等于手中记下的组合时
   
5.     if amount==0:
   
6.         # 把手中的硬记录币拿出去
   
7.         # 生成一条硬币记录
   
8.         yield hand
   
9.     #从硬币序列中拿硬币
   
10.     for coin in coins:
    
11.         # 如果硬币比我要的总数大或比在手中拿的上次选的那个硬币大
    
12.         if coin >amount or (len(hand)>0 and hand[-1]<coin):
    
13.             continue # 换一个银币
    
14.         # 再来摸一次，还差amount-coin金额，还是那些硬币，手中记下了刚才选的那个硬币
    
15.         for result in make_change(amount-coin ,coins=coins,hand=hand+[coin]):
    
16.             # result 就是hand的生成的那个组合如[10,10,10,10,10,10,10,10,10,10,10,10]
    
17.             # 将结果返回给函数外
    
18.             yield result
    
19. 
    
20. # 将每次生成的结果打印出来
    
21. for way in make_change(50,coins=[10,25,50]):
    
22.     print(way)

复制代码

跳转到最佳答案楼层

jackie-L

1. def make_change(amount,coins=[1,5,10,25],hand=None):
   
2.     # 如果手里有硬币就不变，否则为空手
   
3.     hand=[] if hand is None else hand
   
4.      # 需要组合的钱的总数等于手中记下的组合时
   
5.     if amount==0:
   
6.         # 把手中的硬记录币拿出去
   
7.         # 生成一条硬币记录
   
8.         yield hand
   
9.     #从硬币序列中拿硬币
   
10.     for coin in coins:
    
11.         # 如果硬币比我要的总数大或比在手中拿的上次选的那个硬币大
    
12.         if coin >amount or (len(hand)>0 and hand[-1]<coin):
    
13.             continue # 换一个银币
    
14.         # 再来摸一次，还差amount-coin金额，还是那些硬币，手中记下了刚才选的那个硬币
    
15.         for result in make_change(amount-coin ,coins=coins,hand=hand+[coin]):
    
16.             # result 就是hand的生成的那个组合如[10,10,10,10,10,10,10,10,10,10,10,10]
    
17.             # 将结果返回给函数外
    
18.             yield result
    
19. 
    
20. # 将每次生成的结果打印出来
    
21. for way in make_change(50,coins=[10,25,50]):
    
22.     print(way)

复制代码

jackie-L

我觉得上面还是没讲清楚
我简化一下其实就是函数不断给自己放入不同的参数
每次放进去的情况如下
方便讲解我就用最简单数字
（50， [10,25,50],[ ]）
（40， [10,25,50],[10 ]）
（30， [10,25,50],[10,10 ]）
（20， [10,25,50],[10,10, 10 ]）
（10， [10,25,50],[10,10, 10,10 ]）
（0， [10,25,50],[10,10, 10,10,10 ]）
然后后面的其他组合都会进入下面这个判断语句
if coin >amount or (len(hand)>0 and hand[-1]<coin)：
   continue
上面把10这个硬币所有可能试完了
然后由于for coin in coins:这句
就会取出25这个银币
再进行下面的语句
（25， [10,25,50],[25 ]）
中间又会有许多次通不过条件
（0， [10,25,50],[25,25 ]）
以此类推

蛋炒饭妖妖

jackie-L 发表于 2016-12-28 17:33
我觉得上面还是没讲清楚
我简化一下其实就是函数不断给自己放入不同的参数
每次放进去的情况如下

麻烦请教一下yield result 这句是把result返回给谁了呢？

蛋炒饭妖妖

jackie-L 发表于 2016-12-28 17:33
我觉得上面还是没讲清楚
我简化一下其实就是函数不断给自己放入不同的参数
每次放进去的情况如下

麻烦请教一下yield result 这句是把result返回给谁了呢？

蛋炒饭妖妖

jackie-L 发表于 2016-12-28 16:27

麻烦请教一下yield result 这句是把result返回给谁了呢？

jackie-L

蛋炒饭妖妖 发表于 2016-12-29 09:01
麻烦请教一下yield result 这句是把result返回给谁了呢？

这个函数的思路写的很好，而且是一个数学问题，我们先来谈数学模型
题目是有三个数字分别是10,25,50
求3个数字的组成50这个数的各种组合（个数不限）
用什么方法了？
当然是穷尽所有可能的组合，那穷尽所以可能的组合又用什么方法了？

答：每种可能都试一次，我先取10这个数，再用10和目标50对比，比50小，明显不够还要继续，
因为有3个数（10,25,50），所以10就要分别和他们试一次如10,10 |  10,25 |  10,50
显然10,10 |  10,25还是不行，还要继续下去，而10,50大于50了就停止了
干脆我画张图，穷尽所有方法的树状图

jackie-L

上面谈了数学模型，现在又来谈谈代码的实现
for result in make_change(amount-coin ,coins=coins,hand=hand+[coin]):
这是递归的入口最容易出问题，
在每一次拿数字的时候，是不能改变这个层级这个作用域里的变量值的
所以是用amount-coin和hand+[coin]把这个层级选的数字coin分别和amount和hand
组成公式传了下一个层级，并没有改变当前层级的hand和amount
这是这个递归的核心所在。

我们再来谈谈yield
当你开始执行for way in make_change(100,coins=[10,25,50]):
这句的时候函数开始运行，启动生成器
先取第一个10
在运行的第一圈就会直接进入函数的这句
for result in make_change(amount-coin ,coins=coins,hand=hand+[coin]):
这句又是启动一个生成器，最外围的第一圈是没有跑完的，
现在又进入下层
又取一个10
又启动生成器
进入下一层
直到取的数字大于50
函数又退回到上一层
由于每层都要选3个数字
所以每一层都还要再启动2次生成器

我再来谈第一次生成结果的时候
但【10,10,10,10,10】的时候
最下层的生成器会执行
if amount==0:
        yield hand
这个结果会一次返回给每一个层级的出入口
for result in make_change(amount-coin ,coins=coins,hand=hand+[coin]):
        yield result  这句不停的通过每一层yield result 传递直到最外层，最后传到函数外面
就是下面这句
for way in make_change(100,coins=[10,25,50]):
for 循环又启动下一次生成
又启动了，生成器厉害的地方就是，从原来的地方继续跑
然会生成器会通过
for result in make_change(amount-coin ,coins=coins,hand=hand+[coin]):
每一层的入口回到最下层的
yield hand这个刚才yield 【10,10,10,10,10】的地方
又开始继续
【10,10,10,10,10】由于等于50而不是小于50函数会继续试
在我发的树图中你会看的很清楚
【10,10,10,10,10】会进入下面语句分别和10，25,50组合
结果是都会大于50最后停止了是不会再进入下一个层级
由于这个层级的硬币都选完了，都大于50，什么都不会发生
就会继续进行上一层的选25这个【10,10,10,10】和25就会进入这个选择的下一层
在下一层中都会大于50就会终止，返回到【10,10,10,10】和50
【10,10,10,10】和50再进入下一层，结果大于50都回返回来
就再回到上一层把没选的数字，都试完，以此类推，所有代码就会执行完

只要遇到=50的时候
就会yield hand
再通过每一层的yield result，返回到最外面
再继续的时候，生成器又会回到最里面。继续进行

jackie-L

提醒一下if coin >amount or (len(hand)>0 and hand[-1]<coin):
这句中 (len(hand)>0 and hand[-1]<coin)这个的作用在于
减少重复计算
比如你用10和25,50的所有可能都试完了
就没有必要在第一个数为25的时候再和10试了25只用和25,50试即可
50就和50试就行了
反过来也一样，50和10,25的可能都试完了，
10,25的时候就没必要和50试了

jackie-L

能明白我说的了吗？

蛋炒饭妖妖

jackie-L 发表于 2016-12-29 12:11
能明白我说的了吗？

太感谢你啦~~~

真的很清楚的解答。

谢谢~~

conn

顶起

wei_Y

yield就是挂起了，当程序请求到 yield这个关键字时就会 "挂起"，直到调用了__next__，不管是递归还是迭代都是这样。for循环会自动调用__next__这个方法。

1. range(5) ==
   
2. def  range(n):
   
3.     i = 0
   
4.     while i<n:
   
5.         yield i
   
6.         i += 1
   

复制代码

jackie-L

蛋炒饭妖妖 发表于 2016-12-30 10:27
太感谢你啦~~~

真的很清楚的解答。

这个函数绝对是高手才写的出来，而且里面有很多陷阱，估计没人会像我这样回答，还帮你画了个图