配列のマッチング(突合せ)を行うプログラム|アルゴリズム問題を解くコツ


2020-09-08 更新

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

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

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

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

練習問題

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

以下は、購入した商品の中から、値引きの対象となる商品を見つけて、その数量を求めるプログラムである。購入した商品は、 購入[ ] という構造型(品番品名数量から構成されたデータ型)の配列に格納され、要素数は 購入行数 に格納されている。値引きの対象となる商品は、 対象[ ] という構造型(品番数量から構成されたデータ型)の配列に格納され、要素数は 対象行数 に格納されている。ぞれぞれの配列は、 品番 の昇順に整列されていて、 品番 が一致した場合は、 購入[ ]数量 を、 対象[ ]数量 に格納する。 購入[ ] 購入行数対象[ ]対象行数 は、以下に示したプログラムとは別の場所で宣言された大域的変数である。 購入[ ]対象[ ] の添字は、 1 から始まる。プログラム中の  a   b  に入る正しい答えを、解答群の中から選べ。

この問題では、配列名や変数名が日本語なので、わかりやすいように青色文字で示しています

[格納されたデータの例]


[プログラム]

○整数型:K, T
・K ← 1
・T ← 1
■(K ≦ 購入行数) and (T ≦ 対象行数)
|▲購入[K].品番 = 対象[T].品番
||・対象[T].数量 ← 購入[K].数量
||・  a  
||・  b  
|+---
||▲購入[K].品番 < 対象[T].品番
|||・  a  
||+ーーー
|||・  b  
||▼
|▼
■

a と b の解答群

ア K ← K + 1
イ K ← 購入[K].品番 + 1
ウ T ← T + 1
エ T ← 対象[T].品番 + 1

ポイント1:構造型とは何かを知っておこう

この問題には、午後試験の問題用紙に掲載された「共通に使用される擬似言語の記述形式」に説明がない「構造型(構造体、レコード型、ユーザー定義型とも呼ばれます)」が登場します。

擬似言語は、 C 言語によく似ていて、 C 言語には構造型があるので、「わかるよね!」というノリで出題されているのです。しかし、 C 言語の経験がないなら「わかりません!」だと思いますので、この機会に構造型とは何かを知っておきましょう。

label関連記事

午後問題の歩き方 | 地道にアルゴリズム問題に取り組む(1)
3.1 擬似言語の読み方は、事前に確実にマスターする

構造型は、複数のデータをまとめたデータ型です。 C 言語では、 struct というキーワードで構造型を定義します。この問題に示された構造型を C 言語風に定義すると、以下のようになります。

struct 購入構造型 {
  文字列型 品番;
  文字列型 品名;
  整数型 数量;
};

struct 対象構造型 {
  文字列型 品番;
  整数型 数量;
};

構造型は、ユーザーが独自に定義したデータ型であり、変数や配列のデータ型として使います。

ここでは、構造型の名前を、購入構造型と対象構造型にしています。構造体にまとめられた個々のデータをメンバと呼びます。購入構造体のメンバは、品番、品名、数量です。対象構造体のメンバは、品番、数量です。

 

この問題では、購入[ ] および 対象[ ] という配列のデータ型が、購入構造型および対象構造型になっています。構造型の配列の個々の要素には、構造体のメンバ一式が入っています。

構造体の配列の個々の要素で、メンバを指定するときは、

配列名[添字].メンバ名

という表記を使います。このドット( . )を「~の」と読むとわかりやすいでしょう。

たとえば 購入[1].品番 なら、「 購入[1] の品番」と読みます。以下に例を示します。


構造体とは何かがわかったら、問題に示されたプログラムを見てみましょう(以下に示します)。

 購入[K].品番 = 対象[T].品番

は、「購入[K]の品番と対象[T]の品番が一致する」という意味です。

対象[T].数量 ← 購入[K].数量

は、「対象[T]の数量に、購入[K]の数量を格納する」という意味です。

購入[K].品番 < 対象[T].品番

は、「購入[K]の品番が、対象[T]の品番より小さい」という意味です。

○整数型:K, T
・K ← 1
・T ← 1
■(K ≦ 購入行数) and (T ≦ 対象行数)
|▲購入[K].品番 = 対象[T].品番
||・対象[T].数量 ← 購入[K].数量
||・  a  
||・  b  
|+---
||▲購入[K].品番 < 対象[T].品番
|||・  a  
||+ーーー
|||・  b  
||▼
|▼
■

ポイント2:突合せのやり方を知っておこう

この問題のテーマは、午後試験のソフトウェア設計の分野でよく出題される 突合せ です。

突合せとは、「整列済みの 2 つのファイルの先頭から 1 件ずつデータを読み出し、一致したら特定の処理を行って両方を読み進め、不一致ならその先で一致する可能性がある方だけを読み進める」という処理です。

この問題では、 2 つのファイルではなく、 2 つの配列で突合せを行っていますが、やり方は同様です。もしも、「ソフトウェア設計の突合せの問題をやったことがありません!」なら、この機会に突合せのやり方を知っておきましょう。

以下に、問題に示された 2 つの配列で突合せを行う手順を示します。

【手順 1 】
それぞれの先頭の要素を読み出して、品番を比べます。
購入[1].品番 < 対象[1].品番 なので、 購入[ ] だけを先に読み進めます。
なぜなら、それぞれの配列は、品番の昇順に整列されているので、購入[ ]だけを先に読み進めれば、対象[ ]と品番が一致する要素が見つかる可能性があるからです。
【手順 2 】
購入[2].品番 = 対象[1].品番 なので、 対象[1].数量 に 購入[2].数量 を格納して、 購入[ ] と 対象[ ] の両方を先に読み進めます。
一致したら両方を読み進め、不一致なら一方だけを読み進めるのが、突合せのポイントです。
【手順 3 】
購入[3].品番 > 対象[2].品番 なので、対象[ ] だけを先に読み進めます。
【手順 4 】
購入[3].品番 = 対象[3].品番 なので、 対象[3].数量 に 購入[3].数量 を格納して、 購入[ ] と 対象[ ] の両方を先に読み進めます。
【手順5】
この時点で、 対象[ ] が末尾を超えたので、突合せを終了します。
突合せを繰り返す条件は、 「 購入[ ] が末尾を超えていない、かつ、 対象[ ] が末尾を超えていない」です。

突合せのやり方がわかったら、問題の穴埋めができるでしょう。以下に、もう一度、プログラムと解答群を示します。

○整数型:K, T
・K ← 1
・T ← 1
■(K ≦ 購入行数) and (T ≦ 対象行数)
|▲購入[K].品番 = 対象[T].品番
||・対象[T].数量 ← 購入[K].数量
||・  a  
||・  b  
|+---
||▲購入[K].品番 < 対象[T].品番
|||・  a  
||+ーーー
|||・  b  
||▼
|▼
■

a と b の解答群

ア K ← K + 1
イ K ← 購入[K].品番 + 1
ウ T ← T + 1
エ T ← 対象[T].品番 + 1

 a   b は、 2 か所ずつあります。上側にある

購入[K].品番 = 対象[T].品番

という条件で、  a  b  の両方を行っています。これは、どちらか一方が 購入[ ] を読み進める処理で、もう一方が 対象[ ] を読み進める処理です。

ここでは、どちらがどちらなのかを判断できません。

 

下側にある

購入[K].品番 < 対象[T].品番

という条件で、  a  を行っています。これは、購入[ ] を読み進める処理です。

購入[ ] の添字は、 K で示されているので、選択肢の中では、 K の値を 1 つ増やす K ← K + 1(選択肢ア)が適切です。

 a  が 購入[ ] を読み進める処理だとわかったので、  b  は、対象[ ] を読み進める処理であることがわかります。

対象[ ] の添字は、 T で示されているので、選択肢の中では、 T の値を 1 つ増やす T ← T + 1(選択肢ウ)が適切です。

ポイント3:難しそうな選択肢を選ばない

多くの受験者が、「午後試験は時間が足りない!」と言っています。

そのため、「当てずっぽう」で選択肢を選ぶこともあるでしょう。これは、仕方がないことだと思いますが、「選択肢の内容が他より難しそうだから」という理由で選ばないでください。

なぜなら、難しそうな選択肢は、間違いである場合が多いからです。ここで、もう一度、今回の問題の選択肢を見てみましょう。

a と b の解答群

ア K ← K + 1
イ K ← 購入[K].品番 + 1
ウ T ← T + 1
エ T ← 対象[T].品番 + 1

選択肢アとイは K に代入を行い、ウとエは T に代入を行っています。アとウより、イとエの方が難しそうなことをしているので、「難しそうな方が正解かな?」と思うかもしれませんが、実際の正解はアとウです。

これは、「簡単そうな方を選べ」ということではありません。「当てずっぽう」で選択肢を選ぶときには、「選択肢の内容を気にしないで選べ」ということです。

ただし、すべての選択肢から当てずっぽうに選ぶのではなく、「これは絶対に正解ではない」という選択肢を消して、残ったものの中から選んでください。そうすれば、当てずっぽうが当たる確率が上がり、残った選択肢を見て「あっ、そうか!」と正解に気付くこともあります。

 

解答a - ア, b - ウ

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

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

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

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

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ラーニング

人気記事

人気のタグ