Project Euler 198 題

Posted by tjwei on 星期二, 6月 17, 2008 with 2 comments
Project Euler 的 198 題。簡單的說,要算出分母在 10^8 以內,大小在 0~0.01 之間的「混淆數」總共有幾個 。而所謂的混淆數 x,是指如果對於某個 m,分母不超過 m 的「最近似 x 的分數」不只一個時,就稱 x 為混淆數。比方對於 x=9/40 來說,m=6 時, 1/5 和 1/4 都是分母不超過 6 最近似 x 的分數。
這個題目其實如果沒有任何基礎知識的話,還不太容易,所以解出的人不多。但站在一些基礎知識之上, 10^8 這種數量級是很容易用程式來秒殺的。據說 Knuth 的 The Art of Computer Programming 裡面就有提供相關的演算法。
不過使用 Haskell,可以很直接的用遞迴解出:

f a b l m | a*b>l || (a==1 && b > m)  = 0
         | otherwise = (f a c l m)+1+(f c b l m) where c=a+b
main = putStrLn $ show result
      where result= (f 1 100 l2 m) + 49+l2-m
      l = 10^8
      l2 = l `div` 2
      m = floor (sqrt (fromIntegral l2)
七行就簡單解決了。如果你知道背後的數學,上面的程式碼其實是很直接的。但用 Python 解就麻煩了,因為上面這個遞迴解超出 Python 的遞迴深度。可以用迴圈來取代遞迴,如下面的演算法:


def p198(M=10**8, z=100, cnt=0):
 M2=M/2
 a=m=int(M2**0.5)
 stack=range(z,m)
 while stack:
     b=stack[-1]
     if a*b>M2:
         a=stack.pop()
     else:
         cnt+=1
         stack.append(a+b)
 return cnt+M2-z/2
(程式碼我從 Project Euler 直接貼過來,排版有點亂掉)
這個演算法是我參考別人的解答後寫出的,配上 psyco 後,其實還挺巧妙也挺快的,但不太容易讀懂,要跟蹤一下堆疊是怎麼跑的。
但有些簡單的工作, Haskell 寫起來又很累贅。比方有一個整數 n,想找出它的根號的整數部份,如後印出來,在 python 來說再簡單不過的
print int(x**0.5).
Haskell 的作法要先將整數轉成浮點數,開根號,然後再用 floor 轉成整數,最後再用 show 轉成字串才能印出。所以是
putStrLn.show $ (floor . sqrt) (fromIntegral n)
如果有許多浮點數與整數,那更複雜一點的運算就要轉來轉去。雖說這樣可以強迫正確的設計風格,但有時只是簡單的小計算,這樣也未免太累了。
果然 Haskell 能將複雜工作簡單化,簡單工作複雜化。
Categories: , , ,