配列を分割するプログラム(マージソート)|アルゴリズムとプログラミング問題を解くコツ


2022-11-28 更新
info2022 年 11 月

科目 B 問題の新しい擬似言語に合わせて、プログラムを変更しました。
なお、本記事では過去問題を一部改変しています。

この連載では、基本情報技術者試験で、多くの受験者が苦手意識を持っている科目 B 試験 アルゴリズムとプログラミング分野の「アルゴリズム穴埋め問題」に的を絞って、正解を見出すポイントを詳しく説明します。

苦手を克服するには、短いプログラムを何度も練習して、穴埋めに慣れることが重要です。

そのために、旧制度の午後試験のアルゴリズム過去問題の一部をアレンジした練習問題を作りました。とても短い問題ですので、気軽に取り組んでください。

練習問題

問 8 「マージソート」(平成 22 年度 春期 午後)を一部改変

手続 Split は、要素数 num 個の配列 list を 2 つに分割して、前半部を配列 slist1 に格納し、後半部を配列 slist2 に格納する。配列の添字は、 0 から始まる。プログラム中のaに入れる正しい答えを、解答群の中から選べ。

swipeプログラムは横スクロールできます

[プログラム]

◯Split(整数型の配列: list, 整数型: num, 整数型の配列: slist1, 整数型の配列: slist2)
  整数型: num1, num2, i

  num1 ← num ÷ 2        /* slist1の要素数計算 */
  num2 ← num - num1     /* slist2の要素数計算 */

  for (i を 0 から num1 まで 1 ずつ増やす)
    slist1[i] ← list[i]
  endfor

  for (i を 0 から num2 まで 1 ずつ増やす)
    slist2[i] ←  a
  endfor

a の解答群

ア list[i]  
イ list[num + i]
ウ list[num1 + i]  
エ list[num2 + i]

ポイント1: 変数に具体的な値を想定する

すべての問題に共通したポイントがあります。それは、変数に具体的な値を想定する ということです。

このプログラムには、配列の要素数として num 、num1 、num2 という変数が登場しますが、それらを「 num 、num1 、num2 は、何らかの値だ」と思っていたのでは、プログラムの内容をつかめないでしょう。

具体的な値として、たとえば num に 7 を想定してみてください。

num1 ← num ÷ 2 なので、 num1 は 7 ÷ 2 = 3 になります(整数型の計算なので除算の小数点以下がカットされます)。
num2 ← num – num1 なので、 num2 は 7 – 3 = 4 になります。

これによって「 要素数 num 個の配列を num1 個と num2 個に分割する」というつかみどころのない問題が、

要素数 7 個の配列を 3 個と 4 個に分割する

という明確な問題になりました。

ポイント2: ループは最初の処理を想定する

「要素数 7 個の配列を 3 個と 4 個に分割する」という想定で、aの穴埋めをやってみましょう。

このaは、変数 i を使ったループ(繰り返し処理)の中にあります。きっと「うわっ! ループだ! 苦手だ!」という人が多いでしょう。

  for (i を 0 から num2 まで 1 ずつ増やす)
    slist2[i] ←  a
  endfor

ループの穴埋めをするポイントは、 最初の処理を想定する ということです。

「ループなのだから、最初から最後まで処理の流れを追いかける必要があるのでは?」と思っていたのでは、頭が混乱してしまいます。
「ループの穴埋めは、繰り返しのどの場面でも成り立つのだから、わかりやすい最初の処理を想定しよう」と割り切ってください。

そうすれば、ぐっと気持ちが楽になります。

最初の処理では、変数 i = 0 です。

i = 0 のときに a に何が入ればよいか考えればよいのです。

ポイント3: 必ず解答群を見て考える

「考える」といっても、プログラムの空欄だけを見て考えるのではありません。これも、すべての問題に共通したポイントなのですが、必ず解答群を見て考える ようにしてください。

ここでは、

  • 要素数 7 個の配列を 3 個と 4 個に分割する( num = 7, num1 = 3, num2 = 4 )
  • i = 0

を想定しています。

したがって、

slist2[i] ← aの部分は、
slist2[0] ← aです。

配列 slist1 の先頭の要素である slist2[0] に代入するものが答えです。

配列 list の list[0] ~ list[6] のうち、

前半の 3 個の list[0] ~ list[2]
-> 配列 slist1 に格納
後半の 4 個の list[3] ~ list[6]
-> 配列 slist2 に格納

となります。

ここでは先頭の要素を想定しているので、

slist2[0] ← a は、
slist2[0] ← list[3] です。

さあ、これで穴埋めの準備がすべて整いました。

num = 7 、num1 = 3 、num2 = 4 、i = 0 を想定して list[3] になるものを、解答群から選んでみましょう。

変数のままの解答群は、以下のようになっています。

ア list[i]  
イ list[num + i]
ウ list[num1 + i]  
エ list[num2 + i]

これらに num = 7 、num1 = 3 、num2 = 4 、i = 0 を設定すると、以下のようになります。

ア list[0]  イ list[7]
ウ list[3]  エ list[4]

これらの中で、list[3] になっているのは、選択肢ウだけです。したがって、選択肢ウが正解です。

いかがでしょう。「あれあれ、できちゃった!」という気持ちになって、苦手意識が解消されたでしょう。

もしも、「 1 回練習しただけでは不安」なら、何度も繰り返し記事を読んで、ポイントをしっかりとつかんでください。

 

解答

「習うより慣れろ」ということわざがあります。アルゴリズム穴埋め問題の克服に関しては、正にその通りでしょう。

この連載では、これからも短い練習問題を掲載していきますので、穴埋めに慣れることを目指してください。

正解を見出すポイントとして、同じことが示されることもあると思いますが、それは、多くの問題に共通したポイントがあるからです。

それでは、またお会いしましょう!

label 関連タグ
科目A試験は、
免除できます。
独習ゼミで科目A試験を1年間免除して、科目B試験だけに集中しましょう。
免除試験を受けた 74.9% の方が、
科目A免除資格を得ています。
科目A免除試験 最大 2 回の
受験チャンス !
info_outline
科目A免除試験 最大 2 回の
受験チャンス !
詳しく見てみるplay_circle_filled
label これまでの『アルゴリズムとプログラミング問題を解くコツ』の連載一覧 label 著者