手順をヒントにトレースする練習問題｜アルゴリズムとプログラミング問題を解くコツ
2022-11-28 更新
科目 B 問題の新しい擬似言語に合わせて、プログラムを変更しました。
なお、本記事では過去問題を一部改変しています。
この連載では、基本情報技術者試験で、多くの受験者が苦手意識を持っている科目 B 試験 アルゴリズムとプログラミング分野の「アルゴリズム穴埋め問題」に的を絞って、正解を見出すポイントを詳しく説明します。
苦手を克服するには、短いプログラムを何度も練習して、穴埋めに慣れることが重要です。
そのために、実際の試験問題の一部をアレンジした練習問題を作りました。とても短い問題ですので、気軽に取り組んでください。
もくじ
練習問題
手続 InsertSort は、引数で与えられた配列 A[] を、挿入ソートで昇順に整列する。配列 A[] の添字は 0 から始まり、要素数は引数 N で与えられる。挿入ソートの手順は、次のとおりである。
- まず、 A[0] と A[1] を整列し、次に A[0] から A[2] までを整列し、その次に A[0] から A[3] までというように、整列する区間の要素を一つずつ増やしていき、最終的に A[0] から A[N – 1] までを整列する。
- 整列する区間が A[0] から A[M]（ 1 ≦ M < N ）までのとき、 A[M] を既に整列された列 A[0] , more_horiz, A[M – 1] 中の適切な位置に挿入する。その手順は次のとおりである。
- A[M] の値を、作業領域 Tmp に格納する。
- A[M – 1] から A[0] に向かって Tmp と比較し、 Tmp よりも大きな値を順次隣（要素番号の大きい方）に移動する。
- b. で最後に移動した値の入っていた配列要素に Tmp の値を格納する。 b. で移動がなかった場合には A[M] に格納する。
［プログラム］
◯InsertSort(整数型の配列: A, 整数型: N)
整数型: Idx1, Idx2, Tmp
論理型: Loop
for (Idx1 を 1 から N より小さい間 1 つずつ増やす)
Tmp ← A[Idx1]
Idx2 ← a
Loop ← true
while (Idx2 が 0 以上でかつ Loop が true)
if (A[Idx2] が Tmp より大きい)
b
Idx2 ← Idx2 - 1
else
Loop ← false
endif
endwhile
A[Idx2 + 1] ← Tmp
endfor
設問 プログラム中のに入れる正しい答えを、解答群の中から選べ。
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] までを整列する。 */ for (Idx1 を 1 から 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 while (Idx2 が 0 以上でかつ Loop が true) /* Tmp と比較し、Tmp よりも大きな値を */ if (A[Idx2] が Tmp より大きい) /* 順次隣（要素番号の大きい方）に移動する。 */ b Idx2 ← Idx2 - 1 else Loop ← false endif endwhile /* c. b. で最後に移動した値の入っていた配列要素に Tmp の値を格納する。 */ /* b. で移動がなかった場合には A[M] に格納する。 */ A[Idx2 + 1] ← Tmp endfor
ポイント2: 手順の説明とプログラムを対応付ける（その2）
手順の説明とプログラムを対応付けたことで、以下がわかります。
/* a. A[M] の値を、作業領域 Tmp に格納する。 */
Tmp ← A[Idx1]
手順の説明で M と呼んでいる変数は、プログラムでは Idx1 です。
/* b. A[M - 1] から A[0] に向かって */ Idx2 ← a Loop ← true while (Idx2 が 0 以上でかつ Loop が true)
A[M – 1] から A[0] に向かって
を A[Idx2] で示すので、空欄 a で Idx2 に設定する初期値は M – 1 です。説明の M がプログラムでは Idx1 なので、空欄 a は Idx1 – 1 であり、選択肢ウが正解です。
ポイント3: 手順の説明とプログラムを対応付ける（その3）
空欄 b がある分岐では、
/* Tmp と比較し、Tmp よりも大きな値を */ if (A[Idx2] が Tmp より大きい) /* 順次隣（要素番号の大きい方）に移動する。 */ b Idx2 ← Idx2 - 1
Tmp と比較し、 Tmp よりも大きな値を順次隣（要素番号の大きい方）に移動する。
という処理を行っています。
A[Idx2] が Tmp より大きい
なのですから、 Tmp より大きな値は A[Idx2] であり、この値を順次隣（要素番号の大きい方）に移動するのですから、 A[Idx2 + 1] ← A[Idx2] が適切であり、選択肢ウが正解です。
解答a － ウ, b － ウ
「習うより慣れろ」ということわざがあります。アルゴリズム穴埋め問題の克服に関しては、正にその通りでしょう。
この連載では、これからも短い練習問題を掲載していきますので、穴埋めに慣れることを目指してください。
正解を見出すポイントとして、同じことが示されることもあると思いますが、それは、多くの問題に共通したポイントがあるからです。
それでは、またお会いしましょう！
label 関連タグ免除試験を受けた 74.9% の方が、科目A免除資格を得ています。
具体的な値を入れるとプログラムがわかる練習問題｜アルゴリズムとプログラミング問題を解くコツ
update
具体例からヒントを掴む練習問題｜アルゴリズムとプログラミング問題を解くコツ
update
プログラムを分割するコツがわかる練習問題｜アルゴリズムとプログラミング問題を解くコツ
update
手順をヒントにトレースする練習問題｜アルゴリズムとプログラミング問題を解くコツ
update
トレースのテクニックが身につく練習問題｜アルゴリズムとプログラミング問題を解くコツ
update
2進数を掛け算するプログラム | アルゴリズムとプログラミング問題を解くコツ
update
ヒープを配列で実現するプログラム｜アルゴリズムとプログラミング問題を解くコツ
update
ルールに従って検査文字（チェックディジット）を求めるプログラム｜アルゴリズムとプログラミング問題を解くコツ
update
配列のマッチング（突合せ）を行うプログラム｜アルゴリズムとプログラミング問題を解くコツ
update
2進数の知識が必要なプログラム｜アルゴリズムとプログラミング問題を解くコツ
update『プログラムはなぜ動くのか』（日経BP）が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”
大手電気メーカーでＰＣの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識０ベースのＩＴエンジニアや一般書店フェアなどの一般的なＰＣユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。
主な著作物
- 「プログラムはなぜ動くのか」（日経BP）
- 「コンピュータはなぜ動くのか」（日経BP）
- 「出るとこだけ! 基本情報技術者」 (翔泳社)
- 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」（翔泳社）
- 「ｉｆとｅｌｓｅの思考術」（ソフトバンククリエイティブ） など多数
