星期五, 3月 12, 2010

Haskell Practice - Ugly Numbers

題目就在這,我就不再多做說明了,這題寫完,暫時要停下來,把 scm 老師的信消化,然後鳥書繼續前進 XD。

is_un n
    | n == 1 = True
    | n `mod` 2 == 0 = is_un (truncate (fromIntegral n/fromIntegral 2))
    | n `mod` 3 == 0 = is_un (truncate (fromIntegral n/fromIntegral 3))
    | n `mod` 5 == 0 = is_un (truncate (fromIntegral n/fromIntegral 5))
    | otherwise = False


is_un2 n
    | n == 1 = True
    | n `mod` 2 == 0 = is_un2 (until (\x -> x `mod` 2 /= 0) (\x -> truncate (fromIntegral x/ fromIntegral 2)) n) 
    | n `mod` 3 == 0 = is_un2 (until (\x -> x `mod` 3 /= 0) (\x -> truncate (fromIntegral x/ fromIntegral 3)) n)
    | n `mod` 5 == 0 = is_un2 (until (\x -> x `mod` 5 /= 0) (\x -> truncate (fromIntegral x/ fromIntegral 5)) n)
    | otherwise = False

is_un3 n = foldl judge n [2,3,5] == 1
    where judge n y = until (\x -> x `mod` y /= 0) (\x -> truncate (fromIntegral x/ fromIntegral y)) n

un_list :: [Integer] -> Integer -> [Integer]
un_list (x:xs) n 
    | n == 0 = (x:xs)
    | otherwise = un_list (min:x:xs) (n-1) 
    where min = minimum (filter (>x) [u*v | u<-(x:xs), v<-[2, 3, 5]])

傳說中這題是一行就可以寫完的,但是我不知道怎麼寫,我還是一樣照我的想法寫 XD,剛開始的想法非常簡單,一直除 2, 3, 5,最後的結果不等於 1 就不是,這方法當然很慢,不過練習還是有用的,因為從 is_un 至 is_un3 可以讓我練一下 foldl ,也讓我明確的了解到 foldl 和 foldr 的根本性不同 (沒錯,我之前又完全搞錯了,剩下只有 fold fusion 要搞懂了)

最後一個 un_list 的想法則是比較正面,找到前面 list 乘於 2, 3, 5 然後大於 list 最大的數的數列最小值,這速度顯然快很多 XD。在這樣子的狀況下寫成 tail recursive 比較直覺,但是其實將整個數列反過來算也是 ok 的,所以我就索性反過來算了。測試結果如下 ...

*Main> reverse (un_list [5, 4, 3, 2, 1] 1495)
[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60,64,72,75,80,81,90,96,100,108,120,125,128,135,144,150,160,162,180,192,200,216,225,240,243,250,256,270,288, ...

同場加映 Python 版,不過真的只能說 Haskell 影響 Python 很深,在 list 操作部分很像,但是沒有 Haskell 來的漂亮 XD

def ugly_number(list_size):
    ug_list = [1]
    for i in range(0, list_size-1):
        ug_list.append(min(filter(lambda x: x>ug_list[len(ug_list)-1], [x*y for x in ug_list for y in [2,3,5]])))
    return ug_list

---
該繼續打底了 ... XD


2010/03/15 05:58 pm 今天晚上可能無法再做練習了,可能要先看一下 paper ,不過初步的破爛想法是

makePrime x = if prime (x+add) then (x+add)
            else makePrime (x+add) 
            where add = if x `mod` 6 == 1 then 4 else 2
primes = 5: map primeCircule2 primes

其實不是沒有想過一次生二個 element (試著寫 let p = 5:7: map (6+) p),但是回傳時一定要產生一個 element,如果不是的時候總不能丟 0 XD,所以只好先交出一個破爛方法,剩下的明天再試。


2010/03/18 11:06 am 後來想到兩個數列分開算再用 merge 即可,不過速度上應該是佔不到便宜就是了 ...

makePrime_plusn n x = if prime (x+n) then (x+n) else makePrime_plusn n (x+6) 
primes = 5: map makePrime primes
primes2 = merge primes_plus2 primes_plus4 
    where primes_plus2 = 5: map (makePrime_plusn 6) primes_plus2 
          primes_plus4 = 7: map (makePrime_plusn 6) primes_plus4

張貼留言