Proofs from THE BOOK

Paul Erdos 認為上帝把每一個數學定理最精妙的證明都寫在天書 The Book 中， 同時他還說你不必相信上帝，但身為一個數學家，你應該相信天書， 當然天書並不存在於世界上， 於是數學家 Martin Aigner 和 Günter M. Ziegler 就想要寫一本近似於天書的書， 在 Erdos 熱心地幫助之下， 他們將一些具有高超思想、聰明的觀察和出色的洞察力的證明 加以整理，收錄於 Proofs from THE BOOK 一書中， 此書於 1998 年 3 月出版，可惜 Erdos 在 1996年就去世了， 沒能看到此書問世。 網路上有此書的目錄還有第一章的內容「 質數有無限多的六個證明 」可以試讀。

澄清湖接力賽

繼上次 阿公店盃接力賽 之後，又再次接受吳先生的邀請參加 6 月 20 日舉辦的 澄清湖接力， 這項比賽號稱馬拉松接力，也就是說參加接力的 7 個人要跑完 42 公里， 平均每個人跑 6 公里。 接力賽是 8 點開始，所以我 6:40 就起床了， 7:10 出發， 這是第一次自己騎車到澄清湖，有點擔心會迷路， 不過澄清湖是個知名景點，其實很容易找，一路上都有路標， 從九如路一直騎接澄清湖路左轉到底就是了， 一路上天空有厚厚的烏雲，還不時飄雨， 昨天剛發布蓮花的颱風的海上警報，我還在想說今天會不會不能跑。 即使如此，還是決定先騎到澄清湖，到時再見機行事。

Python Idiom: Decorator I

本文將介紹 Python Decorators 的用法，主要內容是根據我的理解部分改寫 Bruce Eckel 的好文 Decorators I: Introduction to Python Decorators 。假設我們有下面兩個函式

def func1():
    print "inside func1()"

def func2():
    print "inside func2()"

我們希望在呼叫 func1() 前顯示 Entering func1， 而在離開 func1() 後顯示 Exited func1， 對 func2() 的要求也是相同，只是把函式名字換成 func2， 最直接的方法是修改 func1 及 func2 的實作內容， 可是這樣做實在太累贅了， 有沒有辦法把 func1 跟 func2 當作物件， 自己寫一個額外的函式來「裝飾」這些物件？ Python 語言中所提供的 decorator 語法可以幫我們達到這個目的 (decorator 就是裝飾者的意思)。 decorator 的使用語法如下

使用快取加速遞迴函式

大家都知道 Fibonacci 序列 吧， 公式很簡單

f(n) = f(n-1)+f(n-2),  f(0) = 0,  f(1) = 1

Fibonacci 的公式是遞迴的， 因為要計算 f(n) 需要上次及上上次計算的結果。 直接套定義就有下面的函式 (in Python)

def fib(n):
   if n in (0, 1):
      return n
   return fib(n-1) + fib(n-2)

實際測試，會發現上面函式的執行效率非常差， 比方說我們要計算 f(5)，套定義，要先計算 f(3) 跟 f(4)， 可是要計算 f(4) 又要先知道 f(3) 跟 f(2)， 也就是說實際上 f(3) 算了兩次，依此類推 f(2) 計算了三次， 如果 n 很大的話，計算 f(n) 就會重覆很多不必要的計算， 要解決這個問題不難，在函式中加入一個快取來記錄之前算過的值就可以了