認識演算法

演算法(Algorithm)是在有限的步驟之內，提供明確的法則，求出問題正確答案的程序。它可以是一種方法、法則或者程序，讓資料可按照預先設計的方式處理。

演算法設計原則

1. 輸入：演算法可以包含零個或一個以上的輸入。
2. 輸出：演算法至少須產生一個輸出。
3. 明確性：電腦程式是根據指令一步一步地執行，沒有臨機應變能力，因此演算法的每一個步驟，都必須清楚、明確地交代。
4. 有效性：演算法的每一步驟都須是一可行的運算，也須能在有限的時間內完成。
5. 有限性：演算法須在有限的次數內解決問題，而結束工作。

演算法設計策略

常見的演算法策略有數種，在此介紹其中五種。

分治法（Divide-and-Conquer）

分治法（Divide-and-Conquer），是將大問題拆解成小問題，分頭解決得到答案，最後再彙總變成大問題的解答。

遞迴(recursion)是實作這個策略的重要方法。

隨堂練習

1. 階乘的計算

階乘的基本定義如下

• n == 0, n! = 1
• n > 0, n! = n x (n-1)!, n正整數
  請設計程式計算 4! 為何？

參考程式碼如下：

def factorial(i):
    if i == 0:
        return 1
    else:
        return( i * factorial(i-1))

print(factorial(4))

2. 費伯納西數列
   費伯納西數列（Fibonacci Polynomial）的基本定義如下：

• n=1, F_n=0
• n=2, F_n=1
• n>2, F_n=F_n-1+F_n-2

n為正整數

請撰寫程式計算F(11)為何？

參考程式碼如下：

def fib(n):
    if n==1:
        return 0
    elif n==2:
        return 1
    else:
        return(fib(n-1)+fib(n-2))

print(fib(11))

動態規劃法

動態規劃（Dynamic Programming），類似Divide and Conquer，一個問題的答案來相依於子問題，常用來解決最佳解的問題。

和Divide and Conquer不同的地方在於，動態規劃多使用了memoization的機制，將處理過的子問題答案記錄下來，避免重複計算，因此在子問題重疊的時候應該使用動態規劃，可以解決重覆計算並保留遞迴思考的優點。

隨堂練習

使用動態規劃法，來解決費伯納西數列問題。

費伯納西數列（Fibonacci Polynomial）的基本定義如下：

• n=1, F_n=0
• n=2, F_n=1
• n>2, F_n=F_n-1+F_n-2

n為正整數

請撰寫程式計算F(11)為何？

參考程式碼如下：
使用一個List，把解過的問題答案記錄起來。

FibArray = [None]*1000 #結果暫存區

def fibonacci(n):
	result = FibArray[n]
	if result == None:
		if n==1:
			return 0
		elif n==2:
			return 1
		else:
			result = fibonacci(n-1)+fibonacci(n-2)
			
		FibArray[n] = result
	return result

print(fibonacci(5))

暴力演算法(Brute force)

又稱列舉法(Enumeration)，和分治法完全不同的概念，就是將問題的可能的走向都全部列出來，列舉出所有可能的答案。

當資料量不大的時候，反而是最直接解決問題的策略。

範例

如果有一個密碼系統，是只能輸入四位數字，那麼直接從0000依序嘗試到9999，是最直接的方法。

for i in range(10000):
    print(str(i).zfill(4))

不過千萬別用在一般手機，品牌廠商都設置了相對應的機制，例如嘗試幾次錯誤就會鎖起來不再讓使用者輸入密碼。

回溯法(Backtracking)

回溯法（Backtracking）是列舉法的優化策略之一。

主要用於搜尋，運用遞迴的方式進行，當發現搜尋過程中，不滿足求解條件時，就回溯返回，嘗試別的路徑，避免無效搜索。

最常見的應用範例是「老鼠走迷宮」
假設有一個迷宮盒子，老鼠想試圖從入口走到出口，但必須依循三個原則：
a. 一次只能走一格
b. 遇到牆無法走時，退回一步找其他道路
c. 走過的路不會走第二次

根據以上原則，依序舉列出所有可能的路線。

經典問題：

• N皇后問題
• 騎士走棋盤

貪心法則(Greedy Method)

貪心法則(Greedy Method)的原理：在對問題求解時，判斷當下最好的選擇

過程：

• 把求解的問題分成若干個子問題
• 對每一子問題求解，得到子問題的區域性最優解
• 把子問題的解區域性最優解合成原來解問題的一個解

隨堂練習

換鈔的最佳策略：請設計程式，列出使用最少數量的貨幣去進行換零錢。

想法：本題最佳的換鈔策略，是從大面額的貨幣開始換

步驟如下：

1. 從最大面額貨幣開始，判斷找錢金額是否大於該面額
2. 如果大於該面額，則進行除法，確認要提供的該面額的張數
3. 取找錢金額相除該面額的餘數，則可以得到尚未找的錢，繼續進行換鈔

參考程式碼：

def change(origin):
  money = [1000, 500, 100, 50, 10, 5, 1] 
  
  #最佳選擇：最大面額開始嘗試
  for i in range(0, len(money),1): 
    if origin >= money[i] :  
      print(f"{money[i]}*{int(origin / money[i])}")
      origin = origin % money[i]

change(965)

演算法成效衡量

• 時間複雜度：執行次數與執行時間
• 空間複雜度：使用的記憶體空間

總結

tags: 資料結構與演算法