質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

関数

関数(ファンクション・メソッド・サブルーチンとも呼ばれる)は、はプログラムのコードの一部であり、ある特定のタスクを処理するように設計されたものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

配列

配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

Q&A

解決済

1回答

1650閲覧

最大部分配列問題(再帰の概念について)

macuserdesu

総合スコア8

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

関数

関数(ファンクション・メソッド・サブルーチンとも呼ばれる)は、はプログラムのコードの一部であり、ある特定のタスクを処理するように設計されたものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

配列

配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

0グッド

1クリップ

投稿2020/04/15 14:35

MITのアルゴリズムイントロダクション第3版の最大部分配列の擬似コードからの質問です。
簡潔に言うと自分は関数内で複数呼び出される再帰関数の処理の流れを追うことが出来ません。
フィボナッチ数や階乗のプログラムなどの基本的な再帰の流れは追うことができるのですが、マージソートなどはギリギリ追跡できたレベルです。
そこで最大部分配列の擬似コードを見たときに具体例などでも試しましたが処理の流れを追うことが出来ませんでした。
疑似コード1
擬似コード2
上記のリンクにある画像にコードがあります。
これを具体例にとって処理の流れを具体的に教えていただきたいです。
ちなみに擬似コード1は理解しています。擬似コード2の処理の流れがわかりません。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

私なりに再帰を読みとくコツとして、その関数が何を求めるものなのか、そしてそれを求めるためにどのように問題を分割しているかに注目すると読みやすくなります。
疑似コード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始まりとして、

A[] = {1, -2, 3, 4, -5}

のような、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 16:10

swordone

総合スコア20649

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

macuserdesu

2020/04/15 23:39

完璧に理解しました!とても分かり易かったです。ありがとうがざいます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問