中级农民
- 积分
- 153
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2014-7-9
- 最后登录
- 1970-1-1
|
tree结构学的时候就觉得理解的不清楚,做起题来更捉急。extra做到最后一题,看着答案都觉得脑袋要炸了。必须再多刷题,多巩固
# 1.1.2
def foo(lst):
"""
>>> x = [1, 2, 3, 4, 5, 6]
>>> foo(x)
[0, 6, 20]
"""
return [lst[i] * i for i in range(len(lst)) if i % 2 == 0]
# 2
# Constructor
def tree(value, branches=[]):
for branch in branches:
assert is_tree(branch)
return [value] + list(branches)
# Selectors
def root(tree):
return tree[0]
def branches(tree):
return tree[1:]
def is_leaf(tree):
return not branches(tree)
def is_tree(tree):
if type(tree) != list or len(tree) < 1:
return False
for branch in branches(tree):
if not is_tree(branch):
return False
return True
# 2.2.1
def square_tree(t):
"""Return a tree with the square of every element in t"""
return tree(root(t)**2, [square_tree(branch) for branch in branches(t)])
# 2.2.2
def height(t):
"""Return the height of a tree"""
if is_leaf(t):
return 0
return 1 + max([height(branch) for branch in branches(t)])
# 2.2.3
def tree_size(t):
"""Return the size of a tree."""
if is_leaf(t):
return 1
return 1 + sum([tree_size(branch) for branch in branches(t)])
# 2.2.4
def tree_max(t):
"""Return the max of a tree."""
if is_leaf(t):
return root(t)
return max([root(t)]+[tree_max(branch) for branch in branches(t)])
#2.3.1
def reduce(fn, s, init):
reduced = init
for x in s:
reduced = fn(reduced, x)
return reduced
def apply_to_all(fn, s):
return [fn(x) for x in s]
from operator import add, mul
def eval_tree(tree):
"""Evaluates an expression tree with functions as root
>>> eval_tree(tree(1))
1
>>> expr = tree(mul, [tree(2), tree(3)])
>>> eval_tree(expr)
6
>>> eval_tree(tree(add, [expr, tree(4)]))
10
"""
if is_leaf(tree):
return root(tree)
if root(tree) == mul:
init = 1
else:
init = 0
return reduce(root(tree), apply_to_all(eval_tree, branches(tree)), init)
#2.3.2
def hailstone_tree(n, h):
"""Generates a tree of hailstone numbers that will reach N, with height H.
>>> hailstone_tree(1, 0)
[1]
>>> hailstone_tree(1, 4)
[1, [2, [4, [8, [16]]]]]
>>> hailstone_tree(8, 3)
[8, [16, [32, [64]], [5, [10]]]]
"""
if h == 0:
return tree(n)
h_b = [hailstone_tree(2 * n, h - 1)]
if (n - 1) % 3 == 0 and (n - 1) // 3 > 1:
h_b += [hailstone_tree((n - 1) // 3, h - 1)]
return tree(n, h_b)
#2.3.3
def find_path(tree, x):
""" Return a path in a tree to a leaf with value X,
None if such a leaf is not present.
>>> t = tree(2, [tree(7, [tree(3), tree(6, [tree(5), tree(11)])]), tree(15)])
>>> find_path(t, 5)
[2, 7, 6, 5]
>>> find_path(t, 6)
[2, 7, 6]
>>> find_path(t, 10)
"""
if root(tree) == x:
return [x]
for path in [find_path(branch, x) for branch in branches(tree)]:
if path:
return [root(tree)] + path |
|