kozima #4882(2007/12/19 05:17 GMT) [ Haskell ] Rating0/0=0.00
Haskell の勉強にと移植してみました。GHCi で33秒とあんまり速くはありませんが、わりとすっきりしたコードになったので投稿してみます。ついでに中身について少し説明でも。
上の桁から順に決めていくのですが、その際に桁数を固定することでゲーデル数化する前と後の数(sum, prod)の両方を部分的に計算でき、枝刈りがやりやすくなります。
実際にやっているのは次の二つですが、他にも末尾の 0 の数で刈れたりするかもしれません。
後者のは実質「積が 10^i を超えたら」なのですが、上のようにした方が速いようです。(扱う数が fixnum に収まりやすい？)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
primes = flip take [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] basis n = map (\x -> 10^x) [n-1,n-2..0] f :: [Integer] -> [Integer] -> Integer -> Integer -> Integer -> Integer -> [Integer] f [] [] _ prod sum _ | prod == sum = [sum] | otherwise = [] f (p:ps) (b:bs) bound prod sum start | start == 0 && prod > sum = [] | otherwise = [x | i <- [start..9], p^i <= bound, x <- f ps bs (div bound $ p^i) (prod * p^i) (sum + b * i) 0] meertens n = [x | i <- [1..n], x <- f (primes i) (basis i) (10^i) 1 0 1]
Rating0/0=0.00-0+
2 replies [ reply ]
kozima
#4882()
[
Haskell
]
Rating0/0=0.00
Haskell の勉強にと移植してみました。GHCi で33秒とあんまり速くはありませんが、わりとすっきりしたコードになったので投稿してみます。ついでに中身について少し説明でも。
上の桁から順に決めていくのですが、その際に桁数を固定することでゲーデル数化する前と後の数(sum, prod)の両方を部分的に計算でき、枝刈りがやりやすくなります。
実際にやっているのは次の二つですが、他にも末尾の 0 の数で刈れたりするかもしれません。
後者のは実質「積が 10^i を超えたら」なのですが、上のようにした方が速いようです。(扱う数が fixnum に収まりやすい？)
Rating0/0=0.00-0+