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,可以很直接的用遞迴解出:
這個演算法是我參考別人的解答後寫出的,配上 psyco 後,其實還挺巧妙也挺快的,但不太容易讀懂,要跟蹤一下堆疊是怎麼跑的。
但有些簡單的工作, Haskell 寫起來又很累贅。比方有一個整數 n,想找出它的根號的整數部份,如後印出來,在 python 來說再簡單不過的
果然 Haskell 能將複雜工作簡單化,簡單工作複雜化。
這個題目其實如果沒有任何基礎知識的話,還不太容易,所以解出的人不多。但站在一些基礎知識之上, 10^8 這種數量級是很容易用程式來秒殺的。據說 Knuth 的 The Art of Computer Programming 裡面就有提供相關的演算法。
不過使用 Haskell,可以很直接的用遞迴解出:
七行就簡單解決了。如果你知道背後的數學,上面的程式碼其實是很直接的。但用 Python 解就麻煩了,因為上面這個遞迴解超出 Python 的遞迴深度。可以用迴圈來取代遞迴,如下面的演算法:
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)
(程式碼我從 Project Euler 直接貼過來,排版有點亂掉)
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
這個演算法是我參考別人的解答後寫出的,配上 psyco 後,其實還挺巧妙也挺快的,但不太容易讀懂,要跟蹤一下堆疊是怎麼跑的。
但有些簡單的工作, Haskell 寫起來又很累贅。比方有一個整數 n,想找出它的根號的整數部份,如後印出來,在 python 來說再簡單不過的
print int(x**0.5).Haskell 的作法要先將整數轉成浮點數,開根號,然後再用 floor 轉成整數,最後再用 show 轉成字串才能印出。所以是
putStrLn.show $ (floor . sqrt) (fromIntegral n)如果有許多浮點數與整數,那更複雜一點的運算就要轉來轉去。雖說這樣可以強迫正確的設計風格,但有時只是簡單的小計算,這樣也未免太累了。
果然 Haskell 能將複雜工作簡單化,簡單工作複雜化。
2 意見:
你可以參考看看 Michele Simionato 寫的 decorator module (http://www.phyast.pitt.edu/~micheles/python/documentation.html) 裡的 @tail_recursive decorator
這樣一來 python 就有類似於 functional programming 的 tail-call elimination 的能力
我沒實際試過, 正好看到你的文章, 也許你可以玩玩看 :)
謝謝。tail recursion decorator 還挺酷的。
一般來說,有兩個 recursive call 的情形,即使有 tail call elimination 還是會碰到深度限制。
但單就這個問題來說,因為他只有一個分枝跑比較遠,所以這個 decorator 應該是可以用的。
張貼留言