3

我被困在一个涉及项目树的编程问题上。问题本身只是更大问题的子问题（但我不会在这里发布它，因为它并不真正相关）。任何人的问题是：

我正在尝试遍历树中的每条路径并计算相关值。

情况例如在这棵树中：

     a
  b     b

现在我应该得到的结果是乘法如下：

离开1 = a * b

离开2 = a * (1-b)

离开3 = (1-a) * b

离开4 = (1-a) * (1-b)

因此，树中较低一级的叶子基本上就是结果（请注意，它们在现实中并不存在，只是概念性的）。

现在，我想递归地执行此操作，但存在一些问题： a 和 b 的值是在遍历期间生成的，但例如 b 的值应该只生成 1 次。所有值都是 0 或 1。如果取节点 A 的左子节点，则在乘法中使用值 A。您使用值 1-A 的正确路径。

此外，树总是完美的，即完整且平衡。

现在我有什么（我用python编程，但它更多的是我对这个问题感兴趣的一般算法）：

def f(n):
  if n == 1:
     return [1]
  generate value #(a, b or whatever one it is)
  g = f(n/2)
  h = scalarmultiply(value,g)
  return h.append(g - h)

请注意，g 和 h 是列表。我的一位教授提供了这段代码作为可能的帮助，但我不认为这能达到我想要的效果。至少，它不会给我一个列表 h ，其中包含每个路径的结果。特别是，我不认为它区分b和1-b。我看错了吗，我应该怎么做？

我在编程方面不是很有经验，所以如果可以的话，试着简单地解释一下:-)

4

2 回答 2

0

尝试这样的事情：

def f(element_count):
    if element_count == 1:  #<-------------------------------A
        return [1,] #at the root node - it has to be 1 otherwise this is pointless
    current_value = get_the_value_however_you_need_to()#<----B
    result_so_far = f(element_count/2)  #<-------------------C
    result = []
    for i in result_so_far:#<--------------------------------D
        result.append(i*current_value)
        result.append(i*(1-current_value))
        result.append((1-i)*current_value)
        result.append((1-i)*(1-current_value))
    return result

以下是它的工作原理：

假设您想使用三层金字塔。然后 element_count 将是第三层上的元素数，因此您可以调用f(4). A 处的条件失败，因此我们继续到 B 处生成下一个值。现在在 C 我们调用f(2).

中的过程f(2)类似，f(2)调用f(1)并f(1)返回[1,]. f(2)现在我们开始回到树的最宽处......

我不确定你的讲师在功能结束时得到了什么。for 循环执行您解释的乘法并建立一个列表，然后返回

于 2013-01-30T23:20:33.600 回答
0

如果我理解正确，你想建立一个像这样的二叉树：

      A
     / \
    /   \
   /     \
  B       C
 / \     / \
D   E   F   G

其中，较低级别节点的布尔值（1、0或它们的 Python 等效项True和False）是使用以下规则从其父节点和祖父节点的值计算的：

D = A and B
E = A and not B
F = not A and C
G = not A and not C

也就是说，每个节点的右后代根据它的逆计算它们的值。您进一步指出，树由一个根值 ( a) 和另一个用于根的两个子项 ( b) 的值定义。

这是一个函数，它将计算这种树的任何节点的值。树的位置由整数索引定义，就像二叉堆通常一样，节点的父节点N是N//2，它的子节点是2*Nand 2*N+1（根节点是1）。它使用记忆字典来避免重复重新计算相同的值。

def tree_value(n, a, b, memo=None):
    if memo is None:
        memo = {1:a, 2:b, 3:b} # this initialization covers our base cases

    if n not in memo: # if our value is unknown, compute it
        parent, parent_dir = divmod(n, 2)
        parent_val = tree_value(parent, a, b, memo) # recurse

        grandparent, grandparent_dir = divmod(parent, 2)
        grandparent_val = tree_value(grandparent, a, b, memo) # recurse again

        if parent_dir: # we're a right child, so invert our parent's value
            parent_val = not parent_val

        if grandparent_dir: # our parent is grandparent's right child, so invert
            grandparent_val = not grandparent_val

        memo[n] = parent_val and grandparent_val

    return memo[n]

您可能会注意到，在计算出父级的值之后，祖父级的值将始终存在于 memo 字典中，您可能会稍微提高性能，但我已将其省略，因此代码更清晰。

如果您需要有效地计算同一棵树中的许多值（而不仅仅是一个），您可能希望在某处保留一个永久的备忘录字典，可能作为全局字典中的一个值，由一个(a, b)元组键控。

于 2013-01-31T21:01:33.937 回答