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

矢沢 久雄
2020-12-25 更新

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

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

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

練習問題

○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

ポイント1：問題に示された具体例でプログラムの機能を理解する

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

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

expand_more

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

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

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

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

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

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

update 2021-02-08

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

update 2020-12-25

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

update 2020-09-08

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

update 2020-09-08

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

update 2020-09-08

2進数を掛け算するプログラム

update 2022-05-06

ヒープを配列で実現するプログラム

update 2020-09-08

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

update 2020-09-08

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

update 2020-09-08

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

update 2021-01-08

矢沢 久雄

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

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

主な著作物

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