Python非单向递归函数如何返回全部结果

python教程

共 2843字,需浏览 6分钟

 ·

2020-12-29 12:41

递归( recursion)是一种神奇的编程技巧,可以大幅简化代码,使之看起来更加简洁。然而递归设计却非常抽象,不容易掌握。通常,我们都是自上而下的思考问题, 递归则是自下而上的解决问题——这就是递归看起来不够直观的原因。

和递归相关的概念里,线性递归/非线性递归、单向递归/非单向递归,是非常重要的,要想掌握递归技术,就必须要深入理解。关于递归的基本概念,有兴趣的读者,可以参考我的博客《Python 递归算法指归》。今天,仅就背包问题谈非单向递归函数如何返回全部结果。

背包问题的背后,是世界七大数学难题之一,多项式复杂程度的非确定性问题。作为程序员,可以将该问题大致上理解为组合优化的问题。背包问题通常被这样描述:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,如何选择,才能使得物品的总价格最高。如果加上不同的限制和条件,背包问题可以衍生出很多变种。比如,下面这道题看起来和背包问题相去甚远,实质上仍然是一个典型的背包问题。

在一款英雄对战游戏中,玩家拥有m件装备和n位英雄,他可以给每一位英雄分配0件或多件装备,而不同的英雄拥有不同数目的装备时将获得不同的攻击力。玩家如何分配这m件装备,可以使得n个英雄获得的攻击力的和最大?以玩家拥有5件装备和3位英雄为例,下表共有3行6列,对应着3位英雄分别拥有从0到5件装备时的攻击力。


0件1件2件3件4件5件
英雄1013579
英雄2011337
英雄3034567

即使不熟悉背包问题,也不难找到解题思路:

  • 找出所有可能的装备分配方案

  • 计算每一个方案的攻击值

  • 选择攻击值最大的分配方案

1. 找出所有可能的装备分配方案

找出将m件装备分配给n位英雄的所有方案是解决问题的核心。这里,循环嵌套是行不通的,因为嵌套层数是输入变量。递归是我想到的可行的方法。

  1. >>> def bag(m, n, series=list()):

  2. if n == 1:

  3. for i in range(m+1):

  4. print(series+[i])

  5. else:

  6. for i in range(m+1):

  7. bag(m-i, n-1, series+[i])

  8. >>> bag(3,2) # 将3件装备分配给2位英雄的全部方案

  9. [0, 0]

  10. [0, 1]

  11. [0, 2]

  12. [0, 3]

  13. [1, 0]

  14. [1, 1]

  15. [1, 2]

  16. [2, 0]

  17. [2, 1]

  18. [3, 0]

递归函数bag,打印出了将3件装备分配给2位英雄的全部方案。显然,这不是一个单向递归,因为在同一级有多次递归调用,这意味着递归过程有多次从递归出口走出。对于非单向递归,是不能使用return返回结果的。那么,如何让递归函数返回全部方案呢?请看下面的例子。

  1. >>> def bag(m, n, result, series=list()):

  2. if n == 1:

  3. for i in range(m+1):

  4. result.append(series+[i])

  5. #print(result[-1])

  6. else:

  7. for i in range(m+1):

  8. bag(m-i, n-1, result, series+[i])

  9.  

  10. >>> result = list()

  11. >>> bag(5, 3, result) # 将5件装备分配给3位英雄,共有56种分配方案

  12. >>> len(result)

  13. 56

  14. >>> result

  15. [[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 0, 3], [0, 0, 4], [0, 0, 5],

  16. [0, 1, 0], [0, 1, 1], [0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 0],

  17. [0, 2, 1], [0, 2, 2], [0, 2, 3], [0, 3, 0], [0, 3, 1], [0, 3, 2],

  18. [0, 4, 0], [0, 4, 1], [0, 5, 0], [1, 0, 0], [1, 0, 1], [1, 0, 2],

  19. [1, 0, 3], [1, 0, 4], [1, 1, 0], [1, 1, 1], [1, 1, 2], [1, 1, 3],

  20. [1, 2, 0], [1, 2, 1], [1, 2, 2], [1, 3, 0], [1, 3, 1], [1, 4, 0],

  21. [2, 0, 0], [2, 0, 1], [2, 0, 2], [2, 0, 3], [2, 1, 0], [2, 1, 1],

  22. [2, 1, 2], [2, 2, 0], [2, 2, 1], [2, 3, 0], [3, 0, 0], [3, 0, 1],

  23. [3, 0, 2], [3, 1, 0], [3, 1, 1], [3, 2, 0], [4, 0, 0], [4, 0, 1],

  24. [4, 1, 0], [5, 0, 0]]

上面的代码中,在调用递归函数之前,先创建一个全局的列表对象result,并作为参数传递给递归函数。递归调用结束后,全部的装备分配方案就保存在列表对象result中。

2. 计算每一个方案的攻击值

遍历56种分配方案,计算每一种方案的攻击力之和,保存到一个新的列表v中。p为3位英雄分别拥有从0到5件装备时的攻击力。

  1. >>> p = [

  2. [0,1,3,5,7,9],

  3. [0,1,1,3,3,7],

  4. [0,3,4,5,6,7]

  5. ]

  6. >>> v = list()

  7. >>> for item in result:

  8. v.append(p[0][item[0]] + p[1][item[1]] + p[2][item[2]])

  9. >>> v

  10. [0, 3, 4, 5, 6, 7, 1, 4, 5, 6, 7, 1, 4, 5, 6, 3, 6, 7, 3,

  11. 6, 7, 1, 4, 5, 6, 7, 2, 5, 6, 7, 2, 5, 6, 4, 7, 4, 3, 6,

  12. 7, 8, 4, 7, 8, 4, 7, 6, 5, 8, 9, 6, 9, 6, 7, 10, 8, 9]

3. 选择攻击值最大的分配方案

找出v列表最大值的序号,进而得到攻击力最大的装备分配方案。

  1. >>> max(v)

  2. 10

  3. >>> result[v.index(max(v))]

  4. [4, 0, 1]

最佳分配方案是第1位英雄持有4件装备,第2位英雄没有装备,第3位英雄持有1件装备,此时3位英雄的攻击力之和为最大,其值为10。

到此这篇关于Python非单向递归函数如何返回全部结果的文章就介绍到这了

  1. 欢迎大家点赞,留言,转发,转载,感谢大家的相伴与支持

    万水千山总是情,点个【在看】行不行

  2. *声明:本文于网络整理,版权归原作者所有,如来源信息有误或侵犯权益,请联系我们删除或授权事


浏览 12
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报