番号2の累乗を理解する

Question

ノードにN個の子があり、高さがHの場合、ノードの総数はN pow（H）に等しいか、私は、単一のノードでツリーの高さを想定しています

Answer 1

は0

である私はまた、葉以外のすべてのノードの子の数がN

ある今のNum（X）は数あるみようと仮定しています高さXの木にあるノードの数です。私たちが求める答えはNum（H）です。

今、私たちは漸化式を導き出すことができます述べたように

Num(H) = 1 + N.Num(H-1) 

用語1は、根を占め、各Num(H-1)され、ルートの子として、そこに根をサブツリーの高さを表し、主ルートのN個の子孫です。

同様

、

民（H）= 1 + N（1 + N.Num（H-2））= 1 + N + N .Num（H-2）= 1+ N + N + N + ... + N ^H .Num（0）

しかし、高さ0のツリー内のノードの数が1であるので、民（0）= 1すなわち単一のノードである。

したがって、民（H）=（N ^{H + 1} -1）/（N-1）Iは、N個の数字を持っている場合、私は2電源までのアドレス空間を収容することができる。また