- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章Python非单向递归函数如何返回全部结果由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
递归( recursion)是一种神奇的编程技巧,可以大幅简化代码,使之看起来更加简洁。然而递归设计却非常抽象,不容易掌握。通常,我们都是自上而下的思考问题, 递归则是自下而上的解决问题——这就是递归看起来不够直观的原因.
和递归相关的概念里,线性递归/非线性递归、单向递归/非单向递归,是非常重要的,要想掌握递归技术,就必须要深入理解。关于递归的基本概念,有兴趣的读者,可以参考我的博客《Python 递归算法指归》。今天,仅就背包问题谈非单向递归函数如何返回全部结果.
背包问题的背后,是世界七大数学难题之一,多项式复杂程度的非确定性问题。作为程序员,可以将该问题大致上理解为组合优化的问题。背包问题通常被这样描述:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,如何选择,才能使得物品的总价格最高。如果加上不同的限制和条件,背包问题可以衍生出很多变种。比如,下面这道题看起来和背包问题相去甚远,实质上仍然是一个典型的背包问题.
在一款英雄对战游戏中,玩家拥有m件装备和n位英雄,他可以给每一位英雄分配0件或多件装备,而不同的英雄拥有不同数目的装备时将获得不同的攻击力。玩家如何分配这m件装备,可以使得n个英雄获得的攻击力的和最大?以玩家拥有5件装备和3位英雄为例,下表共有3行6列,对应着3位英雄分别拥有从0到5件装备时的攻击力.
0件 | 1件 | 2件 | 3件 | 4件 | 5件 | |
---|---|---|---|---|---|---|
英雄1 | 0 | 1 | 3 | 5 | 7 | 9 |
英雄2 | 0 | 1 | 1 | 3 | 3 | 7 |
英雄3 | 0 | 3 | 4 | 5 | 6 | 7 |
即使不熟悉背包问题,也不难找到解题思路:
找出将m件装备分配给n位英雄的所有方案是解决问题的核心。这里,循环嵌套是行不通的,因为嵌套层数是输入变量。递归是我想到的可行的方法.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
>>>
def
bag(m, n, series
=
list
()):
if
n
=
=
1
:
for
i
in
range
(m
+
1
):
print
(series
+
[i])
else
:
for
i
in
range
(m
+
1
):
bag(m
-
i, n
-
1
, series
+
[i])
>>> bag(
3
,
2
)
# 将3件装备分配给2位英雄的全部方案
[
0
,
0
]
[
0
,
1
]
[
0
,
2
]
[
0
,
3
]
[
1
,
0
]
[
1
,
1
]
[
1
,
2
]
[
2
,
0
]
[
2
,
1
]
[
3
,
0
]
|
递归函数bag,打印出了将3件装备分配给2位英雄的全部方案。显然,这不是一个单向递归,因为在同一级有多次递归调用,这意味着递归过程有多次从递归出口走出。对于非单向递归,是不能使用return返回结果的。那么,如何让递归函数返回全部方案呢?请看下面的例子.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
>>>
def
bag(m, n, result, series
=
list
()):
if
n
=
=
1
:
for
i
in
range
(m
+
1
):
result.append(series
+
[i])
#print(result[-1])
else
:
for
i
in
range
(m
+
1
):
bag(m
-
i, n
-
1
, result, series
+
[i])
>>> result
=
list
()
>>> bag(
5
,
3
, result)
# 将5件装备分配给3位英雄,共有56种分配方案
>>>
len
(result)
56
>>> result
[[
0
,
0
,
0
], [
0
,
0
,
1
], [
0
,
0
,
2
], [
0
,
0
,
3
], [
0
,
0
,
4
], [
0
,
0
,
5
],
[
0
,
1
,
0
], [
0
,
1
,
1
], [
0
,
1
,
2
], [
0
,
1
,
3
], [
0
,
1
,
4
], [
0
,
2
,
0
],
[
0
,
2
,
1
], [
0
,
2
,
2
], [
0
,
2
,
3
], [
0
,
3
,
0
], [
0
,
3
,
1
], [
0
,
3
,
2
],
[
0
,
4
,
0
], [
0
,
4
,
1
], [
0
,
5
,
0
], [
1
,
0
,
0
], [
1
,
0
,
1
], [
1
,
0
,
2
],
[
1
,
0
,
3
], [
1
,
0
,
4
], [
1
,
1
,
0
], [
1
,
1
,
1
], [
1
,
1
,
2
], [
1
,
1
,
3
],
[
1
,
2
,
0
], [
1
,
2
,
1
], [
1
,
2
,
2
], [
1
,
3
,
0
], [
1
,
3
,
1
], [
1
,
4
,
0
],
[
2
,
0
,
0
], [
2
,
0
,
1
], [
2
,
0
,
2
], [
2
,
0
,
3
], [
2
,
1
,
0
], [
2
,
1
,
1
],
[
2
,
1
,
2
], [
2
,
2
,
0
], [
2
,
2
,
1
], [
2
,
3
,
0
], [
3
,
0
,
0
], [
3
,
0
,
1
],
[
3
,
0
,
2
], [
3
,
1
,
0
], [
3
,
1
,
1
], [
3
,
2
,
0
], [
4
,
0
,
0
], [
4
,
0
,
1
],
[
4
,
1
,
0
], [
5
,
0
,
0
]]
|
上面的代码中,在调用递归函数之前,先创建一个全局的列表对象result,并作为参数传递给递归函数。递归调用结束后,全部的装备分配方案就保存在列表对象result中.
遍历56种分配方案,计算每一种方案的攻击力之和,保存到一个新的列表v中。p为3位英雄分别拥有从0到5件装备时的攻击力.
1
2
3
4
5
6
7
8
9
10
11
12
13
|
>>> p
=
[
[
0
,
1
,
3
,
5
,
7
,
9
],
[
0
,
1
,
1
,
3
,
3
,
7
],
[
0
,
3
,
4
,
5
,
6
,
7
]
]
>>> v
=
list
()
>>>
for
item
in
result:
v.append(p[
0
][item[
0
]]
+
p[
1
][item[
1
]]
+
p[
2
][item[
2
]])
>>> v
[
0
,
3
,
4
,
5
,
6
,
7
,
1
,
4
,
5
,
6
,
7
,
1
,
4
,
5
,
6
,
3
,
6
,
7
,
3
,
6
,
7
,
1
,
4
,
5
,
6
,
7
,
2
,
5
,
6
,
7
,
2
,
5
,
6
,
4
,
7
,
4
,
3
,
6
,
7
,
8
,
4
,
7
,
8
,
4
,
7
,
6
,
5
,
8
,
9
,
6
,
9
,
6
,
7
,
10
,
8
,
9
]
|
找出v列表最大值的序号,进而得到攻击力最大的装备分配方案.
1
2
3
4
|
>>>
max
(v)
10
>>> result[v.index(
max
(v))]
[
4
,
0
,
1
]
|
最佳分配方案是第1位英雄持有4件装备,第2位英雄没有装备,第3位英雄持有1件装备,此时3位英雄的攻击力之和为最大,其值为10.
到此这篇关于Python非单向递归函数如何返回全部结果的文章就介绍到这了,更多相关Python非单向递归返回 内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我! 。
原文链接:https://xufive.blog.csdn.net/article/details/108264816 。
最后此篇关于Python非单向递归函数如何返回全部结果的文章就讲到这里了,如果你想了解更多关于Python非单向递归函数如何返回全部结果的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
C语言sscanf()函数:从字符串中读取指定格式的数据 头文件: ?
最近,我有一个关于工作预评估的问题,即使查询了每个功能的工作原理,我也不知道如何解决。这是一个伪代码。 下面是一个名为foo()的函数,该函数将被传递一个值并返回一个值。如果将以下值传递给foo函数,
CStr 函数 返回表达式,该表达式已被转换为 String 子类型的 Variant。 CStr(expression) expression 参数是任意有效的表达式。 说明 通常,可以
CSng 函数 返回表达式,该表达式已被转换为 Single 子类型的 Variant。 CSng(expression) expression 参数是任意有效的表达式。 说明 通常,可
CreateObject 函数 创建并返回对 Automation 对象的引用。 CreateObject(servername.typename [, location]) 参数 serv
Cos 函数 返回某个角的余弦值。 Cos(number) number 参数可以是任何将某个角表示为弧度的有效数值表达式。 说明 Cos 函数取某个角并返回直角三角形两边的比值。此比值是
CLng 函数 返回表达式,此表达式已被转换为 Long 子类型的 Variant。 CLng(expression) expression 参数是任意有效的表达式。 说明 通常,您可以使
CInt 函数 返回表达式,此表达式已被转换为 Integer 子类型的 Variant。 CInt(expression) expression 参数是任意有效的表达式。 说明 通常,可
Chr 函数 返回与指定的 ANSI 字符代码相对应的字符。 Chr(charcode) charcode 参数是可以标识字符的数字。 说明 从 0 到 31 的数字表示标准的不可打印的
CDbl 函数 返回表达式,此表达式已被转换为 Double 子类型的 Variant。 CDbl(expression) expression 参数是任意有效的表达式。 说明 通常,您可
CDate 函数 返回表达式,此表达式已被转换为 Date 子类型的 Variant。 CDate(date) date 参数是任意有效的日期表达式。 说明 IsDate 函数用于判断 d
CCur 函数 返回表达式,此表达式已被转换为 Currency 子类型的 Variant。 CCur(expression) expression 参数是任意有效的表达式。 说明 通常,
CByte 函数 返回表达式,此表达式已被转换为 Byte 子类型的 Variant。 CByte(expression) expression 参数是任意有效的表达式。 说明 通常,可以
CBool 函数 返回表达式,此表达式已转换为 Boolean 子类型的 Variant。 CBool(expression) expression 是任意有效的表达式。 说明 如果 ex
Atn 函数 返回数值的反正切值。 Atn(number) number 参数可以是任意有效的数值表达式。 说明 Atn 函数计算直角三角形两个边的比值 (number) 并返回对应角的弧
Asc 函数 返回与字符串的第一个字母对应的 ANSI 字符代码。 Asc(string) string 参数是任意有效的字符串表达式。如果 string 参数未包含字符,则将发生运行时错误。
Array 函数 返回包含数组的 Variant。 Array(arglist) arglist 参数是赋给包含在 Variant 中的数组元素的值的列表(用逗号分隔)。如果没有指定此参数,则
Abs 函数 返回数字的绝对值。 Abs(number) number 参数可以是任意有效的数值表达式。如果 number 包含 Null,则返回 Null;如果是未初始化变量,则返回 0。
FormatPercent 函数 返回表达式,此表达式已被格式化为尾随有 % 符号的百分比(乘以 100 )。 FormatPercent(expression[,NumDigitsAfterD
FormatNumber 函数 返回表达式,此表达式已被格式化为数值。 FormatNumber( expression [,NumDigitsAfterDecimal [,Inc
我是一名优秀的程序员,十分优秀!