# 認識演算法
`演算法(Algorithm)`是在有限的步驟之內，提供明確的法則，求出問題正確答案的程序。它可以是一種方法、法則或者程序，讓資料可按照預先設計的方式處理。
## 演算法設計原則
1. 輸入：演算法可以包含**零個或一個以上**的輸入。
2. 輸出：演算法**至少**須產生一個輸出。
3. 明確性：電腦程式是根據指令一步一步地執行，沒有臨機應變能力，因此演算法的每一個步驟，都必須清楚、明確地交代。
4. 有效性：演算法的每一步驟都須是一可行的運算，也須能在有限的時間內完成。
5. 有限性：演算法須在有限的次數內解決問題，而結束工作。
## 演算法設計策略
常見的演算法策略有數種，在此介紹其中五種。
### 分治法（Divide-and-Conquer）
`分治法（Divide-and-Conquer）`，是將大問題拆解成小問題，分頭解決得到答案，最後再彙總變成大問題的解答。
[`遞迴(recursion)`](https://hackmd.io/@howkii-studio/python_modulization/#recursion)是實作這個策略的重要方法。
#### 隨堂練習
1. 階乘的計算
階乘的基本定義如下
- n == 0, n! = 1
- n > 0, n! = n x (n-1)!, n正整數
請設計程式計算 **4!** 為何？
參考程式碼如下：
```python=
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)為何？
參考程式碼如下：
```python=
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`，把解過的問題答案記錄起來。
```python=
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，是最直接的方法。
```python=
for i in range(10000):
print(str(i).zfill(4))
```
不過千萬別用在一般手機，品牌廠商都設置了相對應的機制，例如嘗試幾次錯誤就會鎖起來不再讓使用者輸入密碼。
### 回溯法(Backtracking)
`回溯法（Backtracking）`是列舉法的優化策略之一。
主要用於搜尋，運用遞迴的方式進行，當發現搜尋過程中，不滿足求解條件時，就回溯返回，嘗試別的路徑，避免無效搜索。
最常見的應用範例是「老鼠走迷宮」
假設有一個迷宮盒子，老鼠想試圖從入口走到出口，但必須依循三個原則：
a. 一次只能走一格
b. 遇到牆無法走時，退回一步找其他道路
c. 走過的路不會走第二次
根據以上原則，依序舉列出所有可能的路線。
經典問題：
- N皇后問題
- 騎士走棋盤
### 貪心法則(Greedy Method)
`貪心法則(Greedy Method)`的原理：在對問題求解時，判斷當下最好的選擇
過程：
- 把求解的問題分成若干個子問題
- 對每一子問題求解，得到子問題的區域性**最優解**
- 把子問題的解區域性最優解合成原來解問題的一個解
#### 隨堂練習
換鈔的最佳策略：請設計程式，列出使用最少數量的貨幣去進行換零錢。
> 想法：**本題最佳的換鈔策略，是從大面額的貨幣開始換**
步驟如下：
1. 從最大面額貨幣開始，判斷找錢金額是否大於該面額
2. 如果大於該面額，則進行除法，確認要提供的該面額的張數
3. 取找錢金額相除該面額的餘數，則可以得到尚未找的錢，繼續進行換鈔
參考程式碼：
```python=
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: `資料結構與演算法`
Sign in with Wallet
Connect another wallet