# 如何實作演算法

當我們已經學會了程式語言的基本觀念，接下來最重要的就是如何活用我們學過的東西，實際做出一個有用的程式，也就是設計並撰寫演算法。

由於計算機（computer、台灣俗稱電腦）的運作是非常簡單而原始的，對已經習慣高階和抽象化思考的人類來說，一開始無法立刻轉換思維去適應機器「這麼笨」的運作方式，當然會覺得困難。但只要經過適當的訓練，將腦袋調整一下，轉換立場站在計算機的角度來思考，就會比較容易寫出演算法。

第一步，我們要先知道自己到底想要做出什麼樣的程式，它是怎麼被使用的，以及會產生什麼樣的結果。之後，我們就要練習把每個具體細節都拆分出來，不斷的拆分、分解成一個個具體可行的數理和邏輯步驟，最終像拼圖一樣把它完整的拼出來，成為一個完整的程式。

對於初學者來說，即使變數、陣列、迴圈、條件判斷…甚至指標的觀念都知道，但要把這些知識串聯起來，實際撰寫一個演算法可能還是有點困難，不知從何下手。也就是說，雖然手邊的材料已經非常齊全了，但初學者還是不知道著手利用這些材料做出一盤好菜。

一般來說這沒有捷徑，只能透過不斷的嘗試錯誤、不斷練習，在跌跌撞撞中學習成長，最後變成高手。話雖這麼說，其實設計一個演算法還是有訣竅的，知道這些訣竅可以減輕新手在學習與成長過程中的痛苦，更快進入適應期。

#### 這邊我們介紹三個訣竅，可幫助初學者更快掌握設計演算法的技巧。
_________________________________________________________
第一個訣竅就是：從下而上（Bottom - UP）設計策略。
嘗試把人腦變的單純，不要用人腦習以為常的觀點來思考事情，而是要模擬計算機（computer）處理事情的方法。依據這種思維模式，很自然的會這樣想：「不要一次看到事情的全貌，要把問題切割成一個一個具體的數理步驟，將解決步驟條列式的以數學和邏輯的語言寫出來」。

Bottom – UP程式設計策略的精隨就是：遇到不會解的問題時，就不要嘗試一次全部解決，先找出「解決部分問題」的方法，先做會做的部分，接著再用「相同的方法、相似的程式片段」，依序把剩下的問題用暴力式的方式寫出來。這時候的暴力程式雖然不夠優雅，但確實可以正確的解決問題。

之後，我們就可以引入變數和迴圈…等觀念，用變數取代重複的敘述中「不同的部分」，然後再用迴圈取代重複的敘述中「相同的部分」，來優化暴力程式。

舉個最簡單的例子，例如要在螢幕上顯示出三次「Hello!」，我們先以最直接、最暴力的方式來寫：

int i;           // 宣告一個變數i，作為我們的「計數器」，想像一下「一個口令一個動作」

i = 1 ;                    // 第一次，設定i的初始值為1
printf（”Hello!\n”）;

i = 2 ;                    // 第二次，i的值被更新為2
printf（”Hello!\n”）;      
	
i = 3 ;                    // 第三次，i的值被更新為3
printf（”Hello!\n”）;

這樣的程式可以正常執行沒有問題，但感覺就是不夠漂亮。我們觀察這個程式，發現作為計數器的變數i都是以1遞增，並且到i = 3時停止執行，而「printf（”Hello!\n”）;」這段完全相同的程式碼被重複了3次 … 這不就是一個for迴圈嗎？因此我們可以優化此段程式碼如下：

for（i=1 ; i <= 3 ; i++）{
 printf（”Hello!\n”）; }

由於每執行一次for迴圈，就會把i的值 + 1（i++運算子），所以當執行到i = 4時，因為不滿足i <= 3這個條件了，就會跳出for迴圈的{ }區塊。若我們底下已經沒有其他的程式碼，程式就停止執行。

我們也可以做一點變化，達到一樣的效果：

for（i = 6 ; i >= 2 ; i = i - 2）{
printf（”Hello!\n”）; } 

i從初始值6開始，每次– 2，到i = 0時因為不滿足i >= 2這個條件了，所以跳出迴圈的{ }區塊，最終也是一樣執行三次。當然for迴圈（）之內的計數器能夠用很多不同的變化寫法，但我們不需要每次都這樣做腦力激盪來把事情變得複雜，一般使用最普通、最容易理解的寫法就好了，讓我們能把心力放在更重要的演算法設計上。

這個例子可能過於簡單，無法很好的表現出Bottom – UP程式設計策略的精隨，我們再看一個例子，例如計算 1 + 2 + 3 + 4 + … 10：

int i ;       // 宣告整數型態的變數i
int sum = 0;  // 宣告並初始化整數型態的變數sum（總和）的值為0

i = 1
sum = sum + i     // 把sum的值 + 1之後，再將運算後的新值存入sum

i = 2
sum = 前一次的結果 + i 

i = 3
sum = 前一次的結果 + i 

	… … … … … … 

i = 10
sum = 前一次的結果 + i 

程式碼中，「前一次的結果」是什麼呢？就是變數sum呀（因為變數sum的值不斷被更新為前一次運算後的新值，也就是說變數sum的值是會不斷被累加的）。所以，我們把中文「前一次的結果」以變數sum取代，再將程式碼改寫如下：

int i ;   
int sum = 0; 

i = 1
sum = sum + i    

i = 2
sum = sum + i 

i = 3
sum = sum + i 

	… … … … … … 

i = 10
sum = sum + i 

暴力程式寫出來了，然後我們再用變數取代「不同的部分」，並且用迴圈取代「相同的部分」，將暴力程式做優化：

int i ;  
int sum = 0;  

for （i = 0 ; i <= 10 ; i++ ）{
		sum = sum + i ; }

這樣，我們就把這題的演算法，用一個很漂亮且精簡的方式給實作出來了。事實上這邊的程式碼是要放在main（）函數的{ }區塊裡的，但我們先省略它，把關注焦點放在設計演算法的訣竅。

若我們今天要計算「1 + 3 + 5 + 7 + 9」，甚至更多奇數的總和，只要把for迴圈的執行條件改變一下就好，如這題就是改成：

int i ;  
int sum = 0;  

for （i = 1 ; i <= 9 ; i = i + 2 ）{
		sum = sum + i ; }

最後我們再來看一個經典的範例：在螢幕上顯示（印出）九九乘法表。假設我們現在根本不知從哪裡開始著手，沒關係，依照Bottom – UP程式策略的精神，我們先做會做的部分就好，例如寫2 * 2 = 4 ~ 2 * 9 = 18 …，這個總沒有問題吧。所以我們就先寫出：

2 * 2 = 4
2 * 3 = 6
2 * 4 = 8
… … …
2 * 9 = 18

3 * 2 = 6
3 * 3 = 9
3 * 4 = 12
… … …
3 * 9 = 27

4 * 2 = 8
4 * 3 = 12
4 * 4 = 16
… … …
4 * 9 = 36

… 繼續往下寫，直到9 * 9 = 81。

 註：1乘以任何數都還是那個數，沒什麼意思，所以我們從2 x 2開始寫就好。

注意到了嗎，我們可以把前面的乘數以一個變數取代（例如i），後面的乘數以另一個變數取代（例如j），所以其實我們的演算法就是計算「i * j」，並讓i的值從2 ~ 9做變化，j的值也是從2 ~ 9做變化。

為了進一步釐清觀念，應用Bottom – UP程式策略的精神，我們先把暴力程式寫出來。

i = 2;
j = 2;
printf（”%1d x %1d = %2d”,i,j,i*j）

i = 2;
j = 3;
printf（”%1d x %1d = %2d”,i,j,i*j）

i = 2;
j = 4;
printf（”%1d x %1d = %2d”,i,j,i*j）

… … … … … … … … …

i = 2;
j = 9;
printf（”%1d x %1d = %2d”,i,j,i*j）

這邊我們只寫了2 x 2到2 x 9的暴力程式，但其他部分的暴力程式，讀者應該也可以很輕鬆地寫出來。之後，在暴力程式中，我們以變數取代「不同的部分」，並且用迴圈取代「相同的部分」，將暴力程式做優化，最終結果如下：

int i , j ;     // 宣告兩個整數變數i和j，因為C語言沒辦法在迴圈的（）內才宣告變數

	for（i = 2; i <= 9 ; i++）{  
		for（j = 2; j <= 9 ; j++）{  
		printf（”%1d x %1d = %2d”,i,j,i*j）; }  
	printf（”\n”）;       // 印完一整列之後要換列 
      } 

 注意最外層for迴圈的藍底範圍是包含它{ }之內全部的範圍，只是沒有表示出來。這裡省略main（）{ }不寫，讓讀者專注在演算法的設計上。

### 執行結果：

我們完成了一個使用兩層「巢狀for迴圈」，在螢幕上顯示（印出）九九乘法表的程式了，演算法也就這短短幾列而已。

理論上，for迴圈和while迴圈可以互相代換，效果是等價的。例如要顯示出九九乘法表可以使用兩個巢狀for迴圈，也可以使用while迴圈，理論上都做的出來，就看你怎麼去寫。當然，不同迴圈寫出來的程式碼會有所不同，所以還是要依照需求和場合選擇適當的寫法，才能有效簡化程式，增加可讀性。
__________________________________________________________

再補充一個例子：找出陣列（array）中最大的元素的值（value）。使用Bottom – UP程式策略，第一步先寫出暴力程式（ar是array的縮寫）：

int max ;                         // 宣告一個整數變數max，來放置陣列的最大值
int ar[5] = {6,15,95,98,23};      // 宣告一個整數陣列並作初始化

max = ar[0] ;                    // 先把陣列第一個元素的值放置到變數max中 

/* 演算法設計：其他陣列元素的值依序「挑戰」現有陣列元素的值，若比它大就取代它，如此最後變數max的值就會是最大值 */

if（ar[1] > max）               
	max = ar[1] ; 

if（ar[2] > max）
	max = ar[2] ; 

if（ar[3] > max）
	max = ar[3] ; 

if（ar[4] > max）
	max = ar[4] ; 

用變數取代敘述中「不同的部分」，將之變成相同：

int max ;                         
int ar[5] = {6,15,95,98,23};      

max = ar[0] ;                     

i = 1;
if（ar[i] > max）
	max = ar[i] ; 

i = 2;
if（ar[i] > max）
	max = ar[i] ; 

i = 3;
if（ar[i] > max）
	max = ar[i] ; 

i = 4;
if（ar[i] > max）
	max = ar[i] ; 

最後，我們再用迴圈取代完全相同的重複敘述，如下：

int max ;                         
int ar[5] = {6,15,95,98,23};      

max = ar[0] ;                     

for（i = 1 ; i <= 4 ; i++）{
if（ar[i] > max）
		 max = ar[i] ;   }

這樣就完成了這個程式，這邊也省略main（）{ }，讓關注焦點集中在演算法設計和程式策略上。

對於初學者來說，透過這種方式，可以快速理解程式的運作邏輯，熟練之後就不需要每次都這樣按部就班一步一步的做了，可以直接寫出有變數和迴圈的程式碼，直接寫出程式。

-----------------------------------------------------------------------------------------

第二個訣竅就是：由上而下（UP - Bottom）設計策略。
第一個訣竅是由下而上，而與之對應的第二個訣竅，就是由上而下，故稱為UP - Bottom。

UP – Bottom程式設計策略有兩個步驟：
1. 寫出解決問題的「最外層迴圈」敘述，再依序向內逐步寫出迴圈，必要時可以先用中文作為虛擬碼，並以工作變數描述需要被重複執行的工作。
2. 逐步將迴圈內的虛擬碼轉換成實際的C語言程式碼，必要時使用「直線方程式」描述工作變數與迴圈變數之間的關係。

 註：工作變數、迴圈變數（計數器）、或者另一個常聽到的旗標變數（flag），其實也都是一般的變數而已，只是方便做出變數應用情境上的區別，便於我們理解與使用。

這裡我們舉一個「印出圖形」的例子，應用UP – Bottom程式設計策略的精隨。例如要在螢幕上顯示（印出）以下的圖形：

*
***
*****
*******
*********

一開始我們不知道如何著手，於是依照UP – Bottom程式設計策略的精神，先想想看如何寫出解決問題的「最外層迴圈」敘述，也就是「印出一列訊息後換列，共印出五列」。這樣的迴圈蠻簡單的，如下：

int i ;                       // 因為C語言無法在迴圈的（）之內才宣告變數

for（i = 1 ; i <= 5 ; i++）{
		第一列印出1個 * 符號;        
        換列;
        第二列印出3個 * 符號; 
        換列;
… … … 
第五列印出9個 * 符號; 
        換列;
    }

外迴圈和虛擬碼都寫出來了，我們再來想想如何把中文的虛擬碼轉換成C語言。由於每一列印出的 * 號不固定，因此我們以一個整數變數x來代表每列 * 符號的個數，為了便於理解與使用，我們把x特稱為工作變數。

我們把最外層的迴圈變數i，和工作變數x的關係寫出來：

i = 1 x = 1 *
i = 2 x = 3 ***
i = 3 x = 5 *****
i = 4 x = 7 *******
i = 5 x = 9 *********

有沒有發現i和x剛好是直線方程式的關係？這裡我們回想一下國中數學，設 x = a*i + b，並且任取兩組x和i的值代進去解聯立方程式，解出a = 2, b = -1，因此得出x = 2*i–1。

有了這個資訊，我們再把剛才虛擬碼的部分更進一步寫清楚：

for（i = 1 ; i <= 5 ; i++）{
		每一列印出x個（即2*i-1個）星號
（印出後）換行;
    }

現在就只差把灰色的虛擬碼寫成真正的程式語言，這也不難，「每一列印出（2*i-1）個星號」這一列虛擬碼，只要用一個for迴圈就行了，如下：

int j ;

	for（j = 1 ; j <= 2*i–1 ; j++）{
		printf（”*”）;           
}

 註：印出x個星號，就是印出一個星號x次的意思，而此處我們把x代換為 2*i–1。

而之後的「換行」更簡單，就是「printf（”\n”）;」而已。接下來，我們把這兩列虛擬碼，以真正的程式碼取代回去，這個印圖形的演算法就完成了：

int i , j;

for（i = 1 ; i <= 5 ; i++）{ 
        for（j = 1 ; j <= 2*i–1 ; j++）{ 
            printf（”*”）; } 
printf（”\n”）; 
 }

 注意最外層for迴圈的藍底範圍是包含它{ }之內全部的範圍，只是沒有表示出來。這裡一樣省略main（）{ }不寫，讓讀者專注在演算法的設計上。

我們再來看一個複雜一點的例子，寫程式在螢幕上顯示以下圖形：

*
****
*******
**********
*************

此圖形的規律是，由下往上看，第五列有13個 * 號，第四列有10個 * 號，並在前面有2個空格；第三列有7個 * 號，並在前面有4個空格（相較於第五列而言） … 依此類推。所以從第一列到第五列的（空格數量 , * 號數量）依序為：
（8 , 1）
（6 , 4）
（4 , 7）
（2 , 10）
（0 , 13）

這個題目的解法和剛才很類似，一樣是在每一列印出不同數量的 * 號，但每一列的前面多了幾個不同數量的空白字元（占1 byte），所以圖形的排版有些不同。其實它的演算法和剛才差不多，只是現在多了空白字元要處理。這題演算法的訣竅是，先把每列空白字元的數量設為變數x，然後再把每一列 * 符號的數量設為變數y。而我們還要為了空白字元，再多加上一條直線方程式，至於迴圈變數仍是i。

以下是這題的演算法，詳細的推導過程就不再寫了。

int i , j ;

for（i = 0 ; i <=4 ; i++）{              // 先寫出最外層的for迴圈，設定其迴圈變數為i

	for（j = 1 ; j <= -2*i + 8 ; j++）   // 每一列空白字元數量和迴圈變數i的直線方程式
		{ printf（” ”）; }             // 印出空白字元（即空格，也占1 byte）

	for（j = 1 ; j <= 3*i + 1 ; j++）    // 每一列 * 號數量和迴圈變數i的直線方程式
		{ printf（”*”）; }             // 印出 * 號 

	printf（”\n”）;                   // 最外層for迴圈的敘述，每執行一次迴圈就換一列
}

 注意最外層for迴圈的藍底範圍是包含它{ }之內全部的範圍，只是沒有表示出來。另外，這邊一樣省略不寫main（）{ }。

最後再用一個輕鬆的例子說明Top – Down程式設計策略的精神。例如我們要計算全校學生穿球鞋到校的人數，我們先不要管寫程式，一般人接到這個任務，會一大早站在校門口，拿個一個計數器，先把計數器的值歸零。當開始上學時，一旦學生進來並且有穿球鞋，你就按一下計數器，直到全校學生都進到學校為止，最後看計數器的數值是多少。

我們以Top – Down程式設計策略的精神，先以虛擬碼寫出外迴圈：

把計數器的值歸零 ;
	for（每一位學生）
	    { if（穿球鞋） 
計數器 + 1 }
	顯示計數器上的值 ;

比虛擬碼更接近程式語言的寫法，如下：
int counter = 0 ;
	for（每一位學生）
	    { if（穿球鞋） 
counter++ }
	printf（”穿球鞋到校的學生人數一共有 %d 個 \n”,counter） ;

這只是舉例讓讀者了解觀念，實際上因為很難簡單的把「穿球鞋」轉化成數理語言，會牽涉到電腦視覺、圖像處理演算法，甚至是大數據、人工智慧（AI） … 非常複雜，所以到此為止。從這個例子中，讀者也可以順便了解到電腦和人腦之間的差異，以及哪些事情是人腦可以輕易完成而電腦（計算機）卻很難做到；而哪些事情又是人腦很難做到，而電腦（計算機）卻可以輕易完成的。

-----------------------------------------------------------------------------------------

第三個訣竅就是：綜合前兩個。
無論是Bottom – UP或是UP – Bottom兩種方法，只是思維方式的不同，最後還是可以得到一樣的答案，就算程式碼略有不同也無所謂。我們也可以把這兩種思維方式綜合起來應用，成為第三種訣竅，其步驟是：

1. 分析問題，會寫多少就先寫多少敘述，不會寫的部分就先用中文虛擬碼表示，這是UP –Bottom策略的精神。
2. 用Bottom – UP策略把中文虛擬碼翻譯成C語言，如果程式碼足夠多，或有這個價值，就把它寫成函數的型式。
3. 如果仍然有無法一次解決的問題（或子問題），就先「簡化問題」，先從最簡單的狀況開始著手，再修改簡化問題的程式碼，或加以擴充，來解決原始問題。

只要熟練前面兩種訣竅，第三個自然水到渠成。

不過訣竅終究只是訣竅，只是輔助的技巧而已，還是要搭配許多練習和實戰經驗，下苦功去實作過，還要不停吸收新知，不停的精進自己的技巧，才能真正學好演算法。