キミならどう書く 2.0 - ROUND 2 -
Posted by
ヒビルテ
at
2006-07-12 11:37
与えられた範囲の中でCollatz予想の収束までのステップ数が最大となる値を求める問題。とりあえず、Haskellで超素朴なコードで試してみたら「h 1000000」に40秒くらいかかった。
import List
g 1 = 1
g n = 1 + g (if even n then n `div` 2 else 3*n + 1)
h n = fst $ maximumBy c [(k, g k) | k <- [1..n]]
where c (_,x) (_,y) = x `compare` y
実行結果。
Main> h 100
97
Main> h 1000000
837799
以下のようにして100000までの値をテーブル化すると7秒まで縮んだ。
更に効率化するにはどうすれば良いだろう?
import List
import Array
tableMax = 100000
table = array (1, tableMax) [(i, g' i) | i <- [1..tableMax]]
g n = if n <= tableMax then table ! n else g' n
g' 1 = 1
g' n = 1 + g (if even n then n `div` 2 else 3*n + 1)
h n = fst $ maximumBy c [(k, g k) | k <- [1..n]]
where c (_,x) (_,y) = x `compare` y
Parent entry
キミならどう書く 2.0 - ROUND 2 -