私なりに再帰を読みとくコツとして、その関数が何を求めるものなのか、そしてそれを求めるためにどのように問題を分割しているかに注目すると読みやすくなります。
疑似コード2のFIND-MAXIMUM-SUBARRAYで求めようとしているのは、配列Aのlow番目からhigh番目の間での部分配列のうち和が最大となるものの(左端の番号,右端の番号,和)の組です。
lowとhighが同じ、つまり要素が1個の部分配列で和が最大となるのは、その要素1個だけ含む部分配列であるので、それを返します。
そうでない場合は、真ん中の番号midを取ると、最大部分和となるのは
- mid含むmidの左側だけ(low~mid番目)で作る部分配列
- mid含まないmidの右側だけ(mid+1~high番目)で作る部分配列
- midをまたいで作る部分配列
のうち、和が最大となるものです。だから、それらをそれぞれ求め、その中での最大を探します。
この時、「mid含むmidの左側だけで作る部分配列」などを求めるため、同じロジックを使いまわします。これが再帰です。
具体的にやってみます。配列のインデックスは1始まりとして、
のような、5個の要素を持つ配列の最大部分配列を求めます。
まず、これを求めるために、FIND-MAXIMUM-SUBARRAY(A, 1, 5)
を呼び出します。
low=1とhigh=8は等しくないので、elseに入ります。
midは(1+5)/2の床関数、つまり小数点切り捨てで3になります。
ここで左側最大を探すべくFIND-MAXIMUM-SUBARRAY(A, 1, 3)
を呼び出します。呼び出しの階層がわかりやすくなるよう、階層の深さを引用のマークダウンで表現します。
low=1とhigh=3は等しくないので、elseに入ります。
midは(1+3)/2の床関数で2になります。
ここで左側最大を探すべくFIND-MAXIMUM-SUBARRAY(A, 1, 2)
を呼び出します。
low=1とhigh=2は等しくないので、elseに入ります。
midは(1+2)/2の床関数で1になります。
ここで左側最大を探すべくFIND-MAXIMUM-SUBARRAY(A, 1, 1)
を呼び出します。
low=1とhigh=1は等しいので、**(1, 1, 1)**が返ります。
今度は右側最大を探すべくFIND-MAXIMUM-SUBARRAY(A, 2, 2)
を呼び出します。
low=2とhigh=2は等しいので、**(2, 2, -2)**が返ります。
midをまたいだ最大を探します。
こっちはわかっているということで簡略。全部取った時が最大値-1なので、**(1, 2, -1)**が返ります。
それぞれの最大を取るときの和を比較します。左側最大の1、右側最大の-2、またいだ最大の-1では、左側最大が最大であるため、その値の組である**(1, 1, 1)**が返ります。
次に右側最大を探すべくFIND-MAXIMUM-SUBARRAY(A, 3, 3)
を呼び出します。
low=3とhigh=3は等しいので、**(3, 3, 3)**が返ります。
1番目から3番目までで、中央の2番目をまたいだ最大を探します。
簡略。1番目~3番目すべて取った場合に最大なので、**(1, 3, 2)**が返る。
出そろったそれぞれの最大和を比較します。左側最大の1、右側最大の3、またいだ最大2なので、最大は右側最大。よって**(3, 3, 3)**が返ります。
次に右側最大を求めるため、FIND-MAXIMUM-SUBARRAY(A, 4, 5)
を呼び出します。
簡略。左側最大はA[4]=4,右側最大はA[5]=-5,またいだ最大は4番目5番目を取った場合で―1。この中で最大は左側最大なので、**(4, 4, 4)**が返る。
そしてまたいだ最大を求めます。
簡略。**(3, 4, 7)**が返る。
それぞれの最大和を比較します。右側最大が3、左側最大が4、またいだ最大が7なので、最大はまたいだもの。最終結果として**(3, 4, 7)**が得られます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2020/04/15 23:39