平成26年度春季 応用情報技術者試験(AP)の午後問題3はフロイドの循環検出法の問題でした。循環小数の循環節を検出する問題…。なんか以前出会ったことがあるなと過去を振り返ってみると、Project EulerのProblem 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)
