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

矢沢 久雄
2022-11-28 更新

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

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

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

練習問題

◯Replace(文字型の配列: A, 文字型の配列: S, 文字型の配列: D, 文字型の配列: B)
  整数型: Aidx, Sidx, Didx, Bidx, Idx
  Aidx ← 0
  Bidx ← 0

  while (A[Aidx] が EOS と等しくない)
    if (A[Aidx] と S[0] が等しい)
      Idx ← Aidx
      a

      do
        Sidx ←　Sidx + 1
        Aidx ←　Aidx + 1
      while (bと A[Aidx] がどちらとも EOS と等しくない)

      if (c)
        Didx ← 0

        while (D[Didx] が EOS と等しくない)
          B[Bidx] ← D[Didx]
          Didx ← Didx + 1
          Bidx ← Bidx + 1
        endwhile
      else
        d
        Aidx ← Idx + 1
        Bidx ← Bidx + 1
      endif

      B[Bidx] ← A[Aidx]
      Aidx ← Aidx + 1
      Bidx ← Bidx + 1
    endif
  endwhile

  B[Bidx] ← EOS

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

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

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

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

expand_more

ポイント2: プログラムを区切ってコメントを書き込む

プログラムの機能（概要だけで OK です）を理解できたら、プログラムを区切って、それぞれの区切りごとに、そこで何をしているかをコメントとして書き込んでみましょう（わかる範囲だけで OK です）。

以下に、区切りとコメントの例を示します。 ここでは、区切りの線とコメントを赤色で示していますが、試験当日は、問題用紙に鉛筆で書き込んでください。 こうすることで、プログラムの内容が、とても見やすくなるでしょう。

◯Replace(文字型の配列: A, 文字型の配列: S, 文字型の配列: D, 文字型の配列: B)
  整数型: Aidx, Sidx, Didx, Bidx, Idx
  Aidx ← 0
  Bidx ← 0

  while (A[Aidx] が EOS と等しくない)
  

    if (A[Aidx] と S[0] が等しい)     A[Aidx] と S[0] が等しい場合の処理
      Idx ← Aidx                      Idx に Aidx の値を保存する
      a

      do                              A [] と S[] が一致するかどうか繰り返しチェックする
        Sidx ←　Sidx + 1
        Aidx ←　Aidx + 1
      while (bと A[Aidx] がどちらとも EOS と等しくない)
      

      if (c)               A[] と S[] が一致した場合は、
        Didx ← 0                      B[] に D[] を格納する

        while (D[Didx] が EOS と等しくない)
          B[Bidx] ← D[Didx]
          Didx ← Didx + 1
          Bidx ← Bidx + 1
        endwhile
      else
        

        d                  A[Aidx] と S[0] が等しかったが、
        Aidx ← Idx + 1                A[] と S[] が一致しなかった場合の処理
        Bidx ← Bidx + 1
      endif
      
      

      B[Bidx] ← A[Aidx]               A[Aidx] と S[0] が等しくない場合は、
      Aidx ← Aidx + 1                 B[] に A[] を格納する
      Bidx ← Bidx + 1
    endif
  endwhile
  


  B[Bidx] ← EOS

ポイント3: 具体的な場面を想定して穴埋めを行う

プログラムを区切ってコメントを書けたら、穴埋めのある区切りごとに、具体的な場面を想定してみましょう。

まず、
A[1], A[2] の “a”, “b” が、
S[0], S[1] の “a”, “b” に一致する
場面を想定してみます。

これに関わるのは、空欄 a, 空欄 b, 空欄 c がある区切りです。 空欄 a と空欄 b がある区切りでは、 A[] と S[] が一致するかどうかをチェックしています。

  while (A[Aidx] が EOS と等しくない)
    if (A[Aidx] と S[0] が等しい)     A[Aidx] と S[0] が等しい場合の処理
      Idx ← Aidx                      Idx に Aidx の値を保存する
      a

      do                              A [] と S[] が一致するかどうか繰り返しチェックする
        Sidx ←　Sidx + 1
        Aidx ←　Aidx + 1
      while (bと A[Aidx] がどちらとも EOS と等しくない)

if (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 （選択肢オ）です。

  while (bと A[Aidx] がどちらとも EOS と等しくない)

の部分では、 A[Aidx] と S[Sidx] が等しい限りチェックが繰り返されます。 したがって、空欄 b は A[Aidx] = S[Sidx] （選択肢イ）です。

ポイント4: 選択肢を空欄に当てはめて考える

同じ場面を想定したまま、空欄 d がある区切りを見てみましょう。

ここでは、空欄 c の条件が真なら B[] に D[]を 格納する処理を行っています。

if (c)               A[] と S[] が一致した場合は、
  Didx ← 0                      B[] に D[] を格納する
  while (D[Didx] が EOS と等しくない)
    B[Bidx] ← D[Didx]
    Didx ← Didx + 1
    Bidx ← Bidx + 1
  endwhile

したがって、空欄 c は、 A[] と S[] が一致したことを判断する条件です。 どのような条件でしょうか？

もしも、プログラムを見ても処理が思い浮かばないなら、選択肢を見てください。

空欄 c の選択肢は、以下に示したア～カがあります。 これらの中に、 A[] と S[] が一致したことを判断できる条件があるのです。

b, c に関する解答群

ア

A[Aidx] と EOS が等しくない

イ

A[Aidx] と S[Sidx] が等しい

ウ

A[Aidx] と S[Sidx] が等しくない

エ

A[Aidx] と S[Sidx] が等しくなく、かつ 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 のときの

if (A[Aidx] が S[0] と等しい)

というチェックが真だったのですから、 A[0] の “a” が入っています。

したがって、空欄 d は、 B[Bidx] ← S[0]（選択肢イ）です。

このように、同様の処理をしている選択肢がある場合は、最初に「これかな？」と思っても、そこで早合点せずに、他の選択肢も「もしかすると、これかも？」と確認するようにしてください。 選択肢は、大きなヒントなのですから、大いに活用しましょう。

解答a － オ, b － イ, c － オ, d ― イ

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

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

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

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

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

update 2022-11-28

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

update 2022-11-28

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

update 2022-11-28

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

update 2022-11-28

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

update 2022-11-28

2進数を掛け算するプログラム | アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

ヒープを配列で実現するプログラム｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

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

update 2022-11-28

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

update 2022-11-28

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

update 2022-11-28

矢沢 久雄

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

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

主な著作物

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