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

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

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

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

<実行例>

• 出力に、上の情報が含まれていれば、どんなプログラムでもよい。

• たとえば、下のようにnodeコマンドを作る。引数は3つ。b, m, dをとる。

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とわかる。

• しかし、このようなプログラムでは、bやdを大きくするとすぐに表示できなくなる。

algo2>node 3 4 3
branching factor= 3, max depth= 4 depth= 3
d:0   0
d:1   1  2  3
d:2   4  5  6  7  8  9 10 11 12
d:3  13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

• そこで、ノードを全て出力するのではなく、端のノードだけを求め出力するほうがよい。

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

• このページでは、上のnode.cを公開します。

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

• gccではコンパイル時に、gcc -o node -lm node.c のように、-lmが必要
• ./node 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);
      for (j = 0; j < pow(b,i); j++) {
         printf("%3d",node);
         node++;
      }
      printf("\n");
   }

   return 0;
}