具体例からヒントを掴む練習問題|アルゴリズム問題を解くコツ

この連載では、基本情報技術者試験で、多くの受験者が苦手意識を持っている午後試験の「アルゴリズム穴埋め問題」に的を絞って、正解を見出すポイントを詳しく説明します。
苦手を克服するには、短いプログラムを何度も練習して、穴埋めに慣れることが重要です。
そのために、実際の試験問題の一部をアレンジした練習問題を作りました。とても短い問題ですので、気軽に取り組んでください。
もくじ
練習問題
副プログラム Replace は、文字列を置換するプログラムである。 Replace には、文字型配列の引数 A[], S[], D[], B[] があり、 A[] を先頭からコピーして B[] に格納する( B[] は十分に大きいとする)。このとき、 A[] 中に S[] と一致する文字列を見つけるたびに、それを D[] の内容に置き換える。このプログラムで扱う文字型配列の添字は 0 から始まり、配列の末尾には定数 EOS が格納されている。
添字 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
A[] | “a” | “a” | “b” | “c” | “a” | “b” | “b” | EOS | ||
S[] | “a” | “b” | EOS | |||||||
D[] | “A” | “B” | “C” | EOS | ||||||
B[] | “a” | “A” | “B” | “C” | “c” | “A” | “B” | “C” | “b” | EOS |
[プログラム]
○Replace(文字型:A[], 文字型:S[], 文字型:D[], 文字型:B[]) ○整数型:Aidx, Sidx, Didx, Bidx, Idx ・Aidx ← 0 ・Bidx ← 0 ■ A[Aidx] ≠ EOS | ▲ A[Aidx] = S[0] | | ・Idx ← Aidx | | ・a | | ■ | | | ・Sidx ← Sidx + 1 | | | ・Aidx ← Aidx + 1 | | ■ b and A[Aidx] ≠ EOS | | ▲ c | | | ・Didx ← 0 | | | ■ D[Didx] ≠ EOS | | | | ・B[Bidx] ← D[Didx] | | | | ・Didx ← Didx + 1 | | | | ・Bidx ← Bidx + 1 | | | ■ | | +--- | | | ・d | | | ・Aidx ← Idx + 1 | | | ・Bidx ← Bidx + 1 | | ▼ | +--- | | ・B[Bidx] ← A[Aidx] | | ・Aidx ← Aidx + 1 | | ・Bidx ← Bidx + 1 | ▼ ■ ・B[Bidx] ← EOS
設問 プログラム中のに入れる正しい答えを、解答群の中から選べ。
a, d に関する解答群
- ア
- B[Bidx] ← A[Aidx]
- イ
- B[Bidx] ← S[0]
- ウ
- Idx ← 0
- エ
- Idx ← 1
- オ
- Sidx ← 0
- カ
- Sidx ← 1
b, c に関する解答群
- ア
- A[Aidx] ≠ EOS
- イ
- A[Aidx] = S[Sidx]
- ウ
- A[Aidx] ≠ S[Sidx]
- エ
- A[Aidx] ≠ S[Sidx] and S[Sidx] ≠ EOS
- オ
- S[Sidx] = EOS
- カ
- S[Sidx] ≠ EOS
ポイント1:問題に示された具体例でプログラムの機能を理解する
問題文の説明を読んだだけでは、プログラムの機能を理解するのが困難な場合があります。この問題では、理解を助けるために、具体例が図示されています。
以下のように、問題文の説明と具体例の図を対応させれば、プログラムの機能を理解できるでしょう。
expand_more
添字 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
A[] | “a” | “a” | “b” | “c” | “a” | “b” | “b” | EOS | ||
S[] | “a” | “b” | EOS | |||||||
D[] | “A” | “B” | “C” | EOS | ||||||
B[] | “a” | “A” | “B” | “C” | “c” | “A” | “B” | “C” | “b” | EOS |
ポイント2:プログラムを区切ってコメントを書き込む
プログラムの機能(概要だけで OK です)を理解できたら、プログラムを区切って、それぞれの区切りごとに、そこで何をしているかをコメントとして書き込んでみましょう(わかる範囲だけで OK です)。
以下に、区切りとコメントの例を示します。ここでは、区切りの線とコメントを赤色で示していますが、試験当日は、問題用紙に鉛筆で書き込んでください。こうすることで、プログラムの内容が、とても見やすくなるでしょう。
○Replace(文字型:A[], 文字型:S[], 文字型:D[], 文字型:B[]) ○整数型:Aidx, Sidx, Didx, Bidx, Idx ・Aidx ← 0 ・Bidx ← 0 ■ A[Aidx] ≠ EOS | ▲ A[Aidx] = S[0] A[Aidx] と S[0] が等しい場合の処理 | | ・Idx ← Aidx Idx に Aidx の値を保存する | | ・a | | ■ A [] と S[] が一致するかどうか繰り返しチェックする | | | ・Sidx ← Sidx + 1 | | | ・Aidx ← Aidx + 1 | | ■ b and A[Aidx] ≠ EOS | | ▲ c A[] と S[] が一致した場合は、 | | | ・Didx ← 0 B[] に D[] を格納する | | | ■ D[Didx] ≠ EOS | | | | ・B[Bidx] ← D[Didx] | | | | ・Didx ← Didx + 1 | | | | ・Bidx ← Bidx + 1 | | | ■ | | +--- | | | ・d A[Aidx] と S[0] が等しかったが、 | | | ・Aidx ← Idx + 1 A[] と S[] が一致しなかった場合の処理 | | | ・Bidx ← Bidx + 1 | | ▼ | +--- | | ・B[Bidx] ← A[Aidx] A[Aidx] と S[0] が等しくない場合は、 | | ・Aidx ← Aidx + 1 B[] に A[] を格納する | | ・Bidx ← Bidx + 1 | ▼ ■ ・B[Bidx] ← EOS
ポイント3:具体的な場面を想定して穴埋めを行う
プログラムを区切ってコメントを書けたら、穴埋めのある区切りごとに、具体的な場面を想定してみましょう。
まず、
A[1], A[2] の “a”, “b” が、
S[0], S[1] の “a”, “b” に一致する
場面を想定してみます。
これに関わるのは、空欄 a, 空欄 b, 空欄 c がある区切りです。空欄 a と空欄 b がある区切りでは、 A[] と S[] が一致するかどうかをチェックしています。
| ▲ A[Aidx] = S[0] A[Aidx] と S[0] が等しい場合の処理 | | ・Idx ← Aidx Idx に Aidx の値を保存する | | ・a | | ■ A [] と S[] が一致するかどうか繰り返しチェックする | | | ・Sidx ← Sidx + 1 | | | ・Aidx ← Aidx + 1 | | ■ b and A[Aidx] ≠ EOS
▲ A[Aidx] = S[0]
の部分では、 Aidx が 1 であり、 A[1] と S[0] が等しいことをチェックします。
その後にある繰り返し処理で、 Sidx と Aidx の値を 1 ずつ増やします。 Sidx は、その名前から S[] の添字だとわかります。
A[1] と S[0] が等しいことをチェックした後は、 A[2] と S[1] が等しいことをチェックします。
したがって、空欄 a は S[Sidx] のSidx を 0 に設定する処理であり、Sidx ← 0 (選択肢オ)です。
| | ■ b and A[Aidx] ≠ EOS
の部分では、 A[Aidx] と S[Sidx] が等しい限りチェックが繰り返されます。したがって、空欄 b は A[Aidx] = S[Sidx] (選択肢イ)です。
ポイント4:選択肢を空欄に当てはめて考える
同じ場面を想定したまま、空欄dがある区切りを見てみましょう。
ここでは、空欄 c の条件が真なら B[] に D[]を 格納する処理を行っています。
| | ▲ c A[] と S[] が一致した場合は、 | | | ・Didx ← 0 B[] に D[] を格納する | | | ■ D[Didx] ≠ EOS | | | | ・B[Bidx] ← D[Didx] | | | | ・Didx ← Didx + 1 | | | | ・Bidx ← Bidx + 1 | | | ■ | | +---
したがって、空欄 c は、 A[] と S[] が一致したことを判断する条件です。どのような条件でしょうか?
もしも、プログラムを見ても処理が思い浮かばないなら、選択肢を見てください。
空欄 c の選択肢は、以下に示したア~カがあります。これらの中に、 A[] と S[] が一致したことを判断できる条件があるのです。
b, c に関する解答群
- ア
- A[Aidx] ≠ EOS
- イ
- A[Aidx] = S[Sidx]
- ウ
- A[Aidx] ≠ S[Sidx]
- エ
- A[Aidx] ≠ S[Sidx] and S[Sidx] ≠ EOS
- オ
- S[Sidx] = EOS
- カ
- S[Sidx] ≠ EOS
これらの選択肢を 1 つずつ空欄 c に当てはめていくと、「あっ、そうか!」と気付くでしょう。
ここで想定している
A[1], A[2] の “a”, “b” が、
S[0], S[1] の “a”, “b” に一致する
場面では、 A[Aidx] = S[Sidx] という条件が真である限りチェックが繰り返され、 S[Sidx] が EOS になったときに、それまでの文字がすべて等しいことが確認され、繰り返しが終わります。
したがって、 A[] と S[] が一致したことを判断できる条件は、 S[Sidx] = EOS(選択肢オ)です。
ポイント5:選択肢を見て「待てよ!」と思いとどまる
最後は、空欄 d がある区切りです。
ここでは、 A[Aidx] と S[0] が等しかったが、 A[] と S[] が一致しなかった場合の処理が行われます。
これは、これまでに想定した場面とは異なるので、
A[0] の “a” と S[0] の “a” が等しかったが、
A[1] の “a” と S[1] の “b” が等しくなかった
場面を想定してみましょう。
| | | ・d A[Aidx] と S[0] が等しかったが、 | | | ・Aidx ← Idx + 1 A[] と S[] が一致しなかった場合の処理 | | | ・Bidx ← Bidx + 1 | | ▼ | +---
この場面では、 B[] に A[0] の “a” を格納します。選択肢を見てみましょう。
a, d に関する解答群
- ア
- B[Bidx] ← A[Aidx]
- イ
- B[Bidx] ← S[0]
- ウ
- Idx ← 0
- エ
- Idx ← 1
- オ
- Sidx ← 0
- カ
- Sidx ← 1
これらの選択肢を見ると、「 B[] に A[0] を格納するのだから、選択肢アの B[Bidx] ← A[Aidx] だろう!」と思うでしょう。
しかし、ここで「待てよ!」と思いとどまってください。
B[] に格納する処理として、もう 1 つ、選択肢イの B[Bidx] ← S[0] があります。
A[Aidx] は、 A[] と S[] が一致するかどうかのチェックで Aidx に 1 を加えているので 0 ではなくなっています。
S[0] には、 Aidx が 0 のときの
▲ A[Aidx] = S[0]
というチェックが真だったのですから、 A[0] の “a” が入っています。
したがって、空欄 d は、B[Bidx] ← S[0](選択肢イ)です。
このように、同様の処理をしている選択肢がある場合は、最初に「これかな?」と思っても、そこで早合点せずに、他の選択肢も「もしかすると、これかも?」と確認するようにしてください。選択肢は、大きなヒントなのですから、大いに活用しましょう。
解答a - オ, b - イ, c - オ, d ― イ
「習うより慣れろ」ということわざがあります。アルゴリズム穴埋め問題の克服に関しては、正にその通りでしょう。
この連載では、これからも短い練習問題を掲載していきますので、穴埋めに慣れることを目指してください。
正解を見出すポイントとして、同じことが示されることもあると思いますが、それは、多くの問題に共通したポイントがあるからです。
それでは、またお会いしましょう!
label 関連タグ免除試験を受けた 86% の方が、 1 年間の午前免除資格を得ています。

具体的な値を入れるとプログラムがわかる練習問題|アルゴリズム問題を解くコツ
update
具体例からヒントを掴む練習問題|アルゴリズム問題を解くコツ
update
プログラムを分割するコツがわかる練習問題|アルゴリズム問題を解くコツ
update
手順をヒントにトレースする練習問題|アルゴリズム問題を解くコツ
update
トレースのテクニックが身につく練習問題|アルゴリズム問題を解くコツ
update
2進数を掛け算するプログラム
update
ヒープを配列で実現するプログラム
update
ルールに従って検査文字(チェックディジット)を求めるプログラム|アルゴリズム問題を解くコツ
update
配列のマッチング(突合せ)を行うプログラム|アルゴリズム問題を解くコツ
update
2進数の知識が必要なプログラム|アルゴリズム問題を解くコツ
update
『プログラムはなぜ動くのか』(日経BP)が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”
大手電気メーカーでPCの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識0ベースのITエンジニアや一般書店フェアなどの一般的なPCユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。
主な著作物
- 「プログラムはなぜ動くのか」(日経BP)
- 「コンピュータはなぜ動くのか」(日経BP)
- 「出るとこだけ! 基本情報技術者」 (翔泳社)
- 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」(翔泳社)
- 「ifとelseの思考術」(ソフトバンククリエイティブ) など多数