配列を分割するプログラム（マージソート）｜アルゴリズムとプログラミング問題を解くコツ
2022-11-28 更新
科目 B 問題の新しい擬似言語に合わせて、プログラムを変更しました。
なお、本記事では過去問題を一部改変しています。
この連載では、基本情報技術者試験で、多くの受験者が苦手意識を持っている科目 B 試験 アルゴリズムとプログラミング分野の「アルゴリズム穴埋め問題」に的を絞って、正解を見出すポイントを詳しく説明します。
苦手を克服するには、短いプログラムを何度も練習して、穴埋めに慣れることが重要です。
そのために、旧制度の午後試験のアルゴリズム過去問題の一部をアレンジした練習問題を作りました。とても短い問題ですので、気軽に取り組んでください。
練習問題
手続 Split は、要素数 num 個の配列 list を 2 つに分割して、前半部を配列 slist1 に格納し、後半部を配列 slist2 に格納する。配列の添字は、 0 から始まる。プログラム中のaに入れる正しい答えを、解答群の中から選べ。
［プログラム］
◯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 は、何らかの値だ」と思っていたのでは、プログラムの内容をつかめないでしょう。
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 のときに a に何が入ればよいか考えればよいのです。
ポイント3: 必ず解答群を見て考える
「考える」といっても、プログラムの空欄だけを見て考えるのではありません。これも、すべての問題に共通したポイントなのですが、必ず解答群を見て考える ようにしてください。
ここでは、
- 要素数 7 個の配列を 3 個と 4 個に分割する（ num = 7, num1 = 3, num2 = 4 ）
- i = 0
を想定しています。
したがって、
slist2[i] ← aの部分は、
slist2[0] ← aです。
配列 slist1 の先頭の要素である slist2[0] に代入するものが答えです。
- 前半の 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 関連タグ免除試験を受けた 74.9% の方が、科目A免除資格を得ています。
具体的な値を入れるとプログラムがわかる練習問題｜アルゴリズムとプログラミング問題を解くコツ
update
具体例からヒントを掴む練習問題｜アルゴリズムとプログラミング問題を解くコツ
update
プログラムを分割するコツがわかる練習問題｜アルゴリズムとプログラミング問題を解くコツ
update
手順をヒントにトレースする練習問題｜アルゴリズムとプログラミング問題を解くコツ
update
トレースのテクニックが身につく練習問題｜アルゴリズムとプログラミング問題を解くコツ
update
2進数を掛け算するプログラム | アルゴリズムとプログラミング問題を解くコツ
update
ヒープを配列で実現するプログラム｜アルゴリズムとプログラミング問題を解くコツ
update
ルールに従って検査文字（チェックディジット）を求めるプログラム｜アルゴリズムとプログラミング問題を解くコツ
update
配列のマッチング（突合せ）を行うプログラム｜アルゴリズムとプログラミング問題を解くコツ
update
2進数の知識が必要なプログラム｜アルゴリズムとプログラミング問題を解くコツ
update『プログラムはなぜ動くのか』（日経BP）が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”
大手電気メーカーでＰＣの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識０ベースのＩＴエンジニアや一般書店フェアなどの一般的なＰＣユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。
主な著作物
- 「プログラムはなぜ動くのか」（日経BP）
- 「コンピュータはなぜ動くのか」（日経BP）
- 「出るとこだけ! 基本情報技術者」 (翔泳社)
- 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」（翔泳社）
- 「ｉｆとｅｌｓｅの思考術」（ソフトバンククリエイティブ） など多数
