再帰処理の速度分析
例年通りの進み方なんだけど、再帰処理の速度分析をするための説明を行う。 最初に、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 らしい節操のない書き方は、説明を避けた。