0

假设我们有一个三角形，每个节点都有 K 个孩子。

K = 2 的示例是：

  1
 2 3
4 5 6

K = 3 的示例是：

    1
  2 3 4
5 6 7 8 9

K = 4 的示例是：

        1
     2 3 4 5
  5 6 7 8 9 1 2

等等

  1. 我想将这些三角形存储在一个数组中。给定元素总数 T 和每个节点 K 的子节点数，我希望检索三角形的总高度（假设它们是完整的三角形）

  2. 我也在寻找数组中每个元素对每个孩子的偏移量。我知道对于上面 K = 2 的示例，数组是 [1, 2, 3, 4, 5, 6] ，其中每个级别 L 的偏移量是 L * (L + 1) / 2 （因为级别 1 有 1元素，2级有2个，3级有3个......）

编辑：这个例子是正确的。每个节点都可以访问 K 个子节点。对于 K = 3 1 可以访问 2 3 和 4。2 可以访问 5 6 和 7。3 可以访问 6 7 和 8。

这些是三角形，而不是图形或树。

4

2 回答 2

1

既然您已经阐明了您的要求...

对于 K=2，有

1
1+1
1+1+1
...

每个级别中的元素，这是系列1,2,3,.... 如果n是级别编号，那么每个级别都有n元素。请注意，这也可以写成1+1(n-1)

对于 K=3 有

1
1+2
1+2+2
...

每个级别的元素，这是系列1,3,5,...；每个级别都有1+2(n-1)元素。

对于 K=4，有

1
1+3
1+3+3
...

每个级别的元素，这是系列1,4,7,...。每个级别都有1+3(n-1)元素。

在每个三角形的每一层都有1+(K-1)(n-1)元素。我希望你能从这里继续。

于 2012-08-24T10:57:20.870 回答
0

T高度三角形的元素总数h将是：

T = ∑<em>1...h (1 + (K-1)(n-1))
T = h + (K-1) * ∑<em>1...h (n-1)
T = h + (K-1) * ∑<em>0..h-1 (n)
T = h + (K-1) * ((h-1)² + h-1) / 2
T = h + (K-1) * (h² + 1 - 2h + h-1) / 2
T = h + (K-1) * (h² - h) / 2

计算高度

因此，要获得高度h，请插入 的值K并求解方程。K这是一个等于 3的简单案例的示例。

T = h + (K-1) * (h² - h) / 2
T = h + (3-1) * (h² - h) / 2
T = h + (h² - h)
T = h²
h = √T

计算偏移量

至于偏移量，您使用我们用来计算元素总数但设置h为 height-1 的相同方程。这是一个在 aK为 4 的三角形中获取第 3 行偏移量的示例。

偏移量(h) = h-1 + (K-1) * ((h-1)² - (h-1)) / 2
偏移量(3) = 3-1 + (4-1) * ((3- 1)² - (3-1)) / 2
偏移量(3) = 2 + 3 * (4 - 2) / 2
偏移量(3) = 5

于 2012-08-24T21:37:12.570 回答