配列のマッチング（突合せ）を行うプログラム｜アルゴリズムとプログラミング問題を解くコツ

矢沢 久雄
2022-11-28 更新

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

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

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

練習問題

問 8 (平成 25 年度 春期 午後）を一部改変

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

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

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

［プログラム］

整数型: K, T
K ← 1
T ← 1

while (k が購入行数以下でかつ T が対象行数以下)
  if (購入[K].品番と対象[T].品番が等しい)
    対象[T].数量 ← 購入[K].数量
    a
    b
  elseif (購入[K].品番が対象[T].品番より小さい)
    a
  else
    b
  endif
endwhile

a と b の解答群

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

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

この問題には、科目 B サンプル問題に掲載された「共通に使用される擬似言語の記述形式」に説明がない「構造型（構造体、レコード型、ユーザー定義型とも呼ばれます）」が登場します。

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

構造型は、複数のデータをまとめたデータ型です。 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

while (k が購入行数以下でかつ T が対象行数以下)
  if (購入[K].品番と対象[T].品番が等しい)
    対象[T].数量 ← 購入[K].数量
    a
    b
  elseif (購入[K].品番が対象[T].品番より小さい)
    a
  else
    b
  endif
endwhile

ポイント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

while (k が購入行数以下でかつ T が対象行数以下)
  if (購入[K].品番と対象[T].品番が等しい)
    対象[T].数量 ← 購入[K].数量
    a
    b
  elseif (購入[K].品番が対象[T].品番より小さい)
    a
  else
    b
  endif
endwhile

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: 難しそうな選択肢を選ばない

多くの受験者が、「旧午後試験では時間が足りない！」と言っていました。 科目 B 試験で出題数が変わったとは言え、 1 問平均 5 分で 16 問解答する必要があるため、この傾向は変わらないと予想されます。

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

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

a と b の解答群

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

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

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

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

解答a － ア, b － ウ

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

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

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

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

具体的な値を入れるとプログラムがわかる練習問題｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

具体例からヒントを掴む練習問題｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

プログラムを分割するコツがわかる練習問題｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

手順をヒントにトレースする練習問題｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

トレースのテクニックが身につく練習問題｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

2進数を掛け算するプログラム | アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

ヒープを配列で実現するプログラム｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

ルールに従って検査文字（チェックディジット）を求めるプログラム｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

配列のマッチング（突合せ）を行うプログラム｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

2進数の知識が必要なプログラム｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

矢沢 久雄

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

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

主な著作物

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