精選文章

良葛格 - 從40個判斷式到1個算式

March 14, 2015 10:55


(文/林信良,轉載自IThome)

在程式開發領域,手中如果能有多種工具,如此面對不同問題,才能使用最適合工具加以解決

若要算出1加到100總和,該怎麼做呢?學過程式的人,八成會寫個for迴圈跑1到100,重複進行加總來解決問題;現在函數式比較有人討論了,那來個遞迴好了,將目前數字與後續數字總和做相加,看來似乎比較高級;至於經常以數學思維來處理問題的人,則會告訴你1加100後乘以100再除以2

還有其他的思考方式嗎?

 

要用到40個判斷式?

不久前在玩機器人積木,設計了個類似吉他的東西,打算用左手三個觸碰感應器區分八個狀態,在每個狀態下,右手可按下主機上五個按鈕各發出一個音階,也就是說,想設計出一個可以發出40個音階的樂器,其實可以再多一個觸碰感應器,以發出更多音階,不過,我先停下來思考一個問題,按照這樣設計,也表示觸碰感應器加上主機按鈕,總共會有40個可能的組合方式,該如何判斷狀態?

最基本的方式,就是建立40個if分支判斷,這方法行不通,光是建立40個分支這個過程就夠嚇人了,更何況,如果打算再多個觸碰感應器,就得再多出40個分支,才能讓樂器變成可以發出80個音階,稍微瞭解程式設計的開發者,都知道這種寫法完全就是個反模式,一定還有其他方式!

建立一個40個元素的陣列如何(積木程式中,並未提供Map)?陣列值為01、02、03、04、05,表示未按任何觸控感應器下,各按下主機其中之一按鈕的情況,如果按下一個觸控感應器,就用11、12、13、14、15來代表主機各按鈕被按下,這麼一來,三個觸碰感應器可當成2進位數字,並轉換出0到7的10進位值,主機按鈕算出1到5的值,如此可跑迴圈,對應到陣列中某個元素值,如果每個元素值之後接上頻率,例如01261626,去掉前兩位再除以1000,那就是261.626,也就是Do音階頻率。

這表示,我可以將40個判斷式,改用40個元素的陣列取代,如果要再多個觸碰感應器,那就是在陣列中追加40個元素,每個元素值之後同樣附上各音階頻率,追加陣列元素值是比追加if分支判斷來得簡單一些,只是得查出各音階頻率,仔細地附加到每個元素值之後,這滿麻煩的。

不過,我還是打開了瀏覽器,鍵入了「音階頻率」開始搜尋,在維基百科「音高」條目上找出「音高頻率表」,過程中,卻順手點進去看了一下「十二平均律」條目,不久,40個元素的陣列就被拋棄了,只留下一個算式。

 

十二平均律的威力

會被十二平均律條目吸引,在於最近接觸樂器,印象中看過幾次這個名稱,簡單來說,就是將一個八度(像是Do、Re、Mi到下個高音Do)平均分成十二等份,每等分為一個半音,至於十二等分的畫分方式不是等差級數,而是等比級數,在十二平均律中,每個音頻率為前一個音的2的12次方根,約為1.059463,例如,如果Do音為261.626,那麼下個半音就是261.626乘上1.059463,也就是277.183(升Do),再下個半音就是261.626*1.059463*1.059463=293.665,也就是Re。

對這個樂器小程式來說,單只是知道這樣就足夠了,之前設計的陣列元素01、02、03、04、05、11、12……到71、72、73、74、75,各可以對應到一個頻率,實際上,陣列元素換算過來10進位就是1到40,一個觸碰感應器輸出值是0與1,主機按鈕輸出值是1到5,如果三個觸碰感應器輸出是a、b、c,主機按鈕輸出是d,換算公式就是(a+b*2+c*4)*5+d,若結果為n,且以頻率261.626開始,之後各個音的頻率就是1.059463的n次方,再乘上261.626。

這麼一來,如果要再增加一個觸碰感應器,若輸出值為d,那換算為10進位的公式,也只要調整為(a+b*2+c*4+d*8)*5+d,也就是可以1到80,不用使用龐大if分支判斷,也不用辛苦地建立陣列將狀態對照至頻率,只因為瞭解了十二平均律,實際上,真正使得設計方向得以朝簡化、有彈性的方向改變的,並不是多高深的程式設計觀念,單單只是音樂領域中的基礎知識。

 

不是所有東西都是釘子

有句西方諺語說:「當你手上只有錘子時,所有東西都是釘子。」這句話若拿來套用在程式開發領域,通常是指手中不要只有一種工具,像是語言、程式庫或框架等,如此面對不同問題,才能使用最適合工具加以解決。實際上,這句話可以擴大來看,擅長某領域知識的人,面對什麼事情,都會用他擅長的邏輯來處理事情,這本是好事,然而有時也會形成一種盲點,就像擅長程式設計思維的人,解決問題有時也很容易就往程式邏輯中鑽,就像一開始談到的1加到100問題。

1加100後乘以100再除以2的解法,其實就是等差級數公式,首項與末項的和乘以項數除以2,據說數學家高斯在小時候就發現這個公式,他的老師讓學生們做從1加到100的習題,大多數小孩應該都是從頭開始加,而高斯觀察到1+100=101、2+99=101……,因而能很快說出5050的正確答案。實際上,就觀察力這點,對數學家與程式人都是滿重要的能力,遇到問題時換個方向觀察規律,往往是從問題中理出頭緒的重要開始,壓縮、模式辨識等重大演算法,往往就是如此產生。

然而,除了換個方向先行觀察之外,如果處理特定領域問題,更重要的,往往不是只用程式邏輯蠻幹,而是跳出既有程式領域,使用問題領域中的思維來尋求解答,這就是許多程式人所謂領域知識的重要性,1加到100的總和,以迴圈來解複雜度會是O(n),以等差級數公式來解決則會是O(1),這邊談到的簡單樂器程式,使用狀態的思維會是40個分支判斷,從十二平均律來解,卻只要一個算式!

不想讓所有東西看來都像是釘子,不單只是在擁有技術或工具上的問題,也在於平常有無在生活各方面、各領域上多所涉獵。

就如同上述樂器程式的問題,某些程度上,是因為我近來涉獵樂器,才得以漂亮地解決,John MacCormick在《改變世界的九大演算法》結論中就談到:「所有偉大的觀念,不需要會寫程式等電腦科學的知識就能解釋」,另一方面「電腦科學的領域不僅僅是寫程式而已」。

 

一定還有其他方式!

從數學領域往其他領域看,也不乏這類例子,像是求圓周率並不是只能使用圓周長與半徑,也可透過亂數取樣模擬來解決,看看產生的數各有多少在圓內及圓外,因此導出圓周率公式,更早前還有1777年法國數學家Buffon的投針試驗(Buffon's needle),他在白紙上畫了等距平行線,並對白紙投擲長度為平行線間距一半、重量相等的針,在2212次投擲中,針與平行線相交704次,2212/704約為3.142,也就是圓周率近似值。

亂數取樣模擬求圓周率這類方式,稱為蒙地卡羅法(Monte Carlo method),Monte Carlo為摩洛哥首都,也就是知名賭城,由此聯想此方式帶有賭博意味,現今則可使用電腦來產生亂數,將蒙地卡羅法應用在數值方法之中,像是計算不規則圖形的面積等。

已經有太多人呼籲過領域知識的重要性,只是每個人時間畢竟有限,不可能各個領域都能有所涉獵,更何況每個領域的專精,沒有個5年、10年,也不足以成為專家。

就我這次的問題來說,也只是剛好問題夠簡單,能夠使用十二平均律,簡單地解決罷了。成為領域專家是個很迷人的目標,不過這之前,重點在於面對問題時,是否總能抱持著「一定還有其他方式」的想法,像是除了1加到100這類的問題之外,你知道費式數列也可以用數學公式來解嗎?