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


2022-11-28 更新
info2022 年 11 月

科目 B 問題の新しい擬似言語に合わせて、プログラムを変更しました。
なお、本記事では過去問題を一部改変しています。

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

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

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

練習問題

問 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

swipe表やプログラムは横スクロールできます

［プログラム］

◯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

設問

　プログラム中のに入れる正しい答えを、解答群の中から選べ。

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] が等しくなく、かつ 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

  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 ― イ

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

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

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

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

label 関連タグ
アルゴリズムテクニック 具体的な値を想定科目 B
科目A試験は、
免除できます。 独習ゼミで科目A試験を1年間免除して、科目B試験だけに集中しましょう。
免除試験を受けた 74.9% の方が、
科目A免除資格を得ています。
詳しく見てみるplay_circle_filled
科目A免除試験 最大 2 回の
受験チャンス ！
info_outline
科目A免除試験 最大 2 回の
受験チャンス ！
詳しく見てみるplay_circle_filled
label これまでの『アルゴリズムとプログラミング問題を解くコツ』の連載一覧

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

update

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

update

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

update

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

update

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

update

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

update

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

update

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

update

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

update

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

update
label 著者

grade IPA認定
科目A免除制度対応
eラーニング

play_circle_filledYouTube でも学べる

guide_youtube

LINE 友だち登録で
「試験によく出る
情報セキュリティ用語集 Top 30 」をプレゼント！

人気記事

1

稼働率の計算方法がわかる｜かんたん計算問題

update 2021-02-09
2

基本情報でわかる 浮動小数点 「3つの情報で1つの数を表す仕組みを知れば、浮動小数点数がわかる」

update 2021-12-03
3

基本情報技術者試験 とは ～難易度や過去問、勉強法、勉強計画など疑問に答えます

update 2023-03-29
4

基本情報でわかる 論理演算 「真理値表を書けば、半加算器と全加算器の仕組みがわかる」

update 2021-12-16
5

基本情報でわかる IPアドレス と サブネットマスク

update 2021-12-02
6

略語でわかる MIPS の計算方法｜かんたん計算問題

update 2022-10-31
7

音声サンプリングの計算方法がわかる｜かんたん計算問題

update 2021-02-25
8

工数の計算方法がわかる｜かんたん計算問題

update 2021-02-09
9

ビットパターンの計算問題｜かんたん計算問題

update 2021-12-02
10

基本情報でわかる FIFO LFU LRU 「略語の意味がわかればわかる」

update 2021-12-02

人気のタグ

アルゴリズム 過去問演習 午前免除試験 午後問題の解説 勉強方法 午前問題 科目 B 午後プログラミング言語問題 試験講評 科目 A 新試験情報 情報セキュリティ 計算問題 午前問題と午後問題の違い Python 2進数 試験情報 テクニック 具体的な値を想定 試験ガイド 出題傾向 2019見直し 勉強時間 学習方法 データベース ネットワーク SQL 論理回路 公開鍵秘密鍵 IPアドレス オブジェクト指向