手順をヒントにトレースする練習問題|アルゴリズム問題を解くコツ


2020-09-08 更新

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

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

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

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

練習問題

info編集部注: スマートフォンでご覧の際は、アルゴリズムを横スクロールすると全文をご覧になれます
問 4 「挿入ソートで昇順に整列するプログラム」(平成 19 年度 春期 午後)を一部改変

 InsertSort 関数は、引数で与えられた配列 A[] を、挿入ソートで昇順に整列する。配列 A[] の添字は 0 から始まり、要素数は引数 N で与えられる。挿入ソートの手順は、次のとおりである。

  1. まず、 A[0] と A[1] を整列し、次に A[0] から A[2] までを整列し、その次に A[0] から A[3] までというように、整列する区間の要素を一つずつ増やしていき、最終的に A[0] から A[N – 1] までを整列する。
  2. 整列する区間が A[0] から A[M]( 1 ≦ M < N )までのとき、 A[M] を既に整列された列 A[0] , more_horiz, A[M – 1] 中の適切な位置に挿入する。その手順は次のとおりである。
    1. A[M] の値を、作業領域 Tmp に格納する。
    2. A[M – 1] から A[0] に向かって Tmp と比較し、 Tmp よりも大きな値を順次隣(要素番号の大きい方)に移動する。
    3. b. で最後に移動した値の入っていた配列要素に Tmp の値を格納する。 b. で移動がなかった場合には A[M] に格納する。

[プログラム]

○InsertSort(整数型:A[], 整数型:N)
○整数型:Idx1, Idx2, Tmp
○論理型:Loop
■ Idx1:1, Idx < N, 1
| ・Tmp ← A[Idx1]
| ・Idx2 ← a
| ・Loop ← true
| ■ Idx2 ≧ 0 and Loop = true
| | ▲ A[Idx2] > Tmp
| | | ・b
| | | ・Idx2 ← Idx2 - 1
| | +---
| | | ・Loop ← false
| | ▼
| ■
| ・A[Idx2 + 1] ← Tmp
■

設問 プログラム中のに入れる正しい答えを、解答群の中から選べ。

a に関する解答群
ア Idx1
イ Idx1 + 1
ウ Idx1 – 1
エ 1 – Idx1

b に関する解答群
ア A[Idx2] ← A[Idx2 + 1]
イ A[Idx2] ← A[Idx2 – 1]
ウ A[Idx2 + 1] ← A[Idx2]
エ A[Idx2 – 1] ← A[Idx2]

ポイント1:手順の説明とプログラムを対応付ける(その1)

この問題のように、問題文に手順が詳しく示されている場合は、手順の説明とプログラムを対応付けることで、空欄で行う処理がわかる場合がよくあります。

以下は、手順の説明とプログラムを対応付けた例です。ここでは、手順の説明を青色の文字でコメントとして追加しています。実際の試験では、これを頭の中でやってください。

図 手順の説明とプログラムを対応付けた例
[プログラム]

○InsertSort(整数型:A[], 整数型:N)
○整数型:Idx1, Idx2, Tmp
○論理型:Loop
/* 1. まず、 A[0] と A[1] を整列し、次に A[0] から A[2] までを整列し、*/
/* その次に A[0] から A[3] までというように、整列する区間の要素を一つ */
/* ずつ増やしていき、最終的に A[0] から A[N - 1] までを整列する。*/
■ Idx1:1, Idx < N, 1
| /* 2. 整列する区間が A[0] から A[M]( 1 ≦ M < N )までのとき、A[M] を */
| /* 既に整列された列 A[0], more_horiz, A[M - 1] 中の適切な位置に挿入する。*/
| /* その手順は次のとおりである。*/
| /*  a. A[M] の値を、作業領域 Tmp に格納する。*/
| ・Tmp ← A[Idx1]
| /*  b. A[M - 1] から A[0] に向かって*/
| ・Idx2 ← a
| ・Loop ← true
| ■ Idx2 ≧ 0 and Loop = true
| | /* Tmp と比較し、Tmp よりも大きな値を */
| | ▲ A[Idx2] > Tmp
| | | /* 順次隣(要素番号の大きい方)に移動する。*/
| | | ・b
| | | ・Idx2 ← Idx2 - 1
| | +---
| | | ・Loop ← false
| | ▼
| ■
| /* c. b. で最後に移動した値の入っていた配列要素に Tmp の値を格納する。*/
| /* b. で移動がなかった場合には A[M] に格納する。*/
| ・A[Idx2 + 1] ← Tmp
■

ポイント2:手順の説明とプログラムを対応付ける(その2)

手順の説明とプログラムを対応付けたことで、以下がわかります。

| /*  a. A[M] の値を、作業領域 Tmp に格納する。*/
| ・Tmp ← A[Idx1]

手順の説明で M と呼んでいる変数は、プログラムでは Idx1 です。

| /*  b. A[M - 1] から A[0] に向かって*/
| ・Idx2 ← a
| ・Loop ← true
| ■ Idx2 ≧ 0 and Loop = true

A[M – 1] から A[0] に向かって

を A[Idx2] で示すので、空欄 a で Idx2 に設定する初期値は M – 1 です。説明の M がプログラムでは Idx1 なので、空欄 a は Idx1 – 1 であり、選択肢ウが正解です。

ポイント3:手順の説明とプログラムを対応付ける(その3)

空欄 b がある分岐では、

Tmp と比較し、 Tmp よりも大きな値を順次隣(要素番号の大きい方)に移動する。

という処理を行っています。

| | /* Tmp と比較し、Tmp よりも大きな値を */
| | ▲ A[Idx2] > Tmp
| | | /* 順次隣(要素番号の大きい方)に移動する。*/
| | | ・b
| | | ・Idx2 ← Idx2 - 1

A[Idx2] > Tmp なのですから、 Tmp より大きな値は A[Idx2] であり、この値を順次隣(要素番号の大きい方)に移動するのですから、 A[Idx2 + 1] ← A[Idx2] が適切であり、選択肢ウが正解です。

 

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

人気記事

人気のタグ