ホーム » スタッフ » 斉藤徹 » 講義録 » 情報構造論

情報構造論」カテゴリーアーカイブ

2020年7月
 1234
567891011
12131415161718
19202122232425
262728293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

リスト処理

リスト構造

リスト構造は、データと次のデータへのポインタで構成され、必要に応じてメモリを確保することで、配列の上限が制限にならないようにする。また、次のデータへのポインタでつなげているため、途中へのデータ挿入が簡単にできるようにする。

まずは、メモリ確保とポインタをつなげるイメージを確実に理解してもらうために、1つ1つのデータをポインタでつなげる処理を示す。

#include <stdio.h>
#include <stdlib.h>

// List構造の宣言
struct List {
   int          data ;  // データ保存部
   struct List* next ;  // 次のデータへのポインタ
} ;

int main() {
   struct List* top ;   // データの先頭
   struct List* p ;

   // (1)
   top = (struct List*)malloc( sizeof( struct List ) ) ;
   top->data = 111 ;
   // (2)
   top->next = (struct List*)malloc( sizeof( struct List ) ) ;
   top->next->data = 222 ;
   // (3)
   top->next->next = (struct List*)malloc( sizeof( struct List ) ) ;
   top->next->next->data = 333 ;
   top->next->next->next = NULL ; // 末尾データの目印

   for( p = top ; p != NULL ; p = p->next ) {
      printf( "%d¥n" , p->data ) ;
   }
   return 0 ;
}

このようなメモリーの中のポインタの指し示す番地のイメージを、具体的な番地の数字を書いてみると、以下のような図で表せる。先頭の111が入った部分が1000番地であったなら、topというポインタには1000番地が入っている。

NULLって何?

前回の授業で説明した、次の配列の添え字の番号を使う方式では、データの末尾を示すためには、-1 を使った。-1 は、配列の添え字で通常ありえない値であり、次のデータはないという目印とした。

同じように、C言語では、通常あり得ないポインタとして、0 番地を示す NULL が定義されている。

#define NULL 0

補助関数

上記のプログラムでは、(struct…)malloc(sizeof(…))を何度も記載し、プログラムが分かりにくいので、以下に示す補助関数を使うと、シンプルに記載できる。

struct List* cons( int x , struct List* n ) {
   struct List* ans ;
   ans = (struct List*)malloc( sizeof( struct List ) ) ;
   if ( ans != NULL ) {
      ans->data = x ;
      ans->next = n ;
   }
   return ans ;
}

int main() {
   struct List* top ;
   top = cons( 111 , cons( 222 , cons( 333 , NULL ) ) ) ;
   :
   return 0 ;
}

補助関数の名前の cons は、constructor の略であり、古くから使われている List Processor(LISP) というプログラム言語でのリスト(セル)を生成する関数が cons 。

typedefを使った書き方

List構造の宣言は、古い書き方では typedef を使うことも多い。typedef は、型宣言において新しい型の名前をつける命令。

// typedef の使い方
//    typedef 型宣言 型名 ;
typedef unsigned int uint32 ; // 符号なし32bit整数をシンプルに書きたい
uint32 x = 12345 ;

typedef struct LIST {     // 構造体のタグ名と新しくつける型名と重複できない
      int   data ;        // のでこの時点のタグ名は "LIST" としておく
      struct LIST* next ;
   } List ;

List* cons( int x , List* n ) {  // C++なら struct List { ... } ; と書く
   List* ans ;                   // だけでこういう表記が可能
   ans = (List*)malloc( sizeof( List ) ) ;
   :
   ((略))
}
int main() {
   List* top ;
   top = cons( 111 , cons( 222 , cons( 333 , NULL ) ) ) ;
   :
   ((略))
}

最近のC言語(C++)では、構造体のタグ名がそのまま型名として使えるので、こういう書き方をする必要はなくなってきている。

// 最近のC++なら...
struct List {
public:
   int   data ;
   List* next ;
public:
   List( int x , List* n )
     : data( x ) , next( n ) {}
} ;

int main() {
   List* top = new List( 1 , new List( 2 , new List( 3 , NULL ) ) ) ;
   :
}

LISPと関数型プログラミング言語

LISPの歴史は長く、最古のFORTRAN,COBOLに次ぐ3番目ぐらいに遡る。最初は、人工知能(AI)のプログラム開発のための関数型プログラミング言語として作られた。特徴として、データもプログラムもすべてリスト構造(S式)で表すことができ、プログラムは関数型に基づいて作られる。

関数型プログラミングは、Ruby や Python でも取り入れられている。関数型プログラミングは、処理を関数をベースに記述することで「副作用を最小限にすることができ」、極端な話をすればループも再帰呼出しの関数で書けばいい…。

LISPの処理系は、最近では Scheme などが普通だが、プログラムエディタの Emacs は、内部処理が LISP で記述されている。

古いAI※※と最近のAIの違い

最近では、AI(Artificial Intelligence) という言葉が復活してきたが、LISP が開発された頃の AI と最近注目されている AI は、微妙に異なる点がある。

LISPが開発された頃の AI は、関数型のプログラム言語で論理的思考を表現することが目標であった。頭脳を左脳と右脳の違いで表現することが多いが、どちらかというと「分析的で論理的に優れ、言語力や計算機能が高い」とされる左脳を作り出すようなもの。しかしながら、この時代では、漠然としたパターンを認識したりするような「感覚的、直感的な能力に優れ総合判断力を司る右脳」のような処理は苦手であった。

しかしながら、最近注目されている AI は、脳神経を真似たニューラルネットワークから発展した機械学習ディープラーニングという技法により今まで難しかった右脳の機能を実現することで、左脳と右脳の機能を兼ね備えたものとなっている。

将棋のプログラミングで例えるなら、左脳(古いAI)に例えられるのが正確に先の手を読む機能であり、右脳に例えられる機能が大局観(全体の良し悪しを見極める判断能力)といえる。

簡単なリスト処理の例

先に示したリスト構造について簡単なプログラム作成を通して、プログラミングに慣れてみよう。

// 全要素を表示する関数
void print( struct List* p ) {
   for( ; p != NULL ; p = p->next )
      printf( "%d " , p->data ) ;
   printf( "¥n" ) ;
}
// データ数を返す関数
int count( struct List* p ) {
   int c = 0 ;
   for( ; p != NULL ; p = p->next )
      c++ ;
   return c ;
}
int main() {
   struct List* top = cons( 111 , cons( 444 , cons( 333 , NULL ) ) ) ;
   print( top ) ;
   printf( "%d¥n" , count( top ) ) ; 
   return 0 ;
}

リスト処理を自分で考えて作成

以下のようなプログラムを作ってみよう。意味がわかって慣れてくれば、配列の部分の for の回し方が変わっただけということに慣れてくるだろう。

// 全要素の合計
int sum( struct List* p ) {
   // sum( top ) → 888
   自分で考えよう
}
// リストの最大値を返す
int max( struct List* p ) {
   // max( top ) → 444 (データ件数0の場合0を返す)
   自分で考えよう
}
// リストの平均値を返す
double mean( struct List* p ) {
   // (111+444+333)/3=296.0
   自分で考えよう
}
// リストの中から指定した値の場所を返す
int find( struct List* p , int key ) {
   // find( top , 444 ) = 1 (先頭0番目)
   // 見つからなかったら -1
   自分で考えよう
}

再帰呼び出しでリスト処理

リスト処理の応用のプログラムを作るなかで、2分木などのプログラミングでは、リスト処理で再帰呼出しを使うことも多いので、先に示したプログラムを再帰呼び出しで書いたらどうなるであろうか?

// 全データを表示
void print( struct List* p ) {
   if ( p == NULL ) {
      printf( "¥n" ) ;
   } else {
      printf( "%d " , p->data ) ;
      print( p->next ) ; // 末尾再帰
   }
}
// データ数を返す関数
int count( struct List* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return 1 + count( p->next ) ; // 末尾再帰
}
// 全要素の合計
int sum( struct List* p ) {
   // sum( top ) → 888
   自分で考えよう
}
// リストの最大値を返す
int max( struct List* p ) {
   // max( top ) → 444 (データ件数0の場合0を返す)
   自分で考えよう
}
// リストの中から指定した値を探す。
int find( struct List* p , int key ) {
   // find( top , 444 ) = 1 
   // 見つかったら1 , 見つからなかったら 0
   自分で考えよう
}

理解度確認

上記プログラム中の sum() , max() , find() を再帰呼び出しをつかって記述せよ。

リスト構造について

データ処理において、配列は基本的データ構造だが、動的メモリ確保の説明で述べたように、基本の配列では大きさを変更することができない。これ以外にも、配列は途中にデータを挿入・削除を行う場合、の処理時間を伴う。以下にその問題点を整理し、その解決策であるリスト構造について説明する。

配列の利点と欠点

今までデータの保存には、配列を使ってきたが、配列は添字で場所を指定すれば、その場所のデータを簡単に取り出すことができる。配列には苦手な処理がある。例えば、配列の中から目的のデータを高速に探す方式として、2分探索法を用いる。

int find( int array[] , int left , int right , int key ) {
   // データは left から right-1までに入っているとする。
   while( left < right ) {
      int mid = (left + right) / 2 ; // 中央の場所
      if ( array[ mid ] == key )
         return mid ;                // 見つかった
      else if ( array[ mid ] > key )
         right = mid ;               // 左半分にある
      else
         left = mid + 1 ;            // 右半分にある
   }
   return -1 ; // 見つからない
}

しかし、配列の中に新たに要素を追加しようとするならば、データは昇順に並んでいる必要があることから、以下のようになるだろう。

void entry( int array[] , int* psize , int key ) {
   // データを入れるべき場所を探す処理
   for( int i = 0 ; i < *psize ; i++ ) // O(N) の処理だけど、
      if ( array[ i ] > key )          // O(log N) でも書けるけど
         break ;                       // 単純に記載する。
   if ( i < *psize ) {
      // 要素を1つ後ろにずらす処理
      for( int j = *psize ; j > i ; j-- ) //  O(N)の処理
         array[ j ] = array[ j - 1 ] ;
      array[ i ] = key ; 
   } else {
      array[ *psize ] = key ;
   }
   (*psize)++ ;
}

これで判るように、データを配列に追加する場合、途中にデータを入れる際にデータを後ろにずらす処理が発生する。

この例は、データを追加する場合であったが、不要となったデータを取り除く場合にも、データの場所の移動が必要である。

順序が重要なデータ列で途中へのデータ挿入削除

例えば、アパート入居者に回覧板を回すことを考える。この中で、入居者が増えたり・減ったりした場合、どうすれば良いか考える。
通常は、自分の所に回覧板が回ってきたら、次の入居者の部屋番号さえわかっていれば、回覧板を回すことができる。

  101   102   103   104   105   106
[ 105 | 106 |  -1 | 102 | 104 | 103 ]

このように次のデータの場所という概念を使うと、データの順序を維持して扱うことができる。

struct LIST {
   int data ;
   int next ;
} ;
struct LIST array[] = {
   /*0*/ { 11 ,  2 } , 
   /*1*/ { 67 ,  3 } ,  // 末尾にデータ34を加える
   /*2*/ { 23 ,  4 } ,  // { 23 , 5 } ,
   /*3*/ { 89 , -1 } ,  // 末尾データの目印
   /*4*/ { 45 ,  1 } ,
   /*5*/ {  0 ,  0 } ,  // { 34 , 4 } ,
} ;
for( int idx = 0 ; idx >= 0 ; idx = array[ idx ].next ) {
   printf( "%d¥n" , array[ idx ].data ) ; 
}

 

この方法を取れば、途中にデータ入れたり、抜いたりする場合に、データの移動を伴わない。

しかし、配列をベースにしているため、配列の上限サイズを超えて格納することはできない。

遠隔の小テストを実施

遠隔授業の中、自分の担当科目で中間試験(小テスト)を実施した。学校としてはレポート課題で評価していいとの話なのでテスト形式の必要性はないけど、レポート課題方式ばかりだと後々の理解力が心配だし、やってみた。
Teamsでテスト問題を配布し、時間が来たらOfficeLenseで自分の回答をスキャンして、PDFで提出。問題は同じようなものを2つづつ準備し、出席番号が偶数なら、出席番号を2で割った値が偶数なら…で、問題が分散するようにしてある。問題の内容も、「図を交えて具体的に説明」といった形式の問題とした。
実施前は、OfficeLense使いこなせない学生が出ないか心配だったり、裏で情報交換で全員同じような回答にならないかの心配をしてた。でも、ざっと見た雰囲気だと、裏情報交換は少ないかなぁ。

裏で情報交換する可能性もあるけど、そこはあえて何も言わないようにした。「どうせ、みんな裏で情報交換するんだろーしぃ〜♪」といった雰囲気をだすと「だったら、やってもいいのか…」と思われるのもまずいので、実施方法だけを事前方法に伝えていた。

遠隔授業6回目の反省

遠隔授業も6回目。Web掲載の講義資料に、Microsoft Edgeのペン書き機能で、図などを交えた説明のスタイルでやってきた。私としては、講義資料のWeb掲載は数年前からやっていたので、黒板がWeb画面になっただけ…の感覚。

んで、今日は出席確認もかねてForms機能でアンケートで意見聞いたら、「書き込みのメモをとるのが追いつかない」とのご意見。

一応、講義の録画機能は使ってるし、書き込みすぎて逆にみづらくなった書き込みを消したりしてるけど、真面目にノートをとる人にしてみれば、ペースが早いみたい。

これまでも、できるだけ雑談を交えながら、ペースを落とすようにしているけど、雑談ネタでも書き込みしながら説明するもんだから、相変わらず追いつかないか… 反省!!

様々なデータの覚え方

前回の malloc() + free() の説明では、実例が少なくイメージがわかりにくいので、名前と年齢のデータを覚える場合の様々な方法を議論する。最後に前期中間のプログラム課題を示す。

malloc+freeの振り返り

// 文字列(可変長)の保存
char  str[] = "ABCDE" ;
char* pc ;
pc = (char*)malloc( strlen( str ) + 1 ) ;
if ( pc != NULL ) { // ↑正確に書くと sizeof( char ) * (strlen(str)+1)
   strcpy( pc , str ) ;
   ////////////////////
   // pcを使った処理
   ////////////////////
   free( pc ) ;
}
//
// 可変長の配列の保存
int  data[] = { 11 , 22 , 33 } ;
int* pi ;
pi = (int*)malloc( sizeof( int ) * 3 ) ;
if ( pi != NULL ) {
   for( int i = 0 ; i < 3 ; i++ )
      pi[ i ] = data[ i ] ;
   ////////////////////
   // piを使った処理
   ////////////////////
   free( pi ) ;
}
//
// 1件の構造体の保存
struct Person {
   char name[ 10 ] ;
   int  age ;
} ;
struct Person* pPsn ;
pPsn = (struct Person*)malloc( sizeof( struct Person ) ) ;
if ( pPsn != NULL ) {
   strcpy( pPsn->name , "t-saitoh" ) ;
   pPsn->age = 55 ;
   ////////////////////
   // pPsnを使った処理
   ////////////////////
   free( pPsn ) ;
}

(おまけ)C++の場合

malloc+freeでのプログラミングは、mallocの結果を型キャストしたりするので、間違ったコーディングの可能性がある。このため、C++ では、new 演算子, delete 演算子というものが導入されている。

// 同じ処理をC++で書いたら
// 文字列の保存
char  str[] = "ABCDE" ;
char* pc = new char[ strlen( str ) + 1 ] ;
strcpy( pc , str ) ;
// pcを使った処理
delete[] pc ;  // new型[]を使ったらdelete[]

// int配列の保存
int  data[] = { 11 , 22 , 33 } ;
int* pi ;
pi = new int[ 3 ] ;
for( int i = 0 ; i < 3 ; i++ )
   pi[ i ] = data[ i ] ;
// piを使った処理
delete[] pi ;

// 構造体の保存
struct Person {
   char name[ 10 ] ;
   int  age ;
} ;
Person* pPsn ;
pPsn = new Person ;
strcpy( pPsn->name , "t-saitoh" ) ;
pPsn->age = 55 ;
// pPsnを使った処理
delete pPsn ; // new型ならdelete

注意すべき点は、malloc+freeとの違いは、mallocがメモリ確保に失敗した時の処理の書き方。返り値のNULLをチェックする方法は、呼び出し側ですべてでNULLの場合を想定した書き方が必要になり、処理が煩雑となる。C++の new 演算子は、メモリ確保に失敗すると、例外 bad_alloc を投げてくるので、try-catch 文で処理を書く。(上記例はtry-catchは省略)

安全な1行1件のデータ入力

C言語では、scanf などの関数は、バッファオーバーフローなどの危険性があるため、以下のような処理を使うことが多い。fgets は、指定されたファイルから1行分のデータを読み込む。sscanf は、文字列のなかから、scanf() と同じようなフォーマット指定でデータを読み込む。

fgets は、これ以上の入力データが無い場合には、NULL を返す。
(Windowsであれば、キー入力でCtrl+Z を入力、macOSやLinuxであれば、Ctrl+Dを入力)

sscanf() は、読み込めたデータ件数を返す。

int main() {
   char buff[ 1024 ] ;
   for( int i = 0 ; i < 3 ; i++ ) {
      if ( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
         char name[ 1024 ] ;
         int  age ;
         if ( sscanf( buff , "%s%d" , name , &age ) == 2 ) {
            // 名前と年齢の2つのデータが正しく読み込めたとき
            ...
         }
      }
   }
   return 0 ;
}

様々なデータの覚え方

配列サイズ固定・名前が固定長

例えば、このデータ構造であれば、table1[] の場合、長い名前にある程度対応できるように nameの配列を100byteにしたりすると、データ件数が少ない場合には、メモリの無駄も多い。

そこで、実際に入力された存在するデータだけをポインタで覚える方法 table2[] という保存方法も考えられる。

// 固定長データのプログラム
#define SIZE 50

// 名前(固定長)と年齢の構造体
struct NameAge {
   char name[ 32 ] ;
   int  age ;
} ;
struct NameAge table1[ SIZE ] ;
int    size1 = 0 ;

void entry1( char s[] , int a ) {
   strcpy( table1[ size1 ].name , s ) ;
   table1[ size1 ].age = a ;
   size1++ ; 
}
// ポインタで覚える場合
struct NameAge* table2[ SIZE ] ;
int    size2 = 0 ;

void entry2( char s[] , int a ) {
   table2[size2] = (struct NameAge*)malloc( sizeof( struct NameAge ) ) ;
   if ( table2[size2] != NULL ) {  // なぜ != NULL のチェックを行うのか、説明せよ
      strcpy( table2[size2]->name , s ) ;
      table2[size2]->age = a ;
      size2++ ;
   }
}
// データ出力
void print_NA( struct NameAge* p ) {
   printf( "%s %d¥n" , p->name , p->age ) ;
}
int main() {
   // table1に保存
   entry1( "t-saitoh" , 55 ) ;
   entry1( "tomoko" ,   44 ) ;
   print_NA( &table1[0] ) ;
   print_NA( &table1[1] ) ;
   // table2に保存
   entry2( "t-saitoh" , 55 ) ;
   entry2( "tomoko" , 44 ) ;
   print_NA( _________________ ) ;  // table2の中身を表示せよ
   print_NA( _________________ ) ;
   return 0 ;
}

配列サイズ固定・名前が可変長

しかしながら、前回の授業で説明したように、際限なく長い名前があるのであれば、以下の様に名前は、ポインタで保存し、データを保存する時に strdup(…) を使って保存する方法もあるだろう。

// 名前が可変長のプログラム

// 名前(固定長)と年齢の構造体
struct NamePAge {
   char* name ;  // ポインタで保存
   int   age ;
} ;
struct NamePAge table3[ SIZE ] ;
int    size3 = 0 ;

void entry3( char s[] , int a ) {
   table3[ size3 ].name = strdup( s ) ;  // ★★★★
   table3[ size3 ].age = a ;
   size3++ ; 
}
// ポインタで覚える場合
struct NamePAge* table4[ SIZE ] ;
int    size4 = 0 ;

void entry4( char s[] , int a ) {
   table4[size4] = (struct NamePAge*)malloc( ____________________ ) ;
   if ( table4[size4] != NULL ) {            // ↑適切に穴埋めせよ
      table4[size4]->name = strdup( s ) ; // ★★★★
      _________________________________ ; // ←適切に穴埋めせよ
      size4++ ;
   }
}
// データ出力
void print_NPA( struct NameAge* p ) {
   printf( "%s %d¥n" , ____________ , ____________ ) ;
}                      // ↑適切に穴埋めせよ
int main() {
   // table3に保存
   entry3( "t-saitoh" , 55 ) ;
   entry3( "jyugemu jyugemu ..." ,   44 ) ;
   print_NPA( _________________ ) ;  // table3[] の中身を表示せよ。
   print_NPA( _________________ ) ; 
   // table4に保存
   entry4( "t-saitoh" , 55 ) ;
   entry4( "jyugemu jyugemu ..." , 44 ) ;
   print_NPA( table4[0] ) ;
   print_NPA( table4[1] ) ; 
   return 0 ;
}

データ件数が可変長ならば

前述のプログラムでは、データ件数全体は、SIZE という固定サイズを想定していた。しかしながら、データ件数自体も数十件かもしれないし、数万件かもしれないのなら、配列のサイズを可変長にする必要がある。

struct NamePAge* table5 ;
int    size5 = 0 ;

void entry5( char s[] , int a ) {
   strcpy( table5[ size5 ].name , s ) ;
   table5[ size5 ].age = a ;
   size5++ ; 
}

int main() {
   // table5に保存
   table5 = (struct NameAge*)malloc( sizeof( struct NameAge ) * 2 ) ;
   if ( table5 != NULL ) {
      entry5( "t-saitoh" , 55 ) ;
      entry5( "tomoko" ,   44 ) ;
   }
   return 0 ;
}

メモリの管理に十分気を付ける必要があるが、名前の長さも配列全体のサイズも可変長であれば、以下のようなイメージ図のデータを作る必要があるだろう。(JavaScriptやJavaといった言語ではデータのほとんどがこういったポインタで管理されている)

レポート課題

授業での malloc , free を使ったプログラミングを踏まえ、以下のレポートを作成せよ。

以下のデータのどれか1つについて、データを入力し、何らかの処理を行うこと。
課題は、原則として、(自分の出席番号%3)+1 についてチャレンジすること。

  1. 名前と電話番号
  2. 名前と生年月日
  3. 名前と身長・体重

このプログラムを作成するにあたり、以下のことを考慮しmallocを適切に使うこと。

名前は、長い名前の人が混ざっているかもしれない。
保存するデータ件数は、10件かもしれない1000件かもしれない。(データ件数は、処理の最初に入力すること。)

ただし、mallocの理解に自信がない場合は、名前もしくはデータ件数のどちらか一方は固定値でも良い。

レポートには、(a)プログラムリスト, (b)プログラムの説明, (c)正しく動いたことがわかる実行例, (d)考察 を記載すること。

考察には、自分のプログラムが正しく動かない事例はどういう状況でなぜ動かないのか…などを検討したり、プログラムで良くなった点はどういう所かを説明すること。

効率のよいメモリ使用と動的メモリ/スタック/malloc+free

次にメモリの利用効率の話について解説する。

配列宣言でサイズは定数

C言語では、配列宣言を行う時は、本来ならば、配列サイズに変数を使うことはできない。

最近のC(C99)では、実は下記のようなものは、裏で後述のalloca()を使って動いたりするので普通に書けるけど…。(^_^;

void foo( int size ) {
   int array[ size ] ;         // エラー
   for( int i = 0 ; i < size ; i++ )
      array[ i ] = i*i ;
}
int main() {
   foo( 3 ) ;
   foo( 4 ) ;
   return 0 ;
}

メモリ利用の効率

配列サイズには、定数式しか使えないので、1クラスの名前のデータを覚えるなら、以下のような宣言が一般的であろう。

#define MEMBER_SIZE 50
#define NAME_LENGTH 20
char name[ MEMBER_SIZE ][ NAME_LENGTH ] ;

しかしながら、クラスに寿限無とか銀魂の「ビチグソ丸」のような名前の人がいたら、20文字では足りない。(“t-saitoh”くんは配列サイズ9byte、”寿限無”くんは配列220byte といった使い方はできない) また、クラスの人数も、巨大大学の学生全員を覚えたいとい話であれば、 10000人分を用意する必要がある。 ただし、10000人の”寿限無”ありを考慮して、5Mbyte の配列を準備したのに、与えられたデータ量が100件で終わってしまうなら、その際のメモリの利用効率は極めて低い。

このため、最も簡単な方法は、以下のように巨大な文字配列に先頭から名前を入れていき、 文字ポインタ配列に、各名前の先頭の場所を入れる方式であれば、 途中に寿限無がいたとしても、問題はない。

char array[2000] = "ayuka¥0mitsuki¥0t-saitoh¥0tomoko¥0....." ;
char *name[ 50 ] = {
   array+0 , array+6 , array+14 , array+23 , ...
} ;

この方式であれば、2000byte + 4byte(32bitポインタ)×50 のメモリがあれば、 無駄なメモリ空間も必要最低限とすることができる。

参考:
寿限無(文字数:全角103文字)

さる御方、ビチクソ丸(文字数:全角210文字)

引用Wikipedia(2020年5月リンク切れてる…)

大きな配列を少しづつ貸し出す処理

// 巨大な配列
char str[ 10000 ] ;
// 使用領域の末尾(初期値は巨大配列の先頭)
char* sp = str ;
// 文字列を保存する関数
char* entry( char* s ) {
   char* ret = sp ;
   strcpy( sp , s ) ;
   sp += strlen( s ) + 1 ;
   return ret ;
}
int main() {
   char* names[ 10 ] ;
   names[ 0 ] = entry( "saitoh" ) ;
   names[ 1 ] = entry( "jugemu-jugemu-gokono-surikire..." ) ;
   return 0 ;
}
// str[] s a i t o h ¥0 j u g e m u - .... ¥0
//       ↑             ↑
//     names[0]        names[1]

このプログラムでは、貸し出す度に、sp のポインタを後ろに移動していく。

スタック

この貸し出す度に、末尾の場所をずらす方式にスタックがある。

int stack[ 100 ] ;
int* sp = stack ;
void push( int x ) {
   *sp = x ;    // 1行で書くなら
   sp++ ;       // *sp++ = x ;
}
int pop() {
   sp-- ;
   return *sp ; // return *(--sp) ;
}
int main() {
   push( 1 ) ;
   push( 2 ) ;
   push( 3 ) ;
   printf( "%d¥n" , pop() ) ;
   printf( "%d¥n" , pop() ) ;
   printf( "%d¥n" , pop() ) ;
   return 0 ;
}


スタックは、最後に保存したデータを最初に取り出せる(Last In First Out)から、LIFO とも呼ばれる。
このデータ管理方法は、最後に呼び出した関数が最初に終了することから、関数の戻り番地の保存や、最後に確保した局所変数が最初に不要となることから、局所変数の管理に利用されている。

alloca() 関数

局所変数と同じスタック上に、一時的にデータを保存する配列を作り、関数が終わると不要になる場合には、alloca() 関数が便利である。alloca の引数には、必要なメモリの byte 数を指定する。100個の整数データを保存するのであれば、int が 32bit の 4byte であれば 400byte を指定する。ただし、int 型は16bitコンピュータなら2byteかもしれないし、64bitコンピュータなら、8byte かもしれないので、sizeof() 演算子を使い、100 * sizeof( int ) と書くべきである。

#include <alloca.h>
void foo( int size ) {
   int* p ;
   // 
   p = (int*)alloca( sizeof( int ) * size ) ;
   for( int i = 0 ; i < size ; i++ )
      p[ i ] = i*i ;
}
int main() {
   foo( 3 ) ;
   foo( 4 ) ;
   return 0 ;
}

alloca() は、指定された byte 数のデータ領域の先頭ポインタを返すが、その領域を 文字を保存するために使うか、int を保存するために使うかは alloca() では解らない。alloca() の返り値は、使う用途に応じて型キャストが必要である。文字を保存するなら、(char*)alloca(…) 、 intを保存するなら (int*)alloca(…) のように使う。

ただし、関数内で alloca で確保したメモリは、その関数が終了すると、その領域は使えなくなる。このため、最後に alloca で確保したメモリが、最初に不要となる…ような使い方でしか使えない。

malloc()とfree()

malloc() は、動的(ヒープ領域)にメモリを確保する命令で、データを保存したい時に malloc() を実行し、不要になった時に free() を実行する。

malloc() では、alloca() と同じように、格納したいデータの byte 数を指定する。また、malloc() は、確保したメモリ領域の先頭を返すが、ヒープメモリが残っていない場合 NULL ポインタを返す。処理が終わってデータ領域をもう使わなくなったら、free() で解放する必要がある。

基本的には、確保したメモリ領域を使い終わった後 free() を実行しないと、再利用できないメモリ領域が残ってしまう。こういう処理を繰り返すと、次第にメモリを食いつぶし、仮想メモリ機能によりハードディスクの読み書きで性能が低下したり、最終的にOSが正しく動けなくなる可能性もある。こういった free() 忘れはメモリーリークと呼ばれ、malloc(),free()に慣れない初心者プログラマーによく見られる。

ヒープメモリは、プロセスの起動と共に確保され、プログラムの終了と同時にOSに返却される。このため、malloc()と処理のあとすぐにプロセスが終了するようなプログラムであれば、free() を忘れても問題はない。授業では、メモリーリークによる重大な問題を理解してもらうため、原則 free() は明記する。

文字列を保存する場合

#include <stdlib.h>
char* names[ 10 ] ;
char  buff[ 1000 ] ;

// 名前を10件読み込む
void inputs() {
   for( int i = 0 ; i < 10 ; i++ ) {
      if ( fgets( buff ,
                  sizeof( buff ) ,
                  stdin ) != NULL ) {
         names[ i ]
            = (char*)malloc( strlen(buff)+1 ) ;
         if ( names[ i ] != NULL )
            strcpy( names[ i ] , buff ) ;
      }
   }
}
// 名前を出力する
void prints() {
   for( int i = 0 ; i < 10 ; i++ )
      printf( "%s" , names[ i ] ) ;
}
int main() {
   // 文字列の入力&出力
   inputs() ;
   prints() ;
   // 使い終わったら、free() で解放
   for( int i = 0 ; i < 10 ; i++ )
      free( names[ i ] ) ;
   return 0 ;
}

文字列を保存する場合には、上記の names[i] への代入のような malloc() と strcpy() を使うことが多い。
このための専用の関数として、strdup() がある。基本的には、以下のような機能である。

char* strdup( char* s ) {
   char* p ;
   if ( (p = (char*)malloc( strlen(s)+1 )) != NULL )
      strcpy( p , s ) ;
   return p ;
}

また、入力した文字列をポインタで保存する場合、以下のようなプログラムを書いてしまいがちであるが、図に示すような状態になることから、別領域にコピーする必要がある。

char  buff[ 1000 ] ;
char* name[10] ;
for( int i = 0 ; i < 10 ; i++ ) {
   if ( fgets( buff , sizeof(buff) , stdin ) != NULL )
      name = buff ;
}

配列に保存する場合

任意サイズの配列を作りたい場合には、malloc() で一括してデータの領域を作成し、その先頭アドレスを用いて配列として扱う。

#include <stdlib.h>
void main() {
   int size ;
   int* array ;
   // 処理するデータ件数を入力
   scanf( "%d" , &size ) ;

   // 整数配列を作る
   if ( (array = (int*)malloc( sizeof(int) * size )) != NULL ) {
      int i ;
      for( i = 0 ; i < size ; i++ )
         array[i] = i*i ; // あんまり意味がないけど
      for( i = 0 ; i < size ; i++ )
         printf( "%d¥n" , array[i] ) ;

      // mallocしたら必ずfree
      free( array ) ;
   }
}

構造体の配列

同じように、任意サイズの構造体の配列を作りたいのであれば、配列サイズに「sizeof( struct Complex ) * データ件数」を指定すればいい。

#include <stdlib.h>
struct Complex {
   double re , im ;
} ;

// 指定した場所にComplexを読み込む。
int input_Complex( struct Complex* p ) {
   return scanf( "%f %f" ,
                 &(p->re) , &(p->re) ) == 2 ;
}

// 指定したComplexを出力
void print_Complex( struct Complex* p ) {
   printf( "%f+j%f¥n" , p->re , p->im ) ;
}
void main() {
   int size ;
   struct Complex* array ;
   // 処理する件数を入力
   scanf( "%d" , &size ) ;
   // 配列を確保して、データの入力&出力
   if ( (array = (struct Complex*)malloc(
                    sizeof(struct Complex) * size )) != NULL ) {
      int i ;
      for( i = 0 ; i < size ; i++ )
         if ( !input_Complex( &array[i] ) )
            break ;
      for( i = 0 ; i < size ; i++ )
         print_Complex( &array[i] ) ;

      // mallocしたら必ずfree
      free( array ) ;
   }
}

ソートのアルゴリズムの分岐点

ソートアルゴリズムの処理時間で、選択法よりクイックソートが有利になる分岐点を求める問題で、

の結果が、N=53.1 になる…との説明が判らないとの質問。# 53.017 が正しいとの結果だったが。

あてずっぽうな計算方法

Excelで実際に計算すればいい。B列2行目に =A2/LOG(A2) を入れて、A列に2,3,…. と数字を入れて変化させて、30.74 に近い場所を探すと53となった。# 手抜きだな!

ニュートン法で解く

方程式で解けない場合は、ニュートン法 f(x)=0 の式でxの値を求める…のが定番の方法。

この場合は f(x) = x/log(x) – 1000/25/log(20) として、ニュートン法の漸化式を解けばいい。
ちょいとプログラムを書いてみた。

((( nlogn.cxx )))
#include <stdio.h>
#include <math.h>

// N/logN = 1000/25/log20 をニュートン法で解く                                                                          
//                                                                                                                      
//      f(x) = x/log(x) - 1000/25/log20                                                                                 
//      f'(x) = log(10) (log(x) - 1) / log(x)^2                                                                         
//                                                                                                                      
//      x <= x + f(x) / f'(x)                                                                                           

//      要注意 C言語のlog関数                                                                                           
//              log(x) = 自然対数を底とするlog                                                                          
//              log10(x) = 10を底とするlog                                                                              

double f( double x ) {
  return x / log10(x) - 1000.0/25.0/log10(20.0) ;
}

double df( double x ) {
  return log(10.0) * ( log(x) - 1.0 ) / pow( log(x) , 2.0 ) ;
}

int main() {
  double x = 5.0 ;

  for( int i = 0 ; i < 5 ; i++ ) {
    double f1 = f(x) ;
    double f2 = df(x) ;
    x = x - f1 / f2 ;
    printf( "%d %lf\n" , i , x ) ;
  }
  return 0 ;
}

((( 実行結果 )))
$ g++ nlogn.cxx
$ ./a.out
0 48.547041
1 52.983539
2 53.016894
3 53.016896
4 53.016896

うーむ、Webの資料では、53 に近い値だし、あてずっぽうで 53.1 となる…って書いたけど、本当は 53.017 だな。m(_ _)m

数年前までの電子情報の学生さんなら、TI の関数電卓持ってたから「授業で解いて…」というと、結果をすぐに答えてくれる優秀な人がクラスに1人くらい必ずいたけど、最近は BYOD でパソコンを使うので TI の関数電卓持ってないから、解いてくれるヤツいないのよね。

ソート処理の見積もりとポインタ処理

前回の授業では、再帰処理やソートアルゴリズムの処理時間の見積もりについて説明を行った。

ソート処理の見積もり

この際の練習問題の1つめは、「再帰方程式の理解度確認の回答」にて解説を示す。

最後の練習問題はここで説明を行う。

選択法とクイックソートの処理時間の比較

例として、データ数N=20件で、選択法なら10msec、クイックソートで20msecかかったとする。

これより、選択法の処理時間を、クイックソートの処理時間を、とすると、





よって、

処理時間が逆転するときのデータ件数は、2つのグラフの交点を求めることになるので、

より、以下の式を解いた答えとなる。これは通常の方程式では解けないが電卓で求めると、N=53.1 ほどかな。(2020/05/26) 真面目に解いたら N=53.017 だった。

実際にも、クイックソートを再帰呼び出しだけでプログラムを書くと、データ件数が少ない場合は選択法などのアルゴリズムの方が処理時間が早い。このため、C言語などの組み込み関数の qsort() などは、データ件数が20とか30とか一定数を下回ったら、再帰を行わずに選択法でソートを行うのが一般的である。

ポインタ処理

ここからは、次のメモリの消費を考慮したプログラムの説明を行うが、ポインタの処理に慣れない人が多いので、ポインタを使ったプログラミングについて説明を行う。

値渡し(call by value)

// 値渡しのプログラム
void foo( int x ) {  // x は局所変数(仮引数は呼出時に
                     // 対応する実引数で初期化される。
   x++ ;
   printf( "%d¥n" , x ) ;
}
void main() {
   int a = 123 ;
   foo( a ) ;  // 124
               // 処理後も main::a は 123 のまま。
   foo( a ) ;  // 124
}

このプログラムでは、aの値は変化せずに、124,124 が表示される。

言い方を変えるなら、呼び出し側main() では、関数の foo() の処理の影響を受けない。このように、関数には仮引数の値を渡すことを、値渡し(call by value)と言う。

でも、プログラムによっては、124,125 と変化して欲しい場合もある。
どのように記述すべきだろうか?

// 大域変数を使う場合
int x ;
void foo() {
   x++ ;
   printf( "%d¥n" , x ) ;
}
void main() {
   x = 123 ;
   foo() ;  // 124
   foo() ;  // 125
}

しかし、このプログラムは大域変数を使うために、間違いを引き起こしやすい。

// 大域変数が原因で予想外の挙動をしめす簡単な例
int i ;
void foo() {
   for( i = 0 ; i < 2 ; i++ )
      printf( "A" ) ;
}
void main() {
   for( i = 0 ; i < 3 ; i++ )  // このプログラムでは、AA AA AA と
      foo() ;                   // 表示されない。
}

ポインタ渡し(call by pointer)

C言語で引数を通して、呼び出し側の値を変化して欲しい場合は、(引数を経由して関数の副作用を受け取るには)、変更して欲しい変数のアドレスを渡し、関数側では、ポインタ変数を使って受け取った変数のアドレスの示す場所の値を操作する。このような値の受け渡し方法は、ポインタ渡し(call by pointer)と呼ぶ。

// ポインタ渡しのプログラム
void foo( int* p ) {  // p はポインタ
   (*p)++ ;
   printf( "%d¥n" , *p ) ;
}
void main() {
   int a = 123 ;
   foo( &a ) ;  // 124
                // 処理後 main::a は 124 に増えている。
   foo( &a ) ;  // 124
}               // さらに125と増える。

C言語では、関数から結果をもらうには、通常は関数の返り値を使う。しかし、返り値は1つの値しか受け取ることができないので、上記のようにポインタを使って、呼び出し側は:結果を入れてもらう場所を伝え、関数側は:指定されたアドレスに結果を書む。

ポインタの加算と配列アドレス

ポインタに整数値を加えることは、アクセスする場所が、指定された分だけ後ろにずれることを意味する。

// ポインタ加算の例
int a[ 5 ] = { 11 , 22 , 33 , 44 , 55 } ;

void main() {
   int* p ;
                               //            p∇
   p = &a[2] ;                 // a[] : 11,22,33,44,55
                               //       -2    +0 +1
   printf( "%d¥n" , *p ) ;     // 33  p[0]
   printf( "%d¥n" , *(p+1) ) ; // 44  p[1]
   printf( "%d¥n" , *(p-2) ) ; // 11  p[-2]

   p = a ;                  //      p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p++ ;                    //       → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p += 2 ;                 //           → → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
}

ここで、注意すべき点は、ポインタの加算した場所の参照と、配列の参照は同じ意味となる。

*(p + 整数式)p[ 整数式 ] は同じ意味

特に配列 a[] の a だけを記述すると、配列の先頭を意味することに注意。

構造体とポインタ

構造体を関数に渡して処理を行う例を示す。

struct Person {
   char name[ 10 ] ;
   int  age ;
} ;
struct Person table[3] = {
   { "t-saitoh" , 55 } ,
   { "tomoko" ,   44 } ,
   { "mitsuki" ,  19 } ,
} ;

void print_Person( struct Person* p ) {
   printf( "%s %d\n" ,
           (*p).name , // * と . では . の方が優先順位が高い
                       // p->name と簡単に書ける。
           p->age ) ;  // (*p).age の簡単な書き方
}

void main() {
   for( int i = 0 ; i < 3 ; i++ ) {
      print_Person( &(table[i]) ) ;
   // print_Person( table + i ) ; でも良い
   }
}

構造体へのポインタの中の要素を参照する時には、アロー演算子 -> を使う。

練習問題(2018年度中間試験問題より)

再帰方程式の理解度確認の解答

再帰呼び出しと再起方程式の資料の中の「理解度確認」の解答

解答

pyraをループで

// pyra() をループで書いたら。
int pyra( int x ) {
   int ans = 0 ;
   for( int i = 1 ; i <= x ; i++ )
      ans += i * i ;
   return ans ;
}

2分探索法を再帰で

// 2分探索を再帰で書いたら
int find( int array[] , int L , int R , int key ) {
   if ( R == L ) {
      return 0 ; // みつからない
   } else {
      int M = (L + R) / 2 ;
      if ( array[ M ] == key )     // みつかった
         return 1 ;           
      else if ( array[ M ] > key ) // 左側にある
         return find( array , L , M , key ) ;
      else                         // 右側にある
         return find( array , M+1 , R , key ) ;
   }
}

このプログラムでは、検索する範囲がLとRで与えられ、この範囲の幅が再帰が呼び出される毎に半分になっていく。

であれば、処理時間は対象となるデータ件数 N = R – L によって、処理時間は変化するので、T(N) で考えると、(ただし途中でデータが見つからない最悪の場合で式を示す)

データ件数0件では、if,R==L,return 0の処理を行う。このため、以下の様な再帰方程式の細小時での処理時間は、

  … ①

となる。(find(件数=1)の次は必ずfind(件数=0)が実行されるのででも良い。)

Nは整数という条件をつけないと、N=1/2, 1/4, 1/8…で止まらない…と勘違いする人もいるし、データ件数が1件になったら再帰がとまると考えた方が分かりやすいので、の方が都合がいいかな…

データが1以上の時で、対象データが L..Mの範囲にあるのなら、再帰の時に対象データ件数は半分になるから、if,R==L,else,if,array[M]==key,else-if,array[M]>keyの処理時間(Tb) と find(…,L,M,…) の処理時間を要するので、次の式となる。

  … ②

一方、(M+1)..Rの範囲にあるのなら同様に、if,R==L,else,if,array[M]==key,else-if,array[M]>key,elseの処理時間(Tc)と、find(…,M+1,R,…) の処理時間なので、

  … ③

となる。ただ、処理時間の見積もりでは厳密な分析が求められないので、(N-1)/2 だと一般式が複雑になるので、N/2 で考える。さらにTbTcの処理時間は少しの時間の違いだし、確率1/2でTbTcのどちらかを実行するので、その平均時間をTbで表すことにすれば、③は②とほぼ同じと見なすことができるので、再帰方程式は①と②で良い。

fib()の再帰方程式

再帰のフィボナッチ数 fib() の処理時間に相応しい再帰方程式は、xの値(Nとする)が2以下の時は、return を実行するだけ。3以上の時は、if,else,return,+ の処理時間と、fib(x-2)の処理時間、fib(x-1)の処理時間を要する。

よって、再帰方程式は、以下の式となる。

これを代入法で一般式を求めると、T(N)=fib(N-2)×Tb+fib(N+1)×Tかな?よって、再帰のfib()の処理時間は、フィボナッチ数に比例する。ちなみに、フィボナッチ数ピネの公式で一般項が示されているので、処理時間のオーダーは、次式となる。

再帰呼び出しと再帰方程式

再帰関数と再帰方程式

再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。プログラムには問題が最小となった時の処理があることで、再帰の繰り返しが止まる。

// 階乗 (末尾再帰)
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の処理(Tb)に加え、x-1の値で再帰を実行する処理時間T(N-1)がかかる。 このことから、 で表せる。

} 再帰方程式

このような再帰を使って表した式は再帰方程式と呼ばれる。これを代入によって解けば、一般式  が得られる。

T(1)=Ta
T(2)=Tb+T(1)=Tb+Ta
T(3)=Tb+T(2)=2×Tb+Ta
:
T(N)=Tb+T(N-1)=Tb + (N-2)×Tb+Ta

一般的に、再帰呼び出しプログラムは(考え方に慣れれば)分かりやすくプログラムが書けるが、プログラムを実行する時には、局所変数や関数の戻り先を覚える必要があり、深い再帰ではメモリ使用量が多くなる
ただし、fact() や pyra() のような関数は、プログラムの末端で再帰が行われている。(fib()は、再帰の一方が末尾ではない)
このような再帰は、末尾再帰と呼ばれ、関数呼び出しの return を、再帰処理の先頭への goto 文に書き換えるといった最適化が可能である。言い換えるならば、末尾再帰の処理は繰り返し処理に書き換えが可能である。このため、末尾再帰の処理をループにすれば再帰のメモリ使用量の問題を克服できる。

再帰を含む一般的なプログラム例

ここまでの再帰方程式は、再帰の度にNの値が1減るものばかりであった。もう少し一般的な再帰呼び出しのプログラムを、再帰方程式で処理時間を分析してみよう。
以下のプログラムを実行したらどんな値になるであろうか?それを踏まえ、処理時間はどのように表現できるであろうか?

int array[ 8 ] = {
  3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
} ;

int sum( int a[] , int L , int R ) { // 非末尾再帰
    if ( R - L == 1 ) {
        return a[ L ] ;
    } else {
        int M = (L + R) / 2 ;
        return sum( a , L , M ) + sum( a , M , R ) ;
    }
}
int main() {
    printf( "%d¥n" , sum( array , 0 , 8 ) ) ;
    return 0 ;
}

このプログラムでは、配列の合計を計算しているが、引数の L,R は、合計範囲の 左端・右端を表している。そして、再帰のたびに2つに分割して解いている。

このような、処理を分割し、分割したそれぞれを再帰で計算し、その処理結果を組み合わせて最終的な結果を求めるような処理方法を、分割統治法と呼ぶ。

このプログラムでは、対象となるデータ件数(R-L)をNとおいた場合、実行される命令からsum()の処理時間Ts(N)は次の再帰方程式で表せる。

   ← Tβ + (L〜M)の処理時間 + (M〜R)の処理時間

これを代入の繰り返しで解いていくと、

ということで、このプログラムの処理時間は、 で表せる。

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

ハノイの塔


ハノイの塔は、3本の塔にN枚のディスクを積み、(1)1回の移動ではディスクを1枚しか動かせない、(2)ディスクの上により大きいディスクを積まない…という条件で、山積みのディスクを目的の山に移動させるパズル。

一般解の予想

ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 以下の一般式で表せることが予想できる。

 … ①

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

再帰方程式

上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、

 … ②
 … ③

ということが言える。(これがハノイの塔の移動回数の再帰方程式)
ディスクが枚の時、予想が正しいのは明らか①,②。
ディスクが 枚で、予想が正しいと仮定すると、 枚では、

 … ③より
 … ①を代入

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

理解度確認

  • 前再帰の「ピラミッドの体積」pyra() を、ループにより計算するプログラムを記述せよ。
  • 前講義での2分探索法のプログラムを、再帰によって記述せよ。(以下のプログラムを参考に)。また、このプログラムの処理時間にふさわしい再帰方程式を示せ。
  • 再帰のフィボナッチ関数 fib() の処理時間にふさわしい再帰方程式を示せ。
int a[ 10 ] = {
   7 , 12 , 22 , 34 , 41 , 56 , 62 , 78 , 81 , 98
} ;
int find( int array[] , int L , int R , int key ) { // 末尾再帰
   // 目的のデータが見つかったら 1,見つからなかったら 0 を返す。
   if ( __________ ) {
      return ____ ; // 見つからなかった
   } else {
      int M = _________ ;
      if ( array[ M ] == key )
         return ____ ;
      else if ( array[ M ] > key )
         return find( array , ___ , ___ , key ) ;
      else
         return find( _____ , ___ , ___ , ___ ) ;
   }
}
int main() {
   if ( find( a , 0 , 10 , 56 ) )
      printf( "みつけた¥n" ) ;
}

再帰を使ったソートアルゴリズム

データを並び替える有名なアルゴリズムの処理時間のオーダは、以下の様になる。

この中で、高速なソートアルゴリズムは、クイックソート(最速のアルゴリズム)とマージソート(オーダでは同程度だが若干効率が悪い)であるが、ここでは、再帰方程式で処理時間をイメージしやすい、マージソートにて説明を行う。

マージソートの分析

マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。

このことから、再帰方程式は、以下のようになる。

  • Tm(1)=Ta

この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが となる。






よって、

選択法とクイックソートの処理時間の比較

データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。

  1. データ件数 = 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
  2. データ件数何件以上なら、クイックソートの方が高速になるか答えよ。

設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓が必要。