平成30年度秋季 応用情報技術者試験(AP)の午後問題3は、ウェーブレット木に関する問題でした。
年齢だけは重ねているので、基本情報や応用情報技術者試試験で出題される、いろいろなアルゴリズムについて詳細は知らなくても、名前だけは聞いたことがあるものが今までは出題されていたのですが、ウェーブレット木というのは初耳のような気がします。
理解を深めるために問題を解いて、プログラムを作成してみました。
プログラム(h30a_ap_pm3.rb)
実行結果
問題文中で取り上げられている、文字列Pについて、
- ウェーブレットの構築
- 文字の出現回数を数える
を実行してみました。図1と同じようなウェーブレット木が構築でき、文字数も数えられているようです。
$ ruby h30a_ap_pm3.rb #<struct Node key=342, left=#<struct Node key=24, left=nil, right=nil>, right=#<struct Node key=17, left=nil, right=nil>> A : 3 C : 2 G : 3 T : 2
追記
以前のプログラムでは、文字の種類の個数が4ではないとき、不具合がありましたので以下のページを参考に修正しました。(2019/03/31)
