Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

平成30年度秋季応用情報午後問3

平成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