提问人：Lucas 提问时间：11/11/2023 最后编辑：jarmodLucas 更新时间：11/12/2023 访问量：92
返回斐波那契递归中的节点数
Return the number of nodes in Fibonacci Recursion
问：
我想编写一个函数，返回斐波那契递归树中的节点数，知道节点数等于计算第 n 个斐波那契数 - 1 所需的加法数。
我有一个程序，它返回加法数来计算第 n 个斐波那契数：
def main():
print('(Fn, additions)')
for i in range(0, 11):
print(f"F({i}) = {fibR(i)}")
def fibR(n):
#Base case
if n == 0 or n == 1:
add = 0
return (n, add)
return (fibR(n-1)[0] + fibR(n - 2)[0], fibR(n-1)[1] + fibR(n - 2)[1] + 1)
if __name__ == '__main__':
main()
如何修改它以返回节点数？我试图将返回元组的第二个组件更改为：
return (fibR(n-1)[0] + fibR(n - 2)[0], (fibR(n-1)[1] + fibR(n - 2)[1] + 1) - 1)
但它不起作用。有人可以帮忙吗？提前致谢
编辑：
预期输出：
(Fn, additions)
F(0) = (0, 0)
F(1) = (1, 0)
F(2) = (1, 0)
F(3) = (2, 1)
F(4) = (3, 3)
F(5) = (5, 6)
F(6) = (8, 11)
F(7) = (13, 19)
F(8) = (21, 32)
F(9) = (34, 53)
F(10) = (55, 87)
答：
0赞
tetris programming
11/12/2023
#1
您的论坛计算节点数是正确的。但是你的 firb（） 函数中有一个小错误。有时，您返回了错误的 add 值。请参阅下面的代码：fibR(n - 1)[1] + fibR(n - 2)[1] + 1
def main():
print('(Fn, additions)')
for i in range(1, 11):
print(f"F({i}) = {fibR(i)[0],fibR(i)[1]}")
def fibR(n):
#Base case
global adders
if n == 0 or n == 1:
add = n
return n, add
return (fibR(n - 1)[0] + fibR(n - 2)[0], fibR(n - 1)[1] + fibR(n - 2)[1] + 1)
if __name__ == '__main__':
main()
#output F(n)=(Fibu value, Number of knots)
F(1) = (1, 1)
F(2) = (1, 2)
F(3) = (2, 4)
F(4) = (3, 7)
F(5) = (5, 12)
F(6) = (8, 20)
F(7) = (13, 33)
F(8) = (21, 54)
F(9) = (34, 88)
F(10) = (55, 143)
请注意，由于添加的数量是节点之间的分支数。
由于您给出了令人困惑的预期输出，因此这里有一张图片，您可以通过自己计算节点数或分支数来验证我的结果。number_of_nodes-1=number_of_additions
评论
0赞
Lucas
11/12/2023
是的，但我想使用添加的数量来返回节点的数量，没有其他事实
0赞
tetris programming
11/12/2023
好的，我明白了。我改变了我的答案。请再次检查
0赞
Lucas
11/12/2023
公式 fibR（n - 1）[1] + fibR（n - 2）[1] + 1 用于计算加法数，而不是节点数。另外，您将 main 函数更改为减去 1，然后获得节点数，但我希望在递归函数中完成，这是练习的重点
0赞
tetris programming
11/12/2023
好的，对不起。我希望我的输入已经让你更接近一点，但我认为我并不完全理解你的练习。也许上传练习？无论如何，如果您找到解决方案，请告诉我
0赞
aazizzailani
11/12/2023
#2
通过分别计算与总和分开计算节点数来修改程序。修改代码，如下所示：
def main():
print('(Fn, nodes)')
for i in range(0, 11):
print(f"F({i}) = {fibR(i)}")
def fibR(n):
if n == 0 or n == 1:
nodes = 0
return (n, nodes)
nodes = fibR(n-1)[1] + fibR(n-2)[1] + 1
return (fibR(n-1)[0] + fibR(n-2)[0], nodes)
if __name__ == '__main__':
main()
通过此更改，输出将与预期的格式匹配。
评论