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


2020-09-08 更新

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

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

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

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

練習問題

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

 副プログラム Replace は、文字列を置換するプログラムである。 Replace には、文字型配列の引数 A[], S[], D[], B[] があり、 A[] を先頭からコピーして B[] に格納する( B[] は十分に大きいとする)。このとき、 A[] 中に S[] と一致する文字列を見つけるたびに、それを D[] の内容に置き換える。このプログラムで扱う文字型配列の添字は 0 から始まり、配列の末尾には定数 EOS が格納されている。

図 Replace の実行例
添字 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:問題に示された具体例でプログラムの機能を理解する

問題文の説明を読んだだけでは、プログラムの機能を理解するのが困難な場合があります。この問題では、理解を助けるために、具体例が図示されています。

以下のように、問題文の説明と具体例の図を対応させれば、プログラムの機能を理解できるでしょう。

 副プログラム Replace は、文字列を置換するプログラムである。 Replace には、文字型配列の引数 A[], S[], D[], B[] があり、 A[] を先頭からコピーして B[] に格納する( B[] は十分に大きいとする)。このとき、 A[] 中に S[] と一致する文字列を見つけるたびに、 それを D[] の内容に置き換える。このプログラムで扱う文字型配列の添字は 0 から始まり、配列の末尾には定数 EOS が格納されている。

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% の方が、
午前試験を免除しています。
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ラーニング

人気記事

人気のタグ