如何在 python 上显示斐波那契递归树
How do I show the fibonacci recursive tree on python
这是我目前的代码:
from loguru import logger
def fibonacci(n, s="% s"):
"""
Using recursive method
"""
# logger.debug(f"Finding {n}th Fibonacci number")
logger.debug(s % ("fib(%d)" % (n)))
a = 0
b = 1
if n <= 0:
return a
elif n in (1, 2):
return b
else:
return fibonacci(n - 1, s % ("fib(%d) + %%s" % (n - 1))) + fibonacci(n - 2, s % ("fib(%d) + %%s" % (n - 2)))
我的目标是在日志中显示递归树,例如 fibonacci(5)
:
fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
and so on...
这可能吗?当前代码没有产生预期的输出。
当前输出:
fib(5)
fib(4) + fib(4)
fib(4) + fib(3) + fib(3)
fib(4) + fib(3) + fib(2) + fib(2)
fib(4) + fib(3) + fib(1) + fib(1)
fib(4) + fib(2) + fib(2)
fib(3) + fib(3)
fib(3) + fib(2) + fib(2)
fib(3) + fib(1) + fib(1)
想法:
一种方法可能是递归中的每个调用都将自身“报告”到它在树记录中的位置。然后我们可以逐层迭代。类似于:
def f(n):
t = ["None"] * (2**(n-1) + 1)
def g(n, i):
l = "(" if i & 1 else ""
r = ")" if not (i & 1) else ""
t[i] = "%sfib(%s)%s" % (l, n, r)
if n > 1:
g(n-1, 2*i+1)
g(n-2, 2*i+2)
g(n, 0)
print(t[0][0:-1])
i = 1
while 2**i-1 < len(t):
print(" + ".join(t[2**i-1:2**(i+1)-1]))
i += 1
输出:
f(5)
"""
fib(5)
(fib(4) + fib(3))
(fib(3) + fib(2)) + (fib(2) + fib(1))
(fib(2) + fib(1)) + (fib(1) + fib(0)) + (fib(1) + fib(0)) + None + None
(fib(1) + fib(0))
"""
您可以定义一个 class 来保存二叉树节点并构建树作为递归斐波那契函数的结果:
class BNode:
def __init__(self,value,left=None,right=None):
self.value = value
self.left = left
self.right = right
def print(self):
printBTree(self,nodeInfo=lambda n:(str(n.value),n.left,n.right))
from functools import lru_cache
@lru_cache() # optimize object count
def fiboTree(n): # (n is an index, not a count)
if n<2: return BNode(n)
a,b = fiboTree(n-2),fiboTree(n-1)
return BNode(a.value+b.value,a,b)
输出:
fiboTree(7).print()
13
____________/ \____________
5 8
_____/ \____ _______/ \______
2 3 3 5
/ \ __/ \_ __/ \_ _____/ \____
1 1 1 2 1 2 2 3
/ \ / \ / \ / \ / \ / \ __/ \_
0 1 0 1 1 1 0 1 1 1 1 1 1 2
/ \ / \ / \ / \ / \
0 1 0 1 0 1 0 1 1 1
/ \
0 1
你可以找到printBTree
函数here
如果只需要说明调用层次,可以直接使用printBTree函数:
def fibo(n):
n=int(n) # linking with strings to let zero come out as a node
return (f"fibo({n})",[None,str(n-2)][n>1], [None,str(n-1)][n>1])
printBTree(5,fibo)
fibo(5)
____________/ \____________
fibo(3) fibo(4)
/ \ _____/ \____
fibo(1) fibo(2) fibo(2) fibo(3)
/ \ / \ / \
fibo(0) fibo(1) fibo(0) fibo(1) fibo(1) fibo(2)
/ \
fibo(0) fibo(1)
要随手打印,我建议使用缩进来传达调用层次结构,否则重复添加将很难与调用者联系起来。
def fibo(n,indent=""):
if n<2: return n
print(indent[:-3] + "|_ "*bool(indent)
+ f"fibo({n}) = fibo({n-2}) + fibo({n-1})")
return fibo(n-2,indent+"| ")+fibo(n-1,indent+" ")
fibo(7)
fibo(7) = fibo(5) + fibo(6)
|_ fibo(5) = fibo(3) + fibo(4)
| |_ fibo(3) = fibo(1) + fibo(2)
| | |_ fibo(2) = fibo(0) + fibo(1)
| |_ fibo(4) = fibo(2) + fibo(3)
| |_ fibo(2) = fibo(0) + fibo(1)
| |_ fibo(3) = fibo(1) + fibo(2)
| |_ fibo(2) = fibo(0) + fibo(1)
|_ fibo(6) = fibo(4) + fibo(5)
|_ fibo(4) = fibo(2) + fibo(3)
| |_ fibo(2) = fibo(0) + fibo(1)
| |_ fibo(3) = fibo(1) + fibo(2)
| |_ fibo(2) = fibo(0) + fibo(1)
|_ fibo(5) = fibo(3) + fibo(4)
|_ fibo(3) = fibo(1) + fibo(2)
| |_ fibo(2) = fibo(0) + fibo(1)
|_ fibo(4) = fibo(2) + fibo(3)
|_ fibo(2) = fibo(0) + fibo(1)
|_ fibo(3) = fibo(1) + fibo(2)
|_ fibo(2) = fibo(0) + fibo(1)
这可以说明记忆的benefits/effect:
def fibo(n,indent="",memo=None):
if n<2: return n
if memo is None: memo = dict()
print(indent[:-3] + "|_ "*bool(indent) + f"fibo({n})",end=" = ")
if n in memo:
print("taken from memo")
else:
print(f"fibo({n-2}) + fibo({n-1})")
memo[n] = fibo(n-2,indent+"| ",memo)+fibo(n-1,indent+" ",memo)
return memo[n]
fibo(7) = fibo(5) + fibo(6)
|_ fibo(5) = fibo(3) + fibo(4)
| |_ fibo(3) = fibo(1) + fibo(2)
| | |_ fibo(2) = fibo(0) + fibo(1)
| |_ fibo(4) = fibo(2) + fibo(3)
| |_ fibo(2) = taken from memo
| |_ fibo(3) = taken from memo
|_ fibo(6) = fibo(4) + fibo(5)
|_ fibo(4) = taken from memo
|_ fibo(5) = taken from memo
这是我目前的代码:
from loguru import logger
def fibonacci(n, s="% s"):
"""
Using recursive method
"""
# logger.debug(f"Finding {n}th Fibonacci number")
logger.debug(s % ("fib(%d)" % (n)))
a = 0
b = 1
if n <= 0:
return a
elif n in (1, 2):
return b
else:
return fibonacci(n - 1, s % ("fib(%d) + %%s" % (n - 1))) + fibonacci(n - 2, s % ("fib(%d) + %%s" % (n - 2)))
我的目标是在日志中显示递归树,例如 fibonacci(5)
:
fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
and so on...
这可能吗?当前代码没有产生预期的输出。
当前输出:
fib(5)
fib(4) + fib(4)
fib(4) + fib(3) + fib(3)
fib(4) + fib(3) + fib(2) + fib(2)
fib(4) + fib(3) + fib(1) + fib(1)
fib(4) + fib(2) + fib(2)
fib(3) + fib(3)
fib(3) + fib(2) + fib(2)
fib(3) + fib(1) + fib(1)
想法:
一种方法可能是递归中的每个调用都将自身“报告”到它在树记录中的位置。然后我们可以逐层迭代。类似于:
def f(n):
t = ["None"] * (2**(n-1) + 1)
def g(n, i):
l = "(" if i & 1 else ""
r = ")" if not (i & 1) else ""
t[i] = "%sfib(%s)%s" % (l, n, r)
if n > 1:
g(n-1, 2*i+1)
g(n-2, 2*i+2)
g(n, 0)
print(t[0][0:-1])
i = 1
while 2**i-1 < len(t):
print(" + ".join(t[2**i-1:2**(i+1)-1]))
i += 1
输出:
f(5)
"""
fib(5)
(fib(4) + fib(3))
(fib(3) + fib(2)) + (fib(2) + fib(1))
(fib(2) + fib(1)) + (fib(1) + fib(0)) + (fib(1) + fib(0)) + None + None
(fib(1) + fib(0))
"""
您可以定义一个 class 来保存二叉树节点并构建树作为递归斐波那契函数的结果:
class BNode:
def __init__(self,value,left=None,right=None):
self.value = value
self.left = left
self.right = right
def print(self):
printBTree(self,nodeInfo=lambda n:(str(n.value),n.left,n.right))
from functools import lru_cache
@lru_cache() # optimize object count
def fiboTree(n): # (n is an index, not a count)
if n<2: return BNode(n)
a,b = fiboTree(n-2),fiboTree(n-1)
return BNode(a.value+b.value,a,b)
输出:
fiboTree(7).print()
13
____________/ \____________
5 8
_____/ \____ _______/ \______
2 3 3 5
/ \ __/ \_ __/ \_ _____/ \____
1 1 1 2 1 2 2 3
/ \ / \ / \ / \ / \ / \ __/ \_
0 1 0 1 1 1 0 1 1 1 1 1 1 2
/ \ / \ / \ / \ / \
0 1 0 1 0 1 0 1 1 1
/ \
0 1
你可以找到printBTree
函数here
如果只需要说明调用层次,可以直接使用printBTree函数:
def fibo(n):
n=int(n) # linking with strings to let zero come out as a node
return (f"fibo({n})",[None,str(n-2)][n>1], [None,str(n-1)][n>1])
printBTree(5,fibo)
fibo(5)
____________/ \____________
fibo(3) fibo(4)
/ \ _____/ \____
fibo(1) fibo(2) fibo(2) fibo(3)
/ \ / \ / \
fibo(0) fibo(1) fibo(0) fibo(1) fibo(1) fibo(2)
/ \
fibo(0) fibo(1)
要随手打印,我建议使用缩进来传达调用层次结构,否则重复添加将很难与调用者联系起来。
def fibo(n,indent=""):
if n<2: return n
print(indent[:-3] + "|_ "*bool(indent)
+ f"fibo({n}) = fibo({n-2}) + fibo({n-1})")
return fibo(n-2,indent+"| ")+fibo(n-1,indent+" ")
fibo(7)
fibo(7) = fibo(5) + fibo(6)
|_ fibo(5) = fibo(3) + fibo(4)
| |_ fibo(3) = fibo(1) + fibo(2)
| | |_ fibo(2) = fibo(0) + fibo(1)
| |_ fibo(4) = fibo(2) + fibo(3)
| |_ fibo(2) = fibo(0) + fibo(1)
| |_ fibo(3) = fibo(1) + fibo(2)
| |_ fibo(2) = fibo(0) + fibo(1)
|_ fibo(6) = fibo(4) + fibo(5)
|_ fibo(4) = fibo(2) + fibo(3)
| |_ fibo(2) = fibo(0) + fibo(1)
| |_ fibo(3) = fibo(1) + fibo(2)
| |_ fibo(2) = fibo(0) + fibo(1)
|_ fibo(5) = fibo(3) + fibo(4)
|_ fibo(3) = fibo(1) + fibo(2)
| |_ fibo(2) = fibo(0) + fibo(1)
|_ fibo(4) = fibo(2) + fibo(3)
|_ fibo(2) = fibo(0) + fibo(1)
|_ fibo(3) = fibo(1) + fibo(2)
|_ fibo(2) = fibo(0) + fibo(1)
这可以说明记忆的benefits/effect:
def fibo(n,indent="",memo=None):
if n<2: return n
if memo is None: memo = dict()
print(indent[:-3] + "|_ "*bool(indent) + f"fibo({n})",end=" = ")
if n in memo:
print("taken from memo")
else:
print(f"fibo({n-2}) + fibo({n-1})")
memo[n] = fibo(n-2,indent+"| ",memo)+fibo(n-1,indent+" ",memo)
return memo[n]
fibo(7) = fibo(5) + fibo(6)
|_ fibo(5) = fibo(3) + fibo(4)
| |_ fibo(3) = fibo(1) + fibo(2)
| | |_ fibo(2) = fibo(0) + fibo(1)
| |_ fibo(4) = fibo(2) + fibo(3)
| |_ fibo(2) = taken from memo
| |_ fibo(3) = taken from memo
|_ fibo(6) = fibo(4) + fibo(5)
|_ fibo(4) = taken from memo
|_ fibo(5) = taken from memo