基本情報技術者 2010年 春期 午後 問08
次のプログラムの説明及びプログラムを読んで、設問1〜3に答えよ。
〔プログラムの説明〕
プログラムSortは配列に格納された整数値のデータを再帰的に分割し、分割したデータの値の大小を比較しながら併合していくことでデータを昇順に整列するプログラムである。Sortは併合に副プログラムMergeを使用する。
(1) num個（num ≧ 1）のデータを配列listに格納してSortを呼び出すと、整列された結果が配列listに返却される。
(2) Sortでは、次の手順で配列listに格納された整数値のデータを整列する。
① 配列listに格納されているデータを、先頭からnum ÷ 2個と残りnum − num ÷ 2個とに分割して、二つの配列slist1とslist2に格納し、それぞれの配列に対して再帰的にSortを呼び出す。ここで、配列slist1とslist2の大きさは省略されているが、必要な領域は確保されている。この再帰的な呼出しは、引数で渡される配列listのデータの個数が1になると終了する。
② Mergeを使用し、二つの配列slist1とslist2を併合して一つの配列listにする。
(3) Mergeでは、次の手順で、整列済の二つの配列slist1とslist2を併合し、整列した一つの配列listを作成する。
① 配列slist1又はslist2のどちらか一方の要素がなくなるまで、次の②を繰り返す。
② 配列slist1とslist2の要素を順に比較して、小さい方から順に配列listに格納する。
③ 配列slist1又はslist2の残った要素を配列listに追加する。
(4) SortとMergeの引数の仕様を表1、2に示す。配列の添字は0から始まる。
次のデータを例にして、整列処理の流れを図に示す。
配列listのデータ：5, 7, 4, 2, 3, 8, 1
設問1：
問題文を見る プログラム中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：num ≧ 0
イ：num ≧ 1
ウ：num > 1
エ：num > 2
bに関する解答群
ア：list[i]
イ：list[num+i]
ウ：list[num1+i]
エ：list[num2+i]
cに関する解答群
ア：(i < num1) and (j < num2)
イ：(i < num1) or (j < num2)
ウ：(j < num1) and (i < num2)
エ：(j < num1) or (i < num2)
オ：(i+j) < (num1+num2)
カ：(i+j) ≦ (num1+num2)
キ：(i+j) > (num1+num2)
ク：(i+j) ≧ (num1+num2)
模範解答
a：ウ、b：ウ、c：ア
解説
解答の導き方
この問題では、配列を小さく分けてから、整列済みの部分を順に併合する処理について、分割の条件、配列からのコピー位置、併合時の繰返し条件を考えます。
a：再帰を止める条件
Sortの説明には、「引数で渡される配列listのデータの個数が1になると終了する」とあります。データが1個なら、すでに整列済みなので、それ以上分割する必要はありません。
したがって、データが2個以上ある場合だけ分割と再帰呼出しを行う条件にします。これに当てはまるのは「num > 1」です。
「num ≧ 1」だと、データが1個のときも分割してSortを呼び出すため、終了条件に到達できません。一方、「num > 2」では、データが2個のときに分割されず、整列されないままになる可能性があります。
b：後半の配列からコピーする位置
Sortでは、まず配列listの先頭からnum1個をslist1にコピーします。続いて、残りのnum2個をslist2にコピーします。
問題文では、先頭の個数を「num ÷ 2」、残りを「num − num1」としています。したがって、slist2に入れる値は、listの「num1番目」から始まります。添字は0から始まるため、コピーする位置は、繰返しの番号iにnum1を足した「num1+i」です。
例として、listが「5, 7, 4, 2, 3, 8, 1」の場合、num1は3、num2は4です。slist1にはlist[0]からlist[2]までをコピーし、slist2にはlist[3]からlist[6]までをコピーします。よって、slist2への代入は「list[num1+i]」です。
c：二つの配列を比較しながら併合する条件
Mergeでは、slist1とslist2の要素を比較し、小さい方をlistに入れます。この比較を行うには、両方の配列に未使用の要素が残っていなければなりません。
iはslist1で次に読む位置、jはslist2で次に読む位置です。そのため、slist1に要素が残っている条件は「i < num1」、slist2に要素が残っている条件は「j < num2」です。両方の条件が成り立つ間だけ、二つの値を比較できます。したがって、繰返し条件は「(i < num1) and (j < num2)」です。
たとえば、slist1が「7」、slist2が「4」の場合、最初は両方に要素があるため比較できます。小さい「4」をlistに入れると、slist2の要素がなくなります。この時点で二つの配列を比較する繰返しは終わり、残った「7」を後続の処理でlistに追加します。
ここで条件を「or」にすると、片方の配列が空になっても繰返しを続けてしまい、存在しない要素を読み取るおそれがあります。また、「i+j」と配列全体の個数を比べる条件では、片方だけが空になったかどうかを判断できず、二つの要素を安全に比較できるとは限りません。
誤りやすいポイント
- データの個数が1のときは、すでに整列済みです。再帰呼出しを続けないようにする条件を選びます。
- 後半の配列は、listの先頭からではなく、前半の個数num1だけ進んだ位置からコピーします。
- Mergeの比較処理では、二つの配列の両方に要素が残っている必要があります。「どちらか一方に残っている」条件と取り違えないようにします。
- 比較処理が終わったあとには、片方にだけ残った要素を追加します。比較処理と残りを追加する処理は、役割が異なります。
FAQ
Q: numが奇数の場合、二つの配列の大きさはどうなりますか？
A: num1は「num ÷ 2」で決まり、num2は残りの個数です。たとえばnumが7なら、num1は3、num2は4になります。
A: num1は「num ÷ 2」で決まり、num2は残りの個数です。たとえばnumが7なら、num1は3、num2は4になります。
Q: 比較する繰返しを「and」にするのはなぜですか？
A: 比較にはslist1とslist2の両方から値を取り出す必要があるためです。片方でも要素がなくなったら比較を止め、残りは後続の処理で追加します。
A: 比較にはslist1とslist2の両方から値を取り出す必要があるためです。片方でも要素がなくなったら比較を止め、残りは後続の処理で追加します。
Q: 片方の配列に残った要素を追加しても、昇順になりますか？
A: Mergeに渡される二つの配列は、どちらも整列済みです。比較処理で小さい値から取り出したあとに残る部分も整列済みなので、そのまま追加できます。
A: Mergeに渡される二つの配列は、どちらも整列済みです。比較処理で小さい値から取り出したあとに残る部分も整列済みなので、そのまま追加できます。
関連キーワード: マージソート、再帰処理、配列、昇順整列、併合
設問2：
問題文を見る 最初に与えられた配列listのデータが次の場合、プログラムSortのαにおける配列listの内容の移り変わりとして正しい答えを、解答群の中から選べ。
配列listのデータ：3, 8, 2, 7, 5, 1
なお、解答群の“→”は、内容が左から右へ移り変わっていくことを示している。
解答群
ア：2 → 3 → 2,3 → 2,3,8 → 1 → 5 → 1,5 → 1,5,7 → 1,2,3,5,7,8
イ：3 → 8 → 3,8 → 2,3,8 → 7 → 5 → 7,5 → 1,5,7 → 1,2,3,5,7,8
ウ：2,8 → 2,3,8 → 1,5 → 1,5,7 → 1,2,3,5,7,8
エ：3,8 → 2,3,8 → 7,5 → 1,5,7 → 1,2,3,5,7,8
オ：2,3,8 → 1,5,7 → 1,2,3,5,7,8
カ：3,8,2 → 7,5,1 → 1,2,3,5,7,8
模範解答
ウ
解説
解答の導き方
この問題では、αの位置にあるMergeの呼出しが行われるたびに、配列listにどの内容が格納されるかを順番に追います。
本文には、配列を「先頭からnum ÷ 2個」と「残り」に分け、それぞれをSortで整列してからMergeで併合するとあります。再帰処理（処理の中で同じ処理を呼び出すこと）なので、分割を進め、データが1個になったところから順に併合します。
まず、与えられた6個のデータは、最初に次の二つに分かれます。
- 前半：3, 8, 2
- 後半：7, 5, 1
データの個数が1個になった部分は、それ以上分割する必要がありません。そこから、Mergeが呼び出される順に結果を追います。
1番目は、前半の3, 8, 2をさらに分割したときの併合です。8と2を比べ、小さい2を先に格納し、残った8を続けて格納するため、結果は2,8です。
次に、3と2,8を併合します。小さい順に並べると、2,3,8になります。ここまでで、前半のデータが整列されました。
後半の7, 5, 1では、まず5と1を併合して1,5にします。続いて7と1,5を併合するので、結果は1,5,7です。
最後に、前半の2,3,8と後半の1,5,7を併合します。結果は1,2,3,5,7,8です。
したがって、αにおける配列listの内容の移り変わりは、2,8 → 2,3,8 → 1,5 → 1,5,7 → 1,2,3,5,7,8です。解答群ではウに当たります。
誤りやすいポイント
-
分割した順番と併合する順番を混同すること
Sortは前半を先に処理し、そのあと後半を処理します。前半の併合が終わってから、後半の併合に進みます。 -
配列全体を一度にMergeすると思うこと
Mergeは再帰処理の各段階で呼び出されます。そのため、途中の小さな配列の併合結果も順番に確認します。 -
併合の途中の比較結果を、αでの配列listの内容として数えること
解答群が示すのは、各Merge呼出しが完了したあとの配列の内容です。比較のたびに一つずつ追加される途中経過ではありません。
FAQ
Q: なぜ最初のMergeの結果は8,2ではなく2,8なのですか？
A: Mergeは、整列済の二つの配列を比べ、小さい値から順に格納する処理だからです。8と2では、2が先になります。
A: Mergeは、整列済の二つの配列を比べ、小さい値から順に格納する処理だからです。8と2では、2が先になります。
Q: データが1個になった配列もMergeしますか？
A: 1個のデータは、その時点ですでに昇順に整列されています。まず分割を止め、複数の配列を併合できる段階まで戻ってからMergeします。
A: 1個のデータは、その時点ですでに昇順に整列されています。まず分割を止め、複数の配列を併合できる段階まで戻ってからMergeします。
Q: なぜ後半の1,5ができる前に、前半の処理が進むのですか？
A: Sortは前半を先に再帰的に呼び出し、その処理が終わってから後半を呼び出します。そのため、前半の併合結果が先に現れます。
A: Sortは前半を先に再帰的に呼び出し、その処理が終わってから後半を呼び出します。そのため、前半の併合結果が先に現れます。
関連キーワード: マージソート、再帰処理、配列、分割統治法、併合
設問3：
問題文を見る 副プログラムMergeのβ部分と同じ結果を得る処理として正しい答えを、解答群の中から選べ。
解答群
模範解答
エ
解説
解答の導き方
この設問では、すでに比較して並べ終えた部分の後ろに、残った値をどの位置へ入れるかを考えます。
配列は、複数の値を番号付きで並べて扱う入れ物です。配列の位置を示す番号を添字といい、この問題では添字は0から始まります。また、併合とは、整列済みの複数の並びを順序を保って一つにまとめることです。
Mergeでは、最初に 、 とします。はslist1から取り出した値の数、はslist2から取り出した値の数を表します。二つの配列の値を比べてlistに入れるたびに、対応する値を1増やします。
このとき、すでにlistへ入れた値は合計で 個です。そのため、次に値を入れる位置は です。プログラムの前半でも、値をlist[i+j]に格納しています。
前半の比較処理は、slist1かslist2のどちらか一方の要素がなくなったところで終わります。つまり、残りを処理し始める時点では、少なくとも一方の配列をすべて使い切っています。
- slist1に値が残っている場合、slist2はすべて使い切っているため、 です。次の格納位置は となります。したがって、slist1の残りはlist[i+num2]から入れます。
- slist2に値が残っている場合、slist1はすべて使い切っているため、 です。次の格納位置は となります。したがって、slist2の残りはlist[j+num1]から入れます。
この二つの位置を使っているのがエです。選択肢の二つの処理のうち、残っていない側の処理は繰り返されず、残っている側だけがlistの続きの位置へ値を入れます。
問題の例である最終段階では、slist1が「4、5、7」、slist2が「1、2、3、8」です。前半の比較処理が終わると、listには「1、2、3、4、5、7」が入り、、 です。slist1は使い切り、slist2の「8」が残っています。次の位置は なので、list[6]に入ります。エの式と一致します。
誤りやすいポイント
- list[i]やlist[j]のように、残っている配列の添字だけを使うと、すでにlistへ入れた値の後ろに続けて格納できません。出力先の位置には、もう一方の配列から入れた値の数も反映させる必要があります。
- slist1の残りを入れる位置にはnum2、slist2の残りを入れる位置にはnum1を加えます。残りの配列自身の要素数ではなく、すでに使い切った配列の要素数を加える点が大切です。
- 前半の比較処理が終わったとき、両方の配列に値が残っているわけではありません。少なくとも一方は使い切っているので、残りを入れる処理ではその条件を利用できます。
FAQ
Q: なぜ、slist1に残りがあるときはnum2を加えるのですか？
A: その場合、slist2はすでにすべてlistに入っています。slist2から入れたnum2個分の後ろに、slist1の残りを続けて入れるためです。
A: その場合、slist2はすでにすべてlistに入っています。slist2から入れたnum2個分の後ろに、slist1の残りを続けて入れるためです。
Q: slist1とslist2の両方に値が残ることはありますか？
A: 前半の比較処理は、どちらか一方の要素がなくなるまで続きます。そのため、処理が終わった時点で両方に値が残ることはありません。
A: 前半の比較処理は、どちらか一方の要素がなくなるまで続きます。そのため、処理が終わった時点で両方に値が残ることはありません。
Q: 選択肢のように二つの処理に分けても、元の処理と同じ結果になりますか？
A: はい。残りがある側の処理だけが実行され、もう一方は条件を満たさないため実行されません。残った値を正しい位置に入れられれば、元の処理と同じ結果になります。
A: はい。残りがある側の処理だけが実行され、もう一方は条件を満たさないため実行されません。残った値を正しい位置に入れられれば、元の処理と同じ結果になります。
関連キーワード: 配列、添字、併合、整列、反復処理
