構造体と実体の違いや、Javaに慣れている学生さんに あらためて、データ構造のイメージを持って欲しいので、 以下のコードを示す。

struct Complex {
   double re ;
   double im ;
} ;
struct Complex2 {
   double* pre ;
   double* pim ;
} ;
void main() {
   // メモリ確保失敗のNULLチェックは省略
   struct Complex a ;
   struct Complex* p ;
   struct Complex2 b ;
   struct Complex2* q ;

   a.re = 1.2 ;
   a.im = 2.3 ;

   p = (struct Complex*)malloc( sizeof( struct Complex ) ) ;
   p->re = 1.2 ;
   p->im = 2.3 ;
   // in Java
   // p = new Complex ;
   // p.re = 1.2 ;
   // p.im = 2.3 ;

   b.pre = (double*)malloc( sizeof( double ) ) ;
   *(b.pre) = 1.2 ;
   b.pim = (double*)malloc( sizeof( double ) ) ;
   *(b.pim) = 2.3 ;

   q = (struct Comple2*)malloc( sizeof( struct Complex2 ) ) ;
   q->pre = (double*)malloc( sizeof( double ) ) ;
   *(q->pre) = 1.2 ;
   q->pim = (double*)malloc( sizeof( double ) ) ;
   *(q->pim) = 2.3 ;
}

上記プログラムのメモリの格納イメージ図を以下に示す。

先週に2分木に対する再帰などを交えたプログラムの説明をしたので、 今週は木の生成について、AVL木などを交えて説明。 後半は、情報処理センターで演習。

#include <stdio.h>
#include <stdlib.h>
// 2分木の宣言
struct Tree {
   int data ;
   struct Tree* left ;
   struct Tree* right ;
} ;
// 木の根
struct Tree* top = NULL ;
// 木のノードを構築する補助関数
struct Tree* tcons( int x , struct Tree* l , struct Tree* r ) {
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->data = x ;
      n->left = l ;
      n->right = r ;
   }
   return n ;
}
// 木を表示する補助関数。枝の左右がわかる様に...
void print( struct Tree* p ) {
   if ( p == NULL ) {
      printf( "x" ) ;
   } else {
      printf( "(" ) ;
      print( p->left ) ;
      printf( " %d " , p->data ) ;
      print( p->right ) ;
   printf( ")" ) ;
   }
}
// 木に1件のデータを追加する補助関数
void entry( int x ) {
   struct Tree** ppt = &top ;

   while( (*ppt) != NULL ) {
      if ( (*ppt)->data == x )
         break ;
      else if ( (*ppt)->data > x )
         ppt = &( (*ppt)->left ) ;
      else
         ppt = &( (*ppt)->right ) ;
   }
   if ( *ppt == NULL )
      (*ppt) = tcons( x , NULL , NULL ) ;
   }
int main() {
   entry( 51 ) ;
   entry( 26 ) ;
   entry( 76 ) ;
   entry( 60 ) ;
   print( top ) ;
   // ((x 26 x) 51 ((x 60 x) 76 x))

   top = NULL ;
   entry( 26 ) ;
   entry( 51 ) ;
   entry( 60 ) ;
   entry( 76 ) ;
   print( top ) ;
   // (x 26 (x 51 (x 60 (x 76 x))))
}

前回の授業で、処理速度のオーダ記法について解説し、 実際例と処理速度の問題について解説する。 後半は、再帰呼び出しの処理速度見積もりのための再帰方程式を示す。

特殊な処理時間の見積もり

前回授業の最後に検討しておくようにと伝えた、 の処理時間のオーダについて、Nが巨大となった時の、最大項を見つければ良いことから、 が、N→∞において 発散するのか収束するのかを求める方法にて説明する。

また、2つのアルゴリズムがNの増加で処理時間が変化する時の事例として、 「データ件数が10件で、最大選択ソートが10msec、クイックソートが20msec出会った場合、 データ100件では、どちらが速いか？、この結果から、 データ件数がいくつ以上であれば、どちらの方法が良いか？」 といった問題について説明する。

最大選択ソートであれば、 より、 であるとする。 一方、クイックソートは、 より、 であるとする。 より、 。 より、 。

これより、データ100件の場合には、 となる。 また、 となりクイックソートの方が速い。

さらに、 となるNを求めれば、N件以上は クイックソートが速い…といった件数を求められる。

再帰関数と再帰方程式

再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。

// 階乗
int fact( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x * fact( x-1 ) ;
}
// ピラミッド体積
int pyra( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x*x + pyra( x-1 ) ;
}
// フィボナッチ数列
int fib( int x ) {
   if ( x <= 2 )
      return 1 ;
   else
      return fib( x-1 ) + fib( x-2 ) ;
}

これらの関数の結果について考えるとともに、この計算の処理時間を説明する。 最初のfact(),pyra()については、 x=1の時は、関数呼び出し,x<=1,return といった一定の処理時間を要し、 で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理に加え、x-1の値で再帰の処理時間がかかる。 このことから、 で表せる。 これを代入によって解けば、 で表せる。 こういった式は、再帰方程式と呼ばれ、一般式を求めることとなる。

最後に、再帰方程式の事例として、ハノイの塔の処理時間について説明し、 数学的帰納法での証明を示す。

ハノイの塔

ハノイの塔は、３本の塔にN枚のディスクを積み、ディスクの上により大きいディスクを積まずに、移動させるパズル。 ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 ということが予想される。

この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚と、その上の(N-1)枚のディスクに分けて考える。 これより、

ということが言える。 ディスクが 枚で、予想が正しいと仮定すると、 枚では、

となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。