Google Treasure Hunt 2008

五月初Google Australia Blog開放了一個treasure hunt的遊戲,
這個網站大致會每周開放一個問題,而目前已經出了兩題了.

第一題是計算機器人到達目的地的所有可能路徑,
第二題是掃描資料夾跟開啟檔案取得內容並計算的功能.

聽說第一個正確解出這些問題的會有獎品...

大致上第二題沒有太大的難度,
而第一題倒是有點麻煩,
而麻煩的地方是在於大數計算的部分.

因為這題跟組合排列有關,所以需要使用階乘的計算
而excel中有提供一個fact的函數可以計算階乘.

例如在excel儲存格中輸入 =fact(5) 就可以得到 120
而輸入 =fact(20) 則是 2.4329E+18
這時只要修改儲存格格式,
改為數值,並去掉小數點,就可以得到2432902008176640000
感覺大致上沒有甚麼問題.

所以就直接套用公式,取得結果送出,但是得到的答案卻是說不正確.
後來仔細研究才發現,
excel中,當fact(21)時,算出來的數值就開始不正確.
在excel中,fact(21)會得到
51090942171709400000
但是實際上的數值應該是
51090942171709440000
那當然,在往後面算也就不會是正確的了.

這時才想到大數運算的問題.
所以只好自己用c#寫個處理超長整數運算的功能.
這才總算得到正確的數值了.

不過,剛剛改用python來試試看階乘計算時才發現,
原來python不會超長整數計算的問題

def fact(num):
    tmp = 1
    for x in range(1,num+1):
        tmp = tmp * x
    return tmp

if __name__ == "__main__":
    print fact(21)
    print fact(50)

不知道出這題是不是要展示python的這個特性
ps. treasure hunt是架在appengine上的系統,所以是用python開發的.