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,.... 場合、各レベルに要素があります。これは次のように書くこともできることに注意してくださいnn1+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高さ-1 に設定します。Kaが 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 に答える