STEP 5.1.1　モデル木　(分枝数b, 最大の深さm) の 特徴的なノード

<背景> 根（ルート）のノード番号を0とする。ルートしかない木は深さ0とする。

<問題> 木の分岐数を b, 最大の深さをmとするとき、深さdにあるノードを知りたい。特に、木の左端と右端のノード名を知りたい。

• この問題では、mとdを同じと考えてもよい。情報工学実験ではmとdの2つの情報は異なる。
• bとmは、探索される木全体を示している情報。それに対してdは、探索アルゴリズムが対象とする深さを表現している。
• これらのノードは、ルートからの深さは同じだが、アルゴリズムによって探索結果　（発見の順序や、実行時の計算量）が異なる。
• 実験で探索パフォーマンスを計測する際に必要になります。

<実行例>

• 問題には、以下のnodeプログラムを公開しています。

algo2>node 2 6 3
branching factor= 2, max depth= 6 depth= 3
d:0 0
d:1 1 2
d:2 3 4 5 6
d:3 7 8 9 10 11 12 13 14

• 分岐数2, 最大の深さ6の木について、深さ3までのノードを表示。
• ここから、この木の深さ3の場合は、左端のノードが7、右端のノードが14とわかる。

• ノードを全て出力するのではなく、端のノードだけを求め出力するほうがよい。 node.cを、node1.cに変えてみよう。下は、実行結果。

algo2>node1 3 4 3
branching factor= 3, max depth= 4 depth= 3
d:0     0 -     0
d:1     1 -     3
d:2     4 -    12
d:3    13 -    39

• 端のノードだけを出力するCプログラム　node1.cを、下に公開します。

• pow関数(べき乗関数）の利用に注意。引数と値はdouble型ですが、引数はintのまま実行しています。
• pow関数には、#include <math.h> も必要。

• gccではコンパイル時に、gcc -o node1 -lm node1.c のように、-lmが必要
• 実行する場合は、./node1 3 4 3 のように、コマンドの前に ./をつけること。

解答例
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main (int argc, char *argv[]){
   int b, m, d; /* Branching factor, Max depth */
   int node, i, j;

   if (argc != 4) {
      printf("Usage: command [branching factor] [max depth] [depth]\n");
      exit (0) ;
   }

   b = atoi(argv[1]);
   m = atoi(argv[2]);
   d = atoi(argv[3]);

   printf("branching factor=%2d, max depth=%2d depth=%2d\n", b, m, d);

   node = 0;
   for (i = 0; i <= d; i++) {
      printf("d:%d ",i);
      printf("%5d - ",node);
      node = node + pow(b, i) - 1;
      printf("%5d\n",node);
      node++;
   }

   return 0;
}