Scratch & Math: 數學裡的皇冠 (一)
有些人說在學校學了很多年的數學但是畢業以後都用不到,但是換一個角度想想,另外有一群人終生奉獻給數學的研究,在數學史的發展中甚至有人為了數學研究犠牲性命也在所不惜。這大概是因為當人們把數學當成一門純粹的學問看待和研究時,就會開始體會到數學的美和潛藏在其間、隱隱和這個世界運行相符的真理。數學裡的數論就是純粹數學研究的代表,它就像數學裡的皇冠般,在眾多數學領域裡煥發出自己的耀眼光采。在這一章裡我們會介紹幾個著名的數論問題,同時用Scratch實做來計算這些問題。
數學關鍵字: 數論 、輾轉相除法( Euclidean algorithm) 、最大公因數( greatest common divisor,gcd)。
程式關鍵字:完整性檢查(Sanity check)。
Scratch程式:
數學做為一種真理
中國漢、唐時期發展出了獨物而完整的數學體系,留傳下來的十部重要數學書籍被總稱為「算經十書」。「周髀算經」是其中最早的一部著作,成書的時間大約在西漢末年,書中已經提到計算直角三角形邊長關係的勾股定理。同樣成書在漢代的「九章算術」共收有246個數學問題,內容分為九大類,涉及田畝面積的計算、糧食交易的比例計算、開平方和開立方的方法,以及聯立方程的計算。
算籌和算盤就是中國古代的計算工具,算經中描述的術文就是計算的程序。有工具有程序,中國古代數學逐漸發展成一個以實用為目的的完整的計算體系。
數學在古希臘就有大不相同的發展歷程。古希臘人提出了許多基本的哲學問題:世界上的事物從那裡來?它們是由什麼構成?古希臘人嘗試利用數學回答這些基本卻艱難的問題,他們視數學為認識宇宙的工具,將哲學的思想帶進數字和幾何形狀之中,逐漸發展出一套強調邏輯推演的數學體系。於是發韌為土地測量和天象觀察的實用數學,逐漸演化為點、線、三角形、多邊形、圓、角度等抽象的幾何觀念。歐幾里得的幾何原本更進一步,由定義和公理出發,推導出一系列的定理。著名的畢達哥拉斯學派提出了原子論,主張構成線段的「點」具有一定的大小,而且有大於零的長度。
畢達哥拉斯學派發現整數的比例可以構成幾何圖形,整數的比例可以發出和諧的聲音。他們對整數有的崇拜逐漸發展為一個宗教性質的組織。因此當畢達哥拉斯的弟子希帕索斯發現等腰直角三角形的斜邊無法用整數比例表示時,對於動搖整個學派的基石的希帕索斯也就只能被祕密處死了。
不過希帕索斯的死並不代表畢達哥拉斯學派的學說就變得正確了。數學做為一種真理,對的永遠就是對的。希帕索斯因為站在真理的一方而歷史留名,古往今來沒有人能用權力、名聲或一切人為的手段挑戰真理。
早期的數論
數論是一種探討數字的理論,特別關注在整數,像質數、因數和倍數都是數論是重要的課題。早期的數論是算術的同義詞,古希臘數學家對這類問題有許多研究,同時已經推導出數論裡的幾項重要定理。
問題1:質數是否有無窮多個?
從歐幾里得開始,就有很多的數學家對於「質數是否有無窮多個」這樣的問題感到興趣,並且不斷有人提出各種證明。歐幾里得在他的著作「幾何原本」中以反證法證明了質數有無窮多個,這個證明方法也就被稱為「歐幾里得定理」。
所謂的反證法就是先假設命題不成立,然後推理出明顯自相矛盾的結果,這樣就可以說明假設不成立,讓原命題得證。
所以用反證法證明「質數是否有無窮多個」,首先就必須假設質數的個數是有限的。所有質數的數列總共有n項,寫做P1, P2, …Pn。
在這種情況下,一定存在一個整數P=(P1*P2*…*Pn)+1。任意質數Pi都可以整除P1*P2*…*Pn,i=1~n。但是由於最小的質數是2,可以推斷出任何一個質數Pi都不能整除1,所以Pi也不能整除(P1*P2*…*Pn)+1。
於是我們得到一個結論,先前假設的n個質數都不會是整數P的因數,整數P的因數只有1和P本身,整數P是一個質數。
推論到這裡就出現了矛盾,原來假設質數的個數有限,總數為n個。而整數P不是假設n個質數中的任何一個,但P卻也是一個質數。這說明原來的假設「質數的個數是有限n個」不合理,所以「質數的個數有無窮多個」才是正確的命題。
問題2:如何求兩個整數的「最大公因數」?
依照算數基本定理,每個大於1的整數均可寫為質數的積,這些質因數按大小排列後,乘積只有一種表示法。
假設現在有兩個大於1的整數105和252,依算數基本定理可以表示成下面的式子:
105 = 2 * 3 * 7
252 = 3 * 5 * 7
在兩個整數間找出共有因數的最大值,就是兩整數的「最大公因數」。在105和252這個例子裡,列出兩個整數的因數分解乘積式,就可以看出3*7=21就是它們的最大公因數。
歐幾里得提出了另外一個演算法來求解兩個整數的最大公因數,被稱為「歐幾里得算法」或是「輾轉相除法」。同樣以整數252和105為例,歐幾里得算法首先將較大的整數252當成被除數,105當成除數,做一次除法,
步驟一得到除法餘數為42之後,進一步將105當成被除數,42當成除數,再做一次除法,
步驟一: 252 = 105 * 2 + 42
步驟二得到除法餘數為21,以相同的方法做第三次除法,
步驟二:105 = 42 * 2 + 21
步驟三得到整除的結果,計算停止,同時判定252和105的最大公因數為21。
步驟一:42 = 21 * 2 + 0
歐幾里得算法可以寫成像下面的直式表示式,左右反覆進行除法的計算,直到有除式的餘數為0。

動手做9–1 歐幾里得算法
[程式設計需求規格]
給定任兩個整數,利用歐幾里得算法求最大公因數。
[程式設計角色和舞台]
由範例庫任意選取一個角色和舞台造形。
[程式設計解決方案]
[程式檢視]
程式[Abby 9–1.1]中將使用者輸入的兩個數分別設定為被除數和除數,再利用迴圈執行歐幾里算法,不斷交換除數為新的被除數,餘數為新的除數,直到除式的餘數為0停止。這個時候最後一個除數就是輸入兩數的最大公因數。
[測試1]第一個數字=225,第二個數字=105。
程式中製做了清單「歐幾里得算法」來記錄並顯示所有的計算過程。當我們輸入被除數為252和除數為105後,可以計算得到兩數的最大公因數為21。

我們可以其他的輸入看看計算結果是否仍然正確。
[測試2]第一個數字=105,第二個數字=225。
接下來我們試試看輪入第一個數字小於第二個數字,在這種情況下,初始設定的被除數會小於除數。

程式執行得到正確的最大公因數21,總共有四個計算步驟,相較於[測試1]多了一步。
由清單記錄可以看到在計算的第一步時,被除數(105)雖然小於除數(225),但是經過輾轉相除,第二步的被除數就被設定為較大的數字225,同時除數被設定為105。
[測試3]第一個數字=0,第二個數字=105。
被除數為0,除數為105。執行程式得到最大公因數為0。

[測試4]第一個數字=225,第二個數字=0。
被除數為225,除數為0。除以0的除式會造成無窮大的商,程式因此進入無窮迴圈,得不到答案。

[測試5]第一個數字=225.1,第二個數字=105.3。
輸入不為整數的數字,被除數為225.1,除數為105.3。程式計算得到最大公因數為一個小數。

經過了五種輸入的數字組合,我們可以看到測試3、4、5的狀況其實會得到錯誤或是沒有意義的答案。我們可以在程式一開始的時候針對輸入數字做檢查,要求輸入的數字必須為大於0的整數,避免浪費執行時間做錯誤或是沒有意義計算。
有鑑於此,我們改寫一下程式[Abby 9–1.1],對於使用者輸入的變數做初始檢查。
[程式設計解決方案]
[程式檢視]
程式[Abby 9–1.2]中對於使用者的輸入進行檢查,呼叫程式[Abby 9–1.3]的條件判斷式來判定數字是否為正整數。
判斷條件分為兩部份。第一部份檢查數字是否大於0,以確保數字會是正數。
整數的判別可以利用下面的程式方塊:當一個數做四捨五入後還等於數字本身,我們就可以判定這個數字是整數。

執行這組新的程式會發現,如果輸入的數字是0、負數或是含小數點的數都不會被接受。只有當輸入兩個正整數後,才會開始計算最大公因數。
觀念平台:完整性檢查(Sanity check)程式設計中常常會對資料做簡單的完整性檢查,以快速而初階的測試確保程式可以正確而合理地進行分析計算。在最大公因數的程式[Abby 9–1.1]中,我們先用幾組簡單的輸入快速得到測試結果,確認對於兩個正整數的最大公因數計算正確無誤,同時也針對其他不同的輸入數字(例如除數為0)進行運算和測試。在快速觀查了不同輸入的執行結果後,對於錯誤的數字輸入進行程式的除錯,然後在適當的地方加上檢查的程式方塊。當我們通過簡單的完整性檢查修改程式,之後的程式執行就不會再出現同樣的錯誤了。
延伸閱讀:
Scratch & Math: 天花板上的蜘蛛(一) 天花板上的蜘蛛(二)
Scratch & Math: 直線裡的宇宙觀(一) 直線裡的宇宙觀(二)
Scratch & Math: 不能說的祕密(一) 不能說的祕密(二)
Scratch & Math: 無理的道理(一) 無理的道理(二) 無理的道理(三)
Scratch & Math: 歡樂派(一) 歡樂派(二) 歡樂派(三) 歡樂派(四)
Scratch & Math: 隱藏在花朶裡的祕密(一) 隱藏在花朶裡的祕密(二)
Scratch & Math: 兔子繁殖是一個好問題 (一) 兔子繁殖是一個好問題 (二) 兔子繁殖是一個好問題 (三)