【基本情報午後】トレースによるアルゴリズムの解き方

アルゴリズムってどうやって解くのかわからない

ループが多いと頭がこんがらがっちゃう

こんな方に向けてトレースという方法を用いたアルゴリズムの説き方を解説します。

本記事の内容

トレースは慣れるまで何問か解く必要がありますが、

慣れてコツを掴めば、地道ではありますが着実に点を取れるようになります。

私も初めは全く理解できませんでしたが、コツを掴むと点数が取りやすくなり、

アルゴリズムが得意分野になりました！

トレースの概要

いきなり出てきたけどトレースってどんな方法なのか、解説していきます。

トレースの意味とは

そもそもトレース（trace）とは、直訳で「なぞる」「追跡する」という意味があります。

ＩＴの分野では「プログラムの実行過程を追跡し調査する」という意味があるようです。

この意味のように、これから紹介するトレースの方法は、プログラムの実行過程を表に書き起こし、変数を追跡する方法です。

トレースによって何ができるようになるのか

アルゴリズム問題で多く出される問題は、

プログラムのある時点で変数の値がどうなっているかという種類の問題です。

このような問題を解くには、

処理が進むにつれてコロコロ変わっていく変数の値を正確に追跡する必要がありますが、

これが、アルゴリズムを解くうえで混乱しやすいポイントですよね。

今回紹介するトレースは、プログラムを進めながら変数を表にまとめていくため、

混乱しやすい変数の追跡を正確に行うことができます。

トレースのやり方

では実際の試験問題のプログラムをトレースしてみましょう。

出典：平成２７年度秋期 基本情報技術者試験 午後 問８

※穴埋め問題のところは正解を入れています（四角で囲われたところ）

はじめにプログラムの引数となる値を確認しましょう。

設問の文を先に見て、引数になる値が書かれていないか確認します。

今回は以下の値が書かれていたので、これをプログラムに当てはめていきます。

• Text[] = ABCXBBACABACADEC
• TextLen = 16
• Pat[] = ABAC
• PatLen = 4

１つめのループ

ここの処理ではSkip[1]～[26]すべてにPatLenを代入しているだけなので、

特に表に書き起こす作業は必要ないですね。

PatLenは設問にあった引数なので、Skipはすべて4と把握しておくだけで大丈夫です。

２つめのループ

1周目Ｉ=１からスタートします。

Ｉ=１のとき、Pat[1] = A、Index(A) = 1なので、

Skip[1] = 3

1周目終わり

2周目Ｉ=２

Ｉ=２のとき、Pat[2] = B、Index(B) = 2なので、

Skip[2] = 2

2周目終わり

3周目も同様に処理すると

これでループが終了しました。

３つめのループ

トレースの前にαとβが気になりますね。

先に設問を見て、どんな問題なのか見ておきましょう。

設問を見ると、αとβがそれぞれ何回実行されたか、という問題でした。

αとβの実行回数もカウントしていきましょう。

（２つめのループのγはトレースに関係ない問題だったので無視しました）

また、今回はループが２つあります。

この解説の中で、一つ目の大きいループをループ①、

ループ①内のループをループ②とします。

はじめにPLastにPatLenが代入されていて、PLast = 4なので、

ループ①の条件が真となり、ループ①に入ります。

ループ②の前までいくと

Text[PText] = X

Pat[PPat] = C

ループ②の条件は偽なのでとばす

２周目

Text[PText] = X

Pat[PPat] = C

ループ②の条件が真なので、ループ②に入る

PPat = 1ではないので、とばす

ループ②を３周期まで進めると

Text[PText] = B

Pat[PPat] = A

となるためループ②の４周期目には入らず抜ける

ループ①の３周期目も同様に進めると

ループ②の４周期目で

Text[PText] = A

Pat[PPat] = A

となり、PText = 9を返してプログラムが完了しました。

まとめ

長々とやってきましたが、ポイントは以下の通りです。

アルゴリズムは慣れるまでがとても難しい分野だと思います。

トレースは時間がかかりますが着実な方法です。

トレースを使っていくつか問題を解いてみて、自分なりのコツをつかんでください！