文字列の出現回数を数えるプログラム｜アルゴリズムとプログラミング問題を解くコツ


2022-11-28 更新
info2022 年 11 月

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

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

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

そのために、旧制度の午後試験のアルゴリズム過去問題の一部をアレンジした練習問題を作りました。とても短い問題ですので、気軽に取り組んでください。

練習問題

問 2 (平成 20 年度 春期 午後）を一部改変

　関数 MatchCounter は、長さが Textlen の文字列 SourceText の中で、長さが Patlen の文字列 Pattern と一致する部分文字列の出現回数を、以下の手順で数える。

  1. 一致する部分文字列の出現回数を数える変数 Counter の値を 0 に初期化する。
  2. SourceText の比較開始位置を先頭から順に 1 文字ずつ後ろにずらしながら、その比較開始位置から始まる長さ Patlen の文字列と Pattern が一致するかどうかを調べ、一致したら出現回数 Counter の値に 1 を加算する。
  3. Counter の値を返す。

　ここで、 0 < Patlen ≦ Textlen であり、配列の添字は 0 から始まる。プログラム中のaに入る正しい答えを、解答群の中から選べ。

［プログラム］

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

◯整数型: MatchCounter(文字型の配列: SourceText, 整数型: Textlen,
                     文字型の配列: Pattern, 整数型: Patlen)
  整数型: Counter, i, j, k
  論理型: Matchflg

  Counter ← 0
  i ← 0

  while (a)
    j ← i
    k ← 0
    Matchflg ← true

    while (k が Patlen より小さく かつ Matchflg が true)
      if ( SourceText[j] と Pattern[k] が等しい)
        j ← j + 1
        k ← k + 1
      else
        Matchflg ← false
      endif
    endwhile

    if (k が Patlen と等しい)
      Counter ← Counter + 1
    endif

    i ← i + 1
  endwhile

  return Counter

a の解答群

ア
i と Patlen の和が Textlen 以下
イ
i と Patlen の和が Textlen より小さい
ウ
i と Textlen の和が Patlen 以下
エ
i と Textlen の和が Patlen より小さい

ポイント1: わかりやすい配列の絵を書いて問題のイメージをつかむ

「こういう配列の繰り返し処理の問題が、とにかく苦手なんです！」という人は、 わかりやすい具体例を想定して、配列の絵を書いてみる とよいでしょう。

問題に示されたプログラムは、汎用的なものであり、様々な配列を処理できますが、汎用的なままではイメージをつかめません。以下のように、具体的な配列の絵を書けば、イメージをつかめるはずです。

配列の絵を書いたことで、この問題は、絵に示された 10 文字の文字列 SourceText の中から、
[A][B][C]
という 3 文字の文字列 Pattern と一致する部分文字列の出現回数を数えるものとなり、その結果は 2 になります。

このように具体的な想定で問題に取り組めば、苦手意識が解消するでしょう。

ポイント2: 問題文にある説明や変数名から変数の役割を知る

プログラムは、登場人物がいてストーリーがある TV ドラマに似ています。プログラムでは、 変数が登場人物 に相当し、 処理の手順がストーリー に相当します。

登場人物の役割がわからなければ TV ドラマのストーリーがわからないように、変数の役割がわからなければプログラムの処理の手順はわかりません。

したがって、プログラムの処理を見る前に、変数の役割を知っておく 必要があります（プログラムを見ないと役割がわからない変数もありますので、可能な範囲で OK です）。

 

変数の役割は、問題文にある説明や、変数名などからわかります。

このプログラムに登場する変数と役割を以下にまとめて示します。

SourceText
探索対象の文字列（問題文の説明からわかる）
Textlen
SourceText の長さ（問題文の説明からわかる）
Pattern
探索する部分文字列（問題文の説明からわかる）
Patlen
Pattern の長さ（問題文の説明からわかる）
Counter
部分文字列の出現回数（問題文の手順の説明からわかる）
Matchflg
一致したことを表すフラグ（変数名からわかる）
i, j, k
配列の添字（プログラムの慣例としてわかる）

SourceText 、Textlen 、Pattern 、Patlen の役割は、問題文の説明からわかります。

Counter の役割は、問題文の手順の説明からわかります。
Matchflg の役割は、変数名（ Match = 一致、 flg = フラグ）からわかります。
i, j, k の役割は、プログラムの慣例としてわかります。配列の添字には、慣例として i を使い、さらに添字に関わる複数の変数が必要な場合は、アルファベットで i の次の j や、さらにその次の k などが使われます（ i, j, k が何を指す添字なのかは、プログラムを見たときにわかります）。

ポイント3: 問題文に示された手順とプログラムを対応付ける

試験問題に、処理の手順が示されていることがよくあります。この問題でも、 1. 2. 3. という番号を付けて、処理の手順が示されています。

この場合には、 それぞれの手順と照らし合わせながらプログラムを読んで行く とよいでしょう。

やみくもにプログラムを読むより、ずっとわかりやすいはずです。「この手順に該当するから、この穴埋めではこういう処理をするはずだ」と気付くこともあります。

 

以下は、処理の手順をプログラムに対応付けたものです。実際の試験では、このように丁寧な書き込みをしている時間はないと思いますので、メモ書き程度でやってください。

Counter ← 0
i ← 0

while (a)
  j ← i
  k ← 0
  Matchflg ← true

    while (k が Patlen より小さく かつ Matchflg が true)
      if ( SourceText[j] と Pattern[k] が等しい)
        j ← j + 1
        k ← k + 1
      else
        Matchflg ← false
      endif
    endwhile

    if (k が Patlen と等しい)
      Counter ← Counter + 1
    endif

    i ← i + 1
endwhile
return Counter1. 一致する部分文字列の出現回数を数える変数 Counter の値を 0 に初期化する。2. SourceText の比較開始位置を先頭から順に 1 文字ずつ後ろにずらしながら、(1.) その比較開始位置から始まる長さ Patlen の文字列と Pattern が一致するかどうかを調べ、(2.) 一致したら出現回数 Counter の値に 1 を加算する。3. Counter の値を返す。

穴埋めをやってみよう

それでは、穴埋めをやってみましょう。

基本情報技術者試験の問題は、すべて選択問題なので、解答群に示された選択肢をヒントにして考えてください（これも大事なポイントです）。もちろん、これまでに示した具体例の絵や、手順とプログラムの対応付けも、大いに活用してください。

aは、

2. SourceText の比較開始位置を先頭から順に 1 文字ずつ後ろにずらしながら

という手順に該当する部分であり、 擬似言語の表現から繰り返しの条件を指定するものであることがわかります。

a に関する解答群を見ると、この繰り返し処理の条件が、i, Textlen, Patlen という変数を使って示されています。さあ、どれでしょうか？

a に関する解答群

ア
i と Patlen の和が Textlen 以下
イ
i と Patlen の和が Textlen より小さい
ウ
i と Textlen の和が Patlen 以下
エ
i と Textlen の和が Patlen より小さい

ここで役立つのが具体例の絵です。

Textlen から Patlen を探索すると、最終的に以下の位置まで Patlen をずらすことになります。

i は、

i ← 0

で初期化してることから、比較の開始位置であり、配列の添字が 0 から始まるので、ここでは 7 です。

この具体例の絵から、 7 + 3 = 10 まで処理を行ってよいことがわかります。
これは、 7 + 3 の部分が 10 以下なら処理を繰り返してよいということです。

7 は i で、 3 は Patlen で、 10 は Textlen なので、この条件は、

i と Patlen の和が Textlen 以下

です。

したがって、選択肢アが正解です。できましたね！

 

解答ア

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

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

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

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

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

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

update 2021-12-03
2

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

update 2021-02-09
3

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

update 2021-12-16
4

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

update 2021-02-25
5

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

update 2021-12-02
6

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

update 2023-03-29
7

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

update 2022-10-31
8

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

update 2021-12-02
9

基本情報技術者試験のシラバス改定｜Ver9.0の概要

update 2024-02-07
10

IT初心者のための 論理回路 入門 ～ 基本情報ではじめるコンピュータ科学の基礎理論（3）

update 2023-07-24

人気のタグ

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