用递归方法求基7树中的最大节点数
用递归方法求基7树中的最大节点数
提问于 2016-05-19 05:02:13
第一次在这里发帖。教自己python和好奇如何使用递归解决下面的问题。我们有一家公司，每个员工最多有7份报告。给定组织的深度x，找出包括首席执行官在内的最大员工数。这基本上是找到一个二叉树的最大节点数，除了基2之外，我们有基7。
我可以用公式(b**(d+1))/(b-1)线性求解，其中b是基，d是树的深度。
def MaxNodes(d):
minions = ((7**(d+1)) - 1) / 6
return minions我还迭代地解决了这个问题：
def answer(x):
minions = 1
for levels in range(x):
if (levels == 0):
minions = 7
else:
minions += (minions * 7)
return minions + 1因此，我们在0级中有值1，从第1级开始，从值7开始，继续乘以7，并将前面的结果相加:1+ (7x1) + (7x7) + (49x7) .对不起，如果这是非常直截了当的，但是我无法思考如何递归地解决这个问题。
提前谢谢你的帮助。
回答 2
Stack Overflow用户
回答已采纳
发布于 2016-05-19 05:15:41
下面是一个简单的递归实现：
def nodes(d):
if d == 0:
return 1
else:
return 1 + 7 * nodes(d - 1)
print [nodes(i) for i in range(5)] # [1, 8, 57, 400, 2801]深度作为参数传递，当它达到0时，函数返回1，从而停止递归。否则，该函数将调用自身，以获得较低级别上的数字，将结果乘以7，并将当前级别添加到其中。
Stack Overflow用户
发布于 2016-05-19 05:45:13
如果您想递归地找到7**x：
def max_siblings(depth, degree=7, total=1):
"""How many siblings maximum at the given *depth*."""
return max_siblings(depth-1, degree, total*degree) if depth else total如果您想递归地找到((7**(depth+1)) - 1) // 6：
def max_nodes(depth, degree=7, total=1):
return max_nodes(depth-1, degree, total+max_siblings(depth)) if depth else total示例：
for depth in range(5):
print(max_nodes(depth))输出：
1
8
57
400
2801您可以使用max_siblings()缓存 decorator计算。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/37314257
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号