ホーム » 2011 » 4月 » 27

日別アーカイブ: 2011年4月27日

2011年4月
« 3月   5月 »
 12
3456789
10111213141516
17181920212223
24252627282930

最近の投稿(電子情報)

アーカイブ

カテゴリー

再帰処理の速度分析

例年通りの進み方なんだけど、再帰処理の速度分析をするための説明を行う。 最初に、fact(N) , 配列の2分割積算 , fib(N) のプログラムを示し、 処理の流れのトレースを解説。 この後に、ハノイの塔の再帰方程式と数学的帰納法による証明を説明する。

ハノイの塔のディスクの移動回数を、 で表す。 ハノイの塔のルールより、N枚のディスクの移動には、(1)最下層の1枚の上にある、(N-1)枚を 隣に移動、(2)最下層の1枚を移動、(3)一旦隣に動かしておいた(N-1)枚を、目的の塔に 移動というステップを経由する。このため、 ただし また、最終的には、 が成り立つ。

ハノイの塔は、少ない枚数での移動を解いてみると、 が予想される。 この式が常に成り立つことを証明するため、枚についてこの予想が成り立つものと仮定する。 この時、枚については、

が成り立つので、

となり、 でも仮定が成り立つことが示される。よって、数学的帰納法により仮定は全ての 自然数について成り立つ。

この証明のような、式の中に自分自身が含まれるような方程式を、再帰方程式と呼ぶ。 再帰処理の速度予測では、これと同じように再帰方程式をたてる事ができる。

プログラムと再帰方程式

int fact( int N ) {
if ( N == 1 )
return 1 ;
else
return N * fact( N - 1 ) ;
}

このプログラムの処理時間は、N=1においては、if,==,return の一定の処理が行われるので、

Nが2以上では、if,==,*,-1,returnの処理と、fact()の再帰が行われる。よって、

この再帰方程式を、代入を繰り返しながらとけば、

が導き出せる。よって、階乗の再帰プログラムの処理時間のオーダは、 となる。

創造工学の導入実験でPerlと正規表現

4年の前期実験では、2週分を創造工学でのシステム作りの導入とするための、 基礎実験を行っている。クラスを3グループに分け、私の担当は初回にPHPによる、 Webプログラミングの説明。これにより簡単な掲示板やアンケートを作ってもらった。

2回目の今日は、1日実験でPerlと正規表現の実験を行った。 最初に、超単純英語によるBot作りをネタに、Perlの基本文法と、正規表現を体験してもらう。 理解度が速い人向けに、後半はメールデータを題材にしながら、 Jcode.pmを用いた文字コード変換、headerのmime_decodeを説明し、 このメールデータの中から、From,Toの部分を抽出するプログラムを作ってもらう。

#!/usr/bin/perl
# 超基本英語によるBot
while( <> ) {
   $line = $_ ;
   if ( $line =~ /like/ ) {
      if ( $line =~ /^(.*)\s+like(|s)\s+(.*)\.$/ ) {
         print "$1 は $3 が好きです。\n" ;
      }
   }
}
#!/usr/bin/perl
# メールデータの文字コード変換
use Jcode ;
my $head = 1 ;
while( <> ) {
   $line = $_ ;
   if ( $head ) {
      print Jcode->new( $line )->mime_decode->utf8 ;
      if ( $line =~ /^$/ ) {
         $head = 0 ;
      }
   } else {
      print Jcode->new( $line )->utf8 ;
   }
}

Perlを初めて使ってもらうので、 暗黙変数$_とのマッチングや、 「式 if ( 条件 ) ;」といった Perl らしい節操のない書き方は、説明を避けた。