ホーム » スタッフ » 斉藤徹 (ページ 109)

斉藤徹」カテゴリーアーカイブ

2025年7月
 12345
6789101112
13141516171819
20212223242526
2728293031  

検索・リンク

宿直で、寮イベント焼き芋づくり

1504231945_640x640.JPG

再帰関数の処理と再帰方程式

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

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

前回授業の最後に検討しておくようにと伝えた、 の処理時間のオーダについて、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の値で再帰の処理時間がかかる。 このことから、 で表せる。 これを代入によって解けば、 で表せる。 こういった式は、再帰方程式と呼ばれ、一般式を求めることとなる。

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

ハノイの塔

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

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


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



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

C言語の構造体からオブジェクト指向に

前回の構造体の説明から、ポインタ渡しの説明を行った後、同様のプログラムをC++で書き換えることで、classやメソッドなどの説明を行う。

構造体でオブジェクト指向もどき

例えば、名前と電話番号の構造体で処理を記述する場合、 以下の様な記載を行うことで、データ設計者とデータ実装者で分けて 仕事ができることを説明。

struct Person {
   char name[10] ;
   int  phone ;
} ;
void readPerson( struct Person* p ) {
   // ポインタの参照で表記
   scanf("%s%d" ,
   (*p).name , &(*p).phone ) ;
}
void printPerson( struct Person* p ) {
   // アロー演算子で表記
   printf( "%s %d¥n" ,
   p->name , p->phone ) ;
}
void main() {
   struct Person table[ 10 ] ;
   for( int i = 0 ; i < 10 ; i++ ) {
      readPerson( &table[i] ) ;
      printPerson( &table[i] ) ;
   }
}

このプログラムの書き方では、mainの中を読むだけもで、 データ入力とデータ出力を行うことはある程度理解できる。 この時、データ構造の中身を知らなくてもプログラムが理解でき、 データ実装者はプログラムを記述できる。これをデータ構造の隠蔽化という。 一方、readPerson()や、printPerson()という関数の中身についても、 入力・出力の方法をどうするのか知らなくても、 関数名から動作は推測できプログラムも書ける。 これを手続きの隠蔽化という。

C++のクラスで表現

上記のプログラムをそのままC++に書き直すと以下のようになる。

class Person {
private: // クラス外からアクセスできない部分
   char name[10] ; // メンバーの宣言
   int  phone ;
public: // クラス外から使える部分
   void read() { // メソッドの宣言
      // pのように対象のオブジェクトを明記する必要はない。
      scanf( "%s%d" , name , &phone ) ;
   }
   void print() {
      printf( "%s %d¥n" , name , phone ) ;
   }
} ;
void main() {
   Person table[ 10 ] ;
   for( int i = 0 ; i < 10 ; i++ ) {
      table[i].read() ;  // メソッドの呼び出し
      table[i].print() ;  // オブジェクト.メソッド()
   }
   // 文法エラーの例
   printf( "%d¥n" , table[0].phone ) ;
   // phoneはprivateなので参照できない。
}

用語の解説:C++のプログラムでは、データ構造とデータの処理を、並行しながら記述する。 データ構造に対する処理は、メソッド(method)と呼ばれる。 データ構造とメソッドを同時に記載したものは、クラス(class)と呼ぶ。 そのclassに対し、具体的な値や記憶域が割り当てられたものをオブジェクト(object)と呼ぶ。

コンストラクタとデストラクタ

プログラムを記述する場合、そのデータ構造を使うにあたり、 初期値が代入を忘れその値を参照すると、予想外の動きの原因となってしまうことが多い。

そこでオブジェクト指向では、データ構造の初期化手続き(同様に処理が終わった後の事後手続き)を 明確に記載するための初期化のコンストラクタ(と事後処理はデストラクタ)の文法がある。

class Person {
private:
   char name[10] ;
   int  phone ;
public:
   Person( char s[] , int tel ) { // コンストラクタ
      strcpy( name , s ) ;
      phone = tel ;
   }
   void print() {
      printf( "%s %d¥n" , name , phone ) ;
   }
} ;
void main() {
   // オブジェクト宣言とコンストラクタでの初期化
   Person saitoh( "tsaitoh" , 272925 ) ;
   saitoh.print() ;
}

コンストラクタを宣言する場合には、返り値無しのクラス名を関数名として記述する。 デストラクタを宣言する場合には、先頭に「~」をつけたクラス名で無引数で記述する。 簡単な例として、文字列をヒープ領域に保存する処理を示す。

// デストラクタが便利な例
class String {
private:
   char* str ;
public:
   // コンストラクタ
   String( char*s ) {
      // ヒープメモリ上に文字列を確保
      str = (char*)malloc( strlen( s ) + 1 ) ;
      strcpy( str , s ) ;
   }
   // デストラクタ
   ~String() {
      free( str ) ; // freeしないとメモリーリークになる。
   }
   void print() {
      printf( "%s" , str ) ;
   }
} ;
void main() {
   String s( "abcdefg" ) ;
   s.print() ;
}  // mainを抜ける段階でsは不要となる。
// ここで自動的にデストラクタ呼び出し~String()をしてくれる。

関数の値渡しと、整数型の数値の範囲

丁度、講義の前に別授業の課題に取り組んでいる学生を見ていたら、 次週に説明を行おうと思っていたN進数、小数点を含む2進数であった。 丁度、「計算機構成論」の補数、「数値計算」の小数点を含む2進数の講義で、 いつもになく、内容と説明時期が重複している…(^_^;

関数の値渡し

関数との引数の値渡しについて解説。 C言語では基本の値渡しメカニズムしかない。 引数で副作用(side effect)を返したい場合は、その代用としてポインタ渡しを利用する。 また、配列が引数の場合、値渡しのためのコピーを最小限とするため、 配列先頭アドレスによるポインタ渡しで行われることを説明する。

// 値渡し
void foo( int x ) {
   x++ ;
   printf( "%d¥n" , x ) ;
}
void main() {
   int a = 123 ;

   foo( a ) ; // 124
   foo( a ) ; // 124
}
// ポインタ渡し
void foo( int* px ) {
   (*px)++ ;
   printf( "%d¥n" , *px ) ;
}
void main() {
   int a = 123 ;

   foo( &a ) ; // 124
   foo( &a ) ; // 125
}
// 参照渡し(C++の新しい文法で紹介のみ)
void foo( int &x ) {
   x++ ;
   printf( "%d¥n" , x ) ;
}
void main() {
   int a = 123 ;

   foo( a ) ; // 124
   foo( a ) ; // 125
}
// 配列でのポインタ渡し
void foo( int x[] ) {
   x[0]++ ;
   printf( "%d¥n" , x[0] ) ;
}
void main() {
   int a[1] = { 123 } ;

   foo( a ) ; // 124
   foo( a ) ; // 125
}

整数型の数値範囲

整数型などの数値範囲について説明を行うために、2の補数表現を復習したあと、 数値の範囲について説明する。

type          | range     | unsigned |    signed
--------------+-----------+----------+---------------
char          | 8bit      | 0..255   |   -128..127
short int     | 16bit     | 0..65535 | -32768..32767
int           | 32bit     | 0..2^32-1|  -2^31..2^31-1
long int      | ?32bit?   |          |
long long int | gcc 64bit | 0..2^64-1|  -2^63..2^63-1

数値範囲の大まかな計算のための2つの方法として、 や、 10進数での桁数の概算のために、 より、 といった計算を行う方法について説明。

次週は、16bitコンピュータで int が簡単に桁あふれする問題や、 2038年問題や2004年問題などを解説する予定。

授業アンケートの結果

授業アンケートが、年度末に演習室が使えなかったことから、 時期遅れではあるけれど、結果がでてきた。

1504161201_545x404.png

プログラミング応用は、昨年度の81.7からは、若干落ちて76.3ポイント。 Q4の板書について、「やや悪い」の評価が多いのと、 Q15の理解把握について、「良い」の評価が少なめなのが、効いているか…。 板書については、文字を大きくとか、記載場所の流れを改めて意識してみよう。


1504161201_540x402.png

情報構造論は、79.8ポイント。あとちょっとで、80点(学生さんなら優)だったのにぃ。 昨年度は、80.9ポイントなので、連続ポイントダウン。 Q4板書のポイントが、これまた低めなので、改めて意識した書き方の必要があるかな。

講義録記事にヒント表示を導入

講義録をBLOGの形で、ページに掲載するのを、この10年ほど続けているけど、 準備が不十分な場合には、授業で過去の記事をプロジェクタで表示しながら説明… という場合もある。

しかし、過去の記事で丁寧に書いてありすぎると、問題の答えまでモロに記事に 書いておくと、記事を読んでいる学生さんが、何も考えないまま…に なってしまう場合が多い。そこで、BLOGのJavaScriptに、 クリック表示/非表示を切り替えられるようなものを埋め込んおくようにした。

// BLOGパーツのJavaScriptに以下を追加
function hint_switch( hs_this ) {
   // 指定ブロック内の末尾ブロックをinline表示/none非表示をスイッチ
   if ( hs_this.lastElementChild.style.display == "none" ) {
      hs_this.lastElementChild.style.display = "inline" ;
   } else {
      hs_this.lastElementChild.style.display = "none" ;
   }
}

そして、一時的に非表示にしたい部分には、以下のHTMLを埋め込む。

<div onclick="hint_switch(this)">
  <p>
    // 常に表示しておく部分(ここをクリック)
  </p>
  <div style="display: none">
    // 一時的に、非表示にしておきたい部分
  </div>
</div>

変数の寿命とスコープ

先週のC言語の制御構文のシメとして、switch-case文の説明をしてから、 変数の寿命とスコープの説明を行った。

switch-case文の説明では、以下の例は期待通りの動きをしない…といった例も交えて説明。 ただし、double誤差問題や文字列のポインタ関連なので、以後の授業で改めて説明が必要だろう。

// double誤差問題
double x ;
for( x = 0.0 ; x <= 1.0 ; x += 0.1 )
   switch( x ) {
   case 0.3 : printf( "A" ) ; // 0.299999...と0.3は違う値になるかも
              break ;
   }

// 文字列の比較の問題
char str[ 10 ] ;
scanf( "%s" , str ) ;
switch( str ) { // strの先頭番地と"yes","no"の先頭番地の比較
case "yes" : printf( "はい" ) ; break ;
case "no"  : printf( "いいえ" ) ; break ;
}

変数の寿命とスコープ

最初に、以下の様なプログラムが期待通りに動かない説明をして、 大域変数を共用することの問題を話す。

int i ; // 大域変数(global variable)
void foo() { // Aを2回表示
   for( i = 0 ; i < 2 ; i++ )
      printf( "A" ) ;
}
void main() {
   // foo(Aを2回表示)を2回呼び出すつもり
   for( i = 0 ; i < 2 ; i++ )
      foo() ;
}

こういったトラブルを避けるためには、局所変数を使えば良い。

局所変数を使って、目的の処理…。改良版はココをクリックで表示。

void foo() { // Aを2回表示
   int i ; // 局所変数 foo::i
   for( i = 0 ; i < 2 ; i++ )
      printf( "A" ) ;
}
void main() {
   int i ; // 局所変数 main::i
   for( i = 0 ; i < 2 ; i++ )
      foo() ;
}


最近の構造型プログラム言語であれば、 変数には寿命(変数が、作られる/消える、タイミング)と、 スコープ(変数が使える範囲)がある。

#include <stdio.h>
// 静的大域変数(スコープ全体,寿命:起動から終了)
int x = 123;
void foo() {
   // 動的局所変数(スコープ:foo内部,寿命:foo呼出から戻るまで)
   int y = 234 ;
   // 静的局所変数(スコープ:foo内部,寿命:起動から終了)
   static int z = 345 ;
   x++ ; y++ ; z++ ;
   printf( "%d %d %d¥n" , x , y , z ) ;
}
void main() {
   foo() ;  // 124,235,346が表示
   foo() ;  // 125,235,347が表示
}

関数の引数

関数の引数の受け渡しの説明。

返り値の型 関数名( 仮引数の宣言 ) {
   何らかの処理 ;  // 関数に入ると仮引数が局所変数で作られ、
   return 式 ;   // 実引数が代入される。
}
void main() {
   関数名( 実引数 ) ;  // 実引数は仮引数にコピーされる。
}

値渡し、ポインタ渡しなどの説明をしたいけど、時間なので次週に説明。 残り時間では、BCPL→B言語→C言語(K&R-C→ANSI-C)→C++といった C言語の変遷を簡単に紹介。

処理速度の分析とオーダ記法

今回は、情報処理センターの機種更新に伴うパスワード再発行やら、 授業アンケートの作業に前半の時間をとられ、そのまま演習室にて授業。

2分探索法の処理時間分析

最初に、先週説明の単純サーチ と、2重ループの最大選択法 との比較をしながら、 以前のBLOG資料を使って、 2分探索法の処理時間が であることを説明する。

オーダ記法

次に、定番の説明であるけれど、 「単純サーチで、100件で1msecかかった。 データ10000件なら何秒かかる?」 同様に、「最大選択法のプログラムで、100件で10msecかかったら、10000件なら何秒?」 という質問から、オーダ記法の導入を説明する。

最後に、 , , といった、Nが大きな値になった時に、式で大きな値となる主要な部分を抜き出したもの がオーダといった説明を行う。

次回の授業での予習ネタとして、以下の式のオーダについて考えておくように…

斉藤卒研室の課題

簡単なunix環境での卒研の課題として、サーバに /home/lab15/Sotsu/access.log を 置いておいた。このファイルは、Webサーバでの数日前のアクセス履歴である。 このファイルの中から、2014年卒研のページ "/sotsu/lab14/" を見た人の 人数を数えよ。

(( /home/lab15/Sotsu/access.log ))
192.156.146.101 - - [29/Mar/2015:07:35:46 +0900]
"GET /~t-saitoh/exp/h8/sample/h8car/h8-3664.x  ....

SQLite3でデータベース

卒研でデータベースを使いたい人もいるようだけど、 MySQLとかまで完璧なのが必要なければ、SQLite を使ったほうが楽。 ただし、データ型は実質すべてtext型になるけど、簡単なアプリベースなら 支障はないはず。

<?php
   // データ保存用の sqlite-data はあらかじめ作っておく。
   //  sqlite-data の書き込み許可
   //    (手抜) $ chmod 777 sqlite-data
   //    (厳密) # chgrp sqlite-data
   //           # chmod 774 sqlite-data
   //  sqlite-data/.htaccess には"Require all denied"を書いて
   //  ディレクトリ内をWeb的にアクセス禁止にする。
   // サーバのPHPを使うと、エラーが見つからず苦労するかも
   // その時は、.htaccess ファイルに、以下の設定を記載しておく
   // "php_flag  display_errors On"
   // 説明しやすいように実行だけ関数をつくる
   function exec_command( $db , $cmd ) {
      if ( ($db->exec( $cmd )) === FALSE ) {
         print $db->lastErrorMsg() ;
      }
   }
   // データベースを作って初期データを登録
   function table_initialize( $db ) {
      exec_command( $db ,
         "create table Person(name text,phone text) ;" ) ;
      exec_command( $db ,
         "insert into Person (name,phone) values('t-saitoh','272925');" ) ;
      exec_command( $db ,
         "insert into Person (name,phone) values('tomoko'  ,'123456');" ) ;
      exec_command( $db ,
         "insert into Person (name,phone) values('mitsuki' ,'234567');" ) ;
   }
   // データベースを作る
   if ( !file_exists( "./sqlite-data/sample.db" ) ) {
      // なにも無い状態
      $db = new SQLite3( "./sqlite-data/sample.db" ) ;
      table_initialize( $db ) ;
   } else {
      // すでに作られている場合
      $db = new SQLite3( "./sqlite-data/sample.db" ) ;
   }
?>
<html>
<head>
</head>
<body>
<pre>
<?php
// 登録されているデータを全部表示
   if ( ($query = $db->query( "select * from Person" )) !== FALSE ) {
      while( $res = $query->fetchArray( SQLITE3_NUM ) ) {
         printf( "| %-10s | %-10s |\n" , $res[0] , $res[1] ) ;
      }
   }
?>
</pre>
</body>
</html>

システム

最新の投稿(電子情報)

最近の投稿(斉藤 徹)

アーカイブ

カテゴリー