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


2020-09-08 更新

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

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

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

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

練習問題

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

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

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

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

[プログラム]

○整数型:MatchCounter(文字型:SourceText[], 整数型:Textlen,
                     文字型:Pattern[], 整数型:Patlen)
○整数型:Counter, i, j, k
○論理型:Matchflg
・Counter ← 0
・i ← 0
■a
| ・j ← i
| ・k ← 0
| ・Matchflg ← true
| ■ (k < Patlen) and (Matchflg = true)
| | ▲ SourceText[j] = Pattern[k]
| | | ・j ← j + 1
| | | ・k ← k + 1
| | +---
| | | ・Matchflg ← false
| | ▼
| ■
| ▲ k = Patlen
| | ・Counter ← Counter + 1
| ▼
| ・i ← i + 1
■
・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
a
|  ・j ← i
|  ・k ← 0
|  ・Matchflg ← true
|  ■ (k < Patlen) and (Matchflg = true)
|  | ▲ SourceText[j] = Pattern[k]
|  | | ・j ← j + 1
|  | | ・k ← k + 1
|  | +---
|  | | ・Matchflg ← false
|  | ▼
|  
|  ▲ k = Patlen
|  | ・Counter ← Counter + 1
|  
| ・i ← i + 1

・return Counter
1. 一致する部分文字列の出現回数を数える変数 Counter の値を 0 に初期化する。2. SourceText の比較開始位置を先頭から順に 1 文字ずつ後ろにずらしながら、(2.) その比較開始位置から始まる長さ 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 関連タグ
実は、午前試験を『免除』できます 独習ゼミで午前免除試験を受けた 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ラーニング

人気記事

人気のタグ