Project Euler 198 題

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...

Read More

程式設計語錄

圖片來源: wikipedia (選自 DevTopics 整理的語錄) (用來讓自己看起有學問的) "Simplicity, carried to the extreme, becomes elegance."  簡單到極致即為優雅。 – Jon Franklin "The best way to predict the future is to implement it."  預測未來的最佳方式就是實做它。 – David Heinemeier...

Read More

zhpy 的另類用法

配合上 zhpy ，我們可以寫出下面這樣的 python 程式: # encoding: zhpy_utf8from math import *from operator import *print Σ(range(100))print sin(π/4) ≠ √(2)/2print ㏒(100), ㏑(e)print 5 × 30 ÷ 2 ≦ tan(√(5)*π/4)Π=λ f:reduce(mul, f, 1)print Π(range(1,6))print set([1, 2, 3, 4, 5]) ∩ set([1, 3, 5, 7, 9])(第一行是 MagicCodec 語法，普通的 zhpy 請去掉第一行)不管實不實用，至少增加了一點可讀性。既然是λ，為什麼要寫成 lambda?以上的程式碼只需要下面的...

Read More

根號 2 到兩百萬位的挑戰

Sphere Online Judge 有一個題目是在 20 秒內計算根號 2，越多位越好（上限是兩百萬位）。有不少人能達到這個目標，但都是使用 C 或者 C++。我想試試看 python 這種以速度慢聞名的語言，能達到什麼程度。試驗的結果是十五萬位。雖然不太多，但是也擠進了排行榜裡面前二十名。而目前 python 語言的第二名還不到五萬位。我的程式沒有用什麼特殊的技巧。事實上， python 的乘法不算太慢，現在 python 已經使用了 Karatsuba 演算法來做乘法，在一萬位以內的效能都還不錯，算到十幾萬位也都還能接受。但再上去就有點吃力了。而最主要的瓶頸在於 long 到 str 的轉換速度。光是將一個兩百萬位的數字轉成字串，就會花上非常久的時間。改用 gmpy 會快很多，應該能夠算到百萬位以上，雖然我沒試過，但...

Read More

Euler 計畫和其他

前一陣註冊了 Project Euler，然後玩了一下裡面的題目。Project Euler 蒐集了一系列的挑戰問題，這些問題的答案都是一個數字或者一組數字。每當你破解一個問題後，你就能與其他同樣破解這個問題的人，討論答案與心得。通常解決這問題需要一點程式設計技巧和數學知識。網站裡面也會對於不同國家或者程式語言的解題者做統計和排名。比方說這是台灣的統計，而這是 Python 語言的統計。和「點點點」相比，台灣的表現很爛。一般所謂的 online judge 系統其實很多，ACM 風格的 online judge 是主流。 UVa online judge 是其中的代表。其他還有如ZeroJudge。和 Project Euler 不同， Project Euler 上傳的是答案，而這類 online...

Read More