递归
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
def fibonacci2(n):
# 使用空间换时间
data = {}
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
if n in data:
return data[n]
else:
r = fibonacci(n - 1) + fibonacci(n - 2)
data[n] = r
return r
return fibonacci(n)
def test_fibonacci():
assert fibonacci(6) == 8
assert fibonacci(12) == 144
assert fibonacci(100) == 354224848179261915075
# 100 = 99 + 98 ==> 99 = 98 + 97
def test_fibonacci2():
assert fibonacci2(6) == 8
assert fibonacci2(12) == 144
assert fibonacci2(100) == 354224848179261915075
# 100 = 99 + 98 ==> 99 = 98 + 97
多叉树
from typing import List
class Node:
def __init__(self, data):
"""
多叉树
:param data:
"""
self.data = data
# self.right self.left
self.children: List[Node] = []
def travel(self, node=None, depth=1, root=True):
if root:
node = self
if node is None:
return
yield node, depth
depth += 1
for child in node.children:
yield from self.travel(child, depth, False)
depth -= 1
def mindmap(self):
content = []
content.append('@startmindmap')
for node, depth in self.travel():
content.append(f'{"*" * depth} {node.data}')
content.append('@endmindmap')
return '\n'.join(content)
def test_mindmap():
root = Node(0)
node_1 = Node(1)
node_2 = Node(2)
node_3 = Node(3)
node_4 = Node(4)
node_5 = Node(5)
node_6 = Node(6)
node_4.children.append(node_6)
node_3.children.append(node_4)
node_3.children.append(node_5)
node_1.children.append(node_2)
node_1.children.append(node_3)
root.children.append(node_1)
print()
max_depth = 0
for node, depth in root.travel():
print(' ' * depth + " " + str(node.data))
print(root.mindmap())
思维导图
http://plantuml.ceshiren.com/uml/SoWkIImgoStCIybDBE3IKZ3Wqj9IC0GIMWf6OD8OH6efc80fBGKp2DUKoo4Lg0MY3G00
优惠券