今日は、前回の演習時間も不足だと思われるので、前半に座学・後半演習とした。

意思決定木

雑誌の占いや性格判断みたいなページには、質問に対して"yes","no"の回答をしてもらって、 最終的にあなたの性格は！みたいなのがよく書かれている。こういうようなものは、

　　　　　　　｜
　　　　　　勉強好き？　　
　　　　　／　　　　　＼
もっと勉強？　　　　　部活好き？　
　／　＼　　　　　　　／　＼
大学　技術者　アスリート　心配！

意思決定木と呼ばれる。このデータ構造では、ノードに質問事項が書かれ、 木の末端のノードには、最終的な答えが記載される。 これをプログラムで表すならば、

struct DTree {
char *mess ;
struct DTree* yes ;
struct DTree* no ;
} ;
struct DTree* dtcons( char* s ,
struct DTree* y ,
struct DTree* n )
{
struct DTree* ret ;
ret = (struct DTree*)malloc( sizeof( struct DTree ) ) ;
if ( ret != NULL ) {
ret->mess = s ;
ret->yes  = y ;
ret->no   = n ;
}
return ret ;
}
struct DTree* top =
dtcons( "勉強好き?" ,
dtcons( "もっと勉強?" ,
dtcons( "大学" , NULL , NULL ) ,
dtcons( "技術者" , NULL , NULL ) ) ,
dtcons( "部活好き?" ,
dtcons( "アスリート" , NULL , NULL ) ,
dtcons( "心配..." , NULL , NULL ) ) ) ;
void main() {
char buff[ 100 ] ;
struct DTree* p = top ;
while( p->yes != NULL || p->no != NULL ) {
printf( "%s" , p->mess ) ;
scanf( "%s" , buff ) ;
if ( strcmp( buff , "yes" ) == 0 )
p = p->yes ;
else
p = p->no ;
}
printf( "%s" , p->mess ) ;
}