ある関数(1)を定義する場合に、その定義の中で、その関数を利用する場合があります。
例えば、階乗( factorial )なども、その典型的な例です。
fact(n) = 1 ( if n == 1 )
= n * fact( n - 1 ) ( otherwize )
この例では、関数fact(n)のnが2より小さい場合は、値は1となり、それ以外の場合は、nとfact(n-1)の積で定義されています。
これから定義しようとしている関数(この例ではfact )を定義するのに、その定義の中で、その関数( fact )を利用するというのは奇異な感じがします(2)。
しかし、これでも、全然問題ありません。実際に、fact(3)を考えてみると、
fact(3) = 3 * fact(3-1) ( 3 == 1 でないので.. ) = 3 * fact(2) = 3 * 2 * fact(2-1) ( 2 == 1 でないので.. ) = 3 * 2 * fact(1) = 3 * 2 * 1 ( 1 == 1 なので.. )
となり、きちんと、fact(3) = 3 * 2 * 1 = 6となって、階乗の計算をしていることになります。
ポイントは、次の二つです。
下の行の定義を使い続ける限り、factが無くなることはないのですがいつか、一行目が利用されて、factを消すことができれば、循環の問題が解決されることがわかります。
では、「本当にいつかは、一行目が利用されるか」といえば、それは、引数nに着目することによって、保証できます。
すなわち、自然数nに対して、これが1でなければ、1より大きな自然数であり、下の行を利用すれば、次にfact関数の引数は、n - 1、すなわち、nより小さな数になることがわかります。つまり、下の行の場合は、fact自身こそ、なくなりはしないのですが、引数となるnの値は、どんどん小くなり、最後に必ず1になる(3)ので、いつかは、上の行が適用されることが保証される(4)わけです。
一見、不自然に見える帰納的定義ですが、慣れると実に自然な表現であることが理解ります。これは、人間が特定の問題を考える場合に、一度に全部の問題を考えるのではなく、取りあえず「一部から考える」という発想をした方が、簡単に感じるからです。
例えば、最初の例の階乗ですが、良くある説明は勿論、次のような形です。
fac(n) = n * (n-1) * .. * 2 * 1
しかし、この説明では、不明な点( ... )があるので、関数の定義(や、アルゴリズム(5))の表現としては不適切です。
そこで、この階乗の表現から、不明な点を除去することにより、次の式が得られます。
fac(n) = n * (n-1) * .. * 2 * 1 = n * ( (n-1) * .. * 2 * 1 ) = n * fac(n-1)
これは、最初の帰納的定義と全く同じ形をしています。もちろん、これに、停止性を示すために、n = 1の場合を追加しなければならないのですが、そこまで考えると、いかに、上記の階乗の表現が不適切であるかが理解ります。
別の言い方をすれば、fact(n)の計算では、n - 1回のかけ算を必要としますが、これを1回と残りのn - 2回のかけ算に分割して考えるという、ごく、自然な発想をすると、この帰納的な定義が導かれることがわかります。
課題 c.1.1 二つの数のかけ算をする関数 mul(a,b) を帰納的に定義しなさい ただし、足し算は使って構いません (ヒント : 一つ目の引数に関して帰納的に定義すればばよい )。
問題を考える場合に、帰納的定義が便利だとしても、それをプログラムで実現する場合にも便利だとは限りません(6)
帰納的に定義されている関数を実際にFortran Programとして、実現するには、帰納を繰り返しの形に書き換える必要があります。
実は、繰り返しを帰納的に書き換えるのは簡単なのですが、その逆は、必ずしも簡単ではありません(7)。
ここでは、簡単に、繰り返しに変換可能な再帰に関してだけ、説明します。
実は、最近のプログラミング言語は、帰納的な定義がされている関数をそのままの形で、記述するだけで、プログラムができてしまうようになっています。
この場合は、再帰を、以下のように繰り返しに書き換えるという作業が不要になるので、より便利になっていると考えてよいでしょう。
それにも拘らず、現在の再帰は、一般に、繰り返しに比較して、効率が悪いことが知られていますので、それを理由に、敢て(上記のように、再帰的定義がそのまま利用できる場合であっても.. )、再帰ではなく、繰り返しに変換する場合がありえます。
factの帰納的な定義から、繰り返しのProgramを作成することを考えます。
まず、自然に再帰的定義をFortranで記述すると以下のようになります。
integer function fact(n) integer n if ( n == 1 ) then fact = 1 else fact = n * fact(n-1) end if end
これは、一見、正しそうなのですが、残念ながら、fortranとしては、正しくないprogramといわれてしまいます。
そこで、これを次のように書換えます。これが、再帰から繰り返しへの変換のテンプレートになります。
integer function fact(n) integer n fact = 1 do if ( n == 1 ) then exit else fact = n * fact n = n - 1 end if end do end
integer function fact(n) integer n fact = 1 do i = 1, n fact = n * fact end do end
前回最大公約数を求めるための二つの方法(虱つぶし法と、互除法)のオーダーの差について説明しました。
明らかに、互除法の方が良い(8)わけだが、このようなプログラムを最初から作成できる(つまり、アルゴリズムを考えることができる.. )か、といえばそうではない。
そこで、どのように考えてゆけば、互除法が得られるかを考えてみましょう。
整数m,n ( m %gt; n )の最大公約数をgcm( m,n )で表すことにしよう。するとgcm(m,n)には次のような性質があることがわかります。
gcm(m,0) = m
gcm(m,n) = gcm(n,m)
gcm(m,n) = gcm(m-n,n)
そこで、これを用いて、gcmを次のように帰納的に定義します。
gcm(m,n) = m ( if n == 0 )
gcm(m,n) = gcm(n,m) ( if m < n )
gcm(m,n) = gcm(m-n,n) ( otherwize )
これを素直に、fortranのprogramにすると、次のようになります。
integer function gcm( m, n ) integer m integer n if ( n == 0 ) then gcm = m else if ( m < n ) then gcm = gcm ( n, m ) else gcm = gcm ( m - n, n ) end if end
これを、繰り返しにかえます。
integer function gcm( m, n ) integer m integer n do if ( n == 0 ) then exit else if ( m < n ) then wk = m m = n n = wk else m = m - n end if end do gcm = m end
分割統治法というのは、あるサイズNの問題が与えられた時に、その問題をよりサイズの小さな問題に分割(例えば、N = L + Mとし、サイズLの問題とMの問題に分割する)して、その小さな問題を解き、その結果に基いて、元のサイズの問題を解くという手法全般をさします。
分割統治法は、問題を解くための方針を与えると同時に、問題を効率良く解くための手段になっていることもしばしばあります。
サイズNの配列の中にあるデータxが、配列の何番目にあるかを知りたいとしよう。この場合のプログラムは次のようになります。
program lsearch_main
integer lsearch
integer array(100) ! 配列サイズは十分な大きさに
integer n
integer x
integer i
! 配列データを入力する
write(*,*) 'データの個数を入力してください'
read(*,*) n
do i = 1, n
write(*,*) i, '番目のデータを入力してください'
read(*,*) array(i)
end do
! 検索したいデータを入力する
write(*,*) '検索したいデータを入力してください'
read(*,*) x
! データを検索する
i = lsearch( array, n, x )
! 検索結果を表示する
if ( i == -1 ) then
write(*,*) 'データ', x, 'は、配列内にみあたりませんでした。'
else
write(*,*) 'データ', x, 'は、', i, '番目にありました。'
end if
end
! 関数 lsearch
! 配列内に、指定したデータがあるかどうかを判定する
! あれば、その位置を返す ( 値は 1 と size の間 )
! なければ -1 を返す
integer function lsearch( array, size, data )
integer array(*)
integer size
integer data
integer i
lsearch = -1 ! 発見できなかったときの準備
do i = 1, size
if ( array( i ) == data ) then
lsearch = i ! 発見できたいので、その場所を記録
exit
end if
end do
end
これの計算量は、データxが、サイズNの配列内にあると仮定すれば、最初に発見できる(コストは1 )可能性もありますし、最後(コストは配列サイズN )、に発見できる可能性もあるので、平均して(N+1)/2のコストが掛ることがわかります。オーダーとしては、O((N+1)/2) = O(N)となります。
もし、配列の内容に関して、なんの仮定もおけない場合は、これ以上のことはできないのですが仮りに、配列データが、小さい順に並んでいる場合には、より旨い方法があります。
これは、分割統治法の典型的な応用になっています。
program bsearch_main
integer bsearch
integer array(100) ! 配列サイズは十分な大きさに
integer n
integer x
integer i
! 配列データを入力する
write(*,*) 'データの個数を入力してください'
read(*,*) n
do i = 1, n
write(*,*) i, '番目のデータを入力してください'
read(*,*) array(i)
end do
! 検索したいデータを入力する
write(*,*) '検索したいデータを入力してください'
read(*,*) x
! データを検索する
i = bsearch( array, n, x )
! 検索結果を表示する
if ( i == -1 ) then
write(*,*) 'データ', x, 'は、配列内にみあたりませんでした。'
else
write(*,*) 'データ', x, 'は、', i, '番目にありました。'
end if
end
! 関数 bsearch
! 配列内に、指定したデータがあるかどうかを判定する
! あれば、その位置を返す ( 値は 1 と size の間 )
! なければ -1 を返す
integer function bsearch( array, size, data )
integer array(*)
integer size
integer data
integer md
integer mn
integer mx
mn = 1
mx = size
bsearch = -1 ! 発見できなかったときの準備
do
if ( mx < mn ) then
exit
end if
md = (mn + mx) / 2
if ( array( md ) == data ) then
bsearch = md ! 発見できたいので、その場所を記録
exit
else if ( array( md ) < data ) then
mn = md + 1
else
mx = md - 1
end if
end do
end
このプログラムでは、サイズNの配列内の検索をサイズN/2 + N/2に分割し、それぞれを検索するという考え方をします。
ここで重要なことは、「配列の内容が小さい順に並んでいる」という仮定が成立すると、「分割した一方だけを検索すれば良い」ことが、「一回の比較で済む」ということが解ることです。もし、この仮定が成立しなければ、分割統治法を適用した所で、得はありません(9)。
課題 c.2.1 bsearch のオーダーは、配列のサイズを N を入力のサイズと考えた 場合、どのくらいになるか ?
提出先
softa-2004@rep.s.cn.cst.nihon-u.ac.jp
ただし、次の点に注意してください。