Mae向きなブログ

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

平成21年度秋期応用情報午後問2

平成21年度秋期 応用情報技術者試験(AP)の午後問題2は文字列照合に関する問題でした。

文字列照合といったら、遥か昔、学生時代に

といったアルゴリズムがあるということは習って知っていましたが、パターン文字列の情報を利用して効率よくスキップするということ位しか理解できていませんでしたので、今回はいい学習の機会となりました。

h21a_ap_pm2.rb

実行結果

問題では、以下の2種類が示されています。

  • 方法1は、単純な照合方法
  • 方法2は、効率的な照合方法、ボイヤー-ムーア法でしょうか?

方法2がどの程度、効率的なのか速度比較を行ってみました。

英大文字、小文字から長さ100万のランダムなテキストを生成し、パターンは生成したテキストの末尾300文字を設定しています。

実行結果は以下の通りです。

$ ruby h21a_ap_pm2.rb
                      user     system      total        real
Naive           999700
  0.720000   0.010000   0.730000 (  0.728408)
Boyer-Moore     999700
  0.190000   0.000000   0.190000 (  0.186781)

平成23年度特別試験応用情報午後問2

平成23年度特別試験 応用情報技術者試験(AP)の午後問題2は集計表(CSV)をHTMLに変換して出力するプログラムに関する問題でした。

h23tokubetsu_ap_pm2.rb

input.csv

東京都,千代田店,23500
東京都,中央店,33500
東京都,港店,18500
埼玉県,川口店,28000
埼玉県,蕨店,9500

実行結果

$ ruby h23tokubetsu_ap_pm2.rb input.csv > output.html

簡単な問題だと油断して最初に得られた結果が以下です。

f:id:rahaema:20170624103331p:plain:w350

間違いを修正して実行したのが以下です。実際に自分で手を動かして作ってみると間違いにすぐに気付くことができますが、ただ紙上で解くだけだと模範解答を見るまで気づけなかったかもしれないなと思います。

f:id:rahaema:20170624103544p:plain:w350

平成25年度春季応用情報午後問2

平成25年度春季 応用情報技術者試験(AP)の午後問題2は逆ポーランド記法に関する問題でした。

h25h_ap_pm2.rb

実行結果

$ ruby h25h_ap_pm2.rb
1 2 3 * +
2 3 + 4 *

参考

Unity5入門

Unityという言葉は少し前から聞いたことがあったのですが、とうとう必要に迫られてUnityについて勉強し始めました。Web上にも有用な情報はたくさんありそうですが、まずは本を読みながらUnityの概要や基本のキについて身につけたいところです。なかなか高機能なのでどこまで学べばゴールになるのでしょうか。ゴールの設定が難しそうです。

Unity5入門 最新開発環境による簡単3D&2Dゲーム制作

Unity5入門 最新開発環境による簡単3D&2Dゲーム制作

参考URL

平成26年度春季応用情報午後問3

平成26年度春季 応用情報技術者試験(AP)の午後問題3はフロイドの循環検出法の問題でした。循環小数の循環節を検出する問題…。なんか以前出会ったことがあるなと過去を振り返ってみると、Project EulerProblem 26でした。そのときは、割った余りをハッシュに格納していき、再び同じ余りに出会ったら循環節検出という単純な方法で解いています。せっかくフロイドの循環検出法について解いてみたので、両者を速度比較してみました。

h26h_ap_pm3.rb

実行結果

実行結果は以下のようになりました。フロイドの循環検出法は、ウサギがカメに追いついたとき、ウサギはスタート地点に戻され、再び一歩ずつ進むなど、なんとなく遅いイメージがあるのですが、実際に実行してみるとフロイドの循環検出法が早いという意外な結果となりました。不思議です。

$ ruby h26h_ap_pm3.rb
                 user     system      total        real
ウサギとカメ     14939
  2.390000   0.000000   2.390000 (  2.404701)
単純な方法      14939
  3.410000   0.120000   3.530000 (  3.537377)

参考

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

平成26年度秋季 応用情報技術者試験(AP)の午後問題3はマージソートの問題でした。今までいくつかのプログラミング言語クイックソートをはじめ何種類かのソートアルゴリズムを作ってはいますが、よく考えてみるとマージソートを作ったことはなかったような気がします。マージソートは理屈は簡単に思えるのですが、それを作るとなると億劫に思っていたんだと思います。せっかくの機会なので作ってみました。

h26a_ap_pm3.rb

実行結果

$ ruby h26a_ap_pm3.rb
Before:6 4 3 8 7 2 1 5
After :1 2 3 4 5 6 7 8

参考

平成27年度春季応用情報午後問3

平成27年度春季 応用情報技術者試験(AP)の午後問題3はデータ圧縮の前処理として用いられるBlock-sorting(ブロックソート)に関する問題でした。学生時代(20年以上前)、データ圧縮について少し勉強したことがあるのですが、Block-sortingというアルゴリズムに接するのは今回が初めてです。Wikipedeiaで調べてみると、1994に開発されているようです。ちょうど自分が学生時代、データ圧縮について勉強しているときに開発されてたんですね。

h27h_ap_pm3.rb

実行結果

$ ruby h27h_ap_pm3.rb
入力文字列: papaya
変換結果 : yppaaa, 3
復元処理後: papaya

入力文字列: kiseki
変換結果 : skkeii, 4
復元処理後: kiseki

思うこと

「図4 関数decodeのプログラム」ではが空欄になっていますが、をwhileループの外に出したということは、は、「n != line」と答えさせようという意図があるのではないでしょうか。模範解答のを想定するのであれば、は不要で以下で良いのではと思います。ひょっとしたら勘違いをしているかもしれませんが。

  outputString = []
  n = line
  while outputString.length < blockSortString.length
    outputString << decodeArray[0][n]
    n = decodeArray[1][n]
  end

参考