2

k分木の葉の数を計算する関数 f(x) を見つけようとしています。たとえば、それぞれ -1、-2、-3 の 3 つの子を持つルート 4 で始まるツリーを作成したとします。葉は null 値ではなく、0 値のみになります。私は関数を理解しようとして過去 1 日を費やしましたが、正しい方向に進んでいるようには見えません。

元：

              4
         /    |     \
        3     2      1
     /  |\   /|     /  
    2   1 0 1 0    0  
   /|  /   /
  1 0 0   0
 /
0

7 葉。

どんな助けでも大歓迎です！ありがとう！

明確にするために、コードがツリーを再帰的に横断した場合と同じ答えを導き出す数式が必要です。

その他の例: {4,7}{5,13}{6,24}{7,44}{8,81}{9,149}{10,274}{11,504}{12,927}{13,1705}{14,3136} {15,5768}{16,10609}{17,19513}{18,35890}{19,66012}{20,121415}

 public int numleaves(TreeNode node) {
    if (node == null)
        return 0; 
    else if (node.getLeft() == null && node.getMiddle() == null && node.getRight() == null)
        return 1; 
    else
        return numleaves(node.getLeft()) + numleaves(node.getMiddle()) + numleaves(node.getRight());
}
4

4 に答える 4

2

ご質問にはお答えできませんが、解決策があります。k子供の数がに等しい場合の概要を説明することしかできません2。このケースk=3は、2 つの複素数と 1 つの実数解を持つ 3 次多項式につながります。非数値的な方法でそれらを導出するためのツールがここにはありません。

しかし、ケースを見てみましょうk=2。興味深いことに、この問題は、境界条件が異なることを除いて、フィボナッチ数と非常に密接に関連しています。

再帰式を書き留めるのは簡単です。

a(n) = a(n-1) + a(n-2)

境界条件a(1)=1とa(0)=1. これの特性多項式は

x^2 = x + 1

解x1 = 1/2 + sqrt(5)/2と を使用しx2 = 1/2 - sqrt(5)/2ます。だということだ

a(n) = u*x1^n + v*x2^n

探しuてvいるシーケンスの明示的な式です。得られた境界条件を入れる

u = (sqrt(5)+1)/(2*sqrt(5))
v = (sqrt(5)-1)/(2*sqrt(5))

すなわち

a(n) = (sqrt(5)+1)/(2*sqrt(5))*(1/2 + sqrt(5)/2)^n + (sqrt(5)-1)/(2*sqrt(5))*(1/2 - sqrt(5)/2)^n

のためにk=2。

于 2013-11-04T19:55:58.373 に答える
1

あなたのコードは、開始値 と でトリボナッチ数列を計算しているようです。これは、On-Line Encyclopedia of Integer Sequences のシーケンス A000073で、そのシーケンスの最初のエントリではなく 3 番目のエントリから始まります。百科事典ページのコメント セクションでは、明示的な式が示されています。これは次数 3 の特性多項式による線形再帰関係であるため、その多項式の根に関して閉じた形式の解があります。以下は、最初のいくつかの値を生成する特定の式に基づく Python 2 コードの短い部分です。(簡略化のために以下の編集を参照してください。)112

from math import sqrt

c = (1 + (19 - 3 * sqrt(33))**(1/3.) + (19 + 3 * sqrt(33))**(1/3.)) / 3.
m = (1 - c) / 2
p = sqrt(((3*c - 5)*(c+1)/4))
j = 1/((c-m)**2 + p**2)
b = (c - m) / (2 * p*((c - m)**2 + p**2))
k = complex(-j / 2, b)
r1 = complex(m, p)

def f(n):
    return int(round(j*c**(n+2) + (2*k*r1**(n+2)).real))

for n in range(0, 21):
    print n, f(n)

そして出力：

0 1
1 1
2 2
3 4
4 7
5 13
6 24
7 44
8 81
9 149
10 274
11 504
12 927
13 1705
14 3136
15 5768
16 10609
17 19513
18 35890
19 66012
20 121415

編集: 上記のコードは不必要に複雑です。このround操作により、 の第 2 項をf(n)省略でき (増加するにつれてゼロに収束しますn)、第 1 項の式を簡略化できます。同じ出力を生成する簡単なコードを次に示します。

s = (19 + 297**0.5)**(1/3.)
c = (1 + s + 4/s)/3
j = 3 - (2 + 1/c)/c
for n in range(0, 32):
    print n, int(round(c**n / j))
于 2013-11-04T21:08:19.370 に答える
0

仕方ありませんが、そこに二項木が見えます。http://en.wikipedia.org/wiki/Binomial_heap

適切な近似は、パスカル三角形の k 番目の行の合計であると思います。ここで、k はルート ノードの番号を表します。

于 2013-11-04T19:16:40.967 に答える