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


2020-09-08 更新

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

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

そのために、実際の試験問題の一部をアレンジした練習問題を作りました。とても短い問題ですので、気軽に取り組んでください。

info編集部注: 本記事では過去問題を一部改変しています。

練習問題

info編集部注: スマートフォンでご覧の際は、アルゴリズムや表を横スクロールすると全文をご覧になれます
問 8 「マージソート」(平成 22 年度 春期 午後)を一部改変

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

[プログラム]

〇Split(整数型:list[], 整数型:num, 整数型:slist1[], 整数型:slist2[])
〇整数型:num1, num2, i
・num1 ← num ÷ 2        /* slist1の要素数計算 */
・num2 ← num - num1     /* slist2の要素数計算 */
■ i:0, i < num1, 1
|・slist1[i] ← list[i]
■
■ i:0, i < num2, 1
|・slist2[i] ←   a  

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 を使ったループ(繰り返し処理)の中にあります。きっと「うわっ! ループだ! 苦手だ!」という人が多いでしょう。

■ i:0, i < num2, 1
|・slist2[i] ←   a  

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

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

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

最初の処理では、変数 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 関連タグ
実は、午前試験を『免除』できます 独習ゼミで午前免除試験を受けた 86% の方が、
午前試験を免除しています。
2021 年度 春期試験 向け
最大 20 % OFF!
info_outline
2021年度 春期試験向け
最大 20 % OFF!
詳しく見てみるplay_circle_filled
label これまでの『アルゴリズム問題を解くコツ』の連載一覧 label 著者

『プログラムはなぜ動くのか』(日経BP)が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”

大手電気メーカーでPCの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識0ベースのITエンジニアや一般書店フェアなどの一般的なPCユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。

主な著作物

  • 「プログラムはなぜ動くのか」(日経BP)
  • 「コンピュータはなぜ動くのか」(日経BP)
  • 「出るとこだけ! 基本情報技術者」 (翔泳社)
  • 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」(翔泳社)
  • 「ifとelseの思考術」(ソフトバンククリエイティブ) など多数

grade IPA認定
午前免除制度対応
eラーニング

人気記事

人気のタグ