甚麼是演算法
廣義
演算法是解決某一問題的一步一步程序 (a step-by-step procedure for solving a problem)
狹義
演算法是一個由一些步驟所構成的集合,依循這些步驟得以解決數學問題或完成計算機進程 (a set of steps that are followed in order to solve a mathematical problem or to complete a computer process)
流程圖 (flowchart) 是演算法
計算機科學 嚴謹定義
由有限(finite)步驟(step)所構成的集合,依照給定輸入(input)依序執行每個明確(definite)且有效(effective) 的步驟,以便能夠解決特定的問題;而步驟的執行必定會終止(terminate),並產生輸出(output) 。
特性
- 指定輸入(input):演算法必須指定輸入,可以由外界輸入0 個、1 個或多個資料。
- 具有輸出(output):演算法必定有至少1 個以上的輸出。
- 有限性(finiteness):演算法步驟的個數必須是有限的,而且步驟的執行最後會終止(terminate)。
- 明確性(definiteness):演算法的每個步驟都必須是明確(definite) 而不含糊的(unambiguous)。
- 有效性(effectiveness):演算法的每個步驟必須是有效的(effective) 或說是可行的(feasible)。
如何表示演算法 Example : Euclidean algorithm
流程圖,Pseudo Code
自然語言
歐幾里德演算法:
問題:給定二個正整數m及n,找出此二數的最大公因數GCD(也就是能同時整除m及n的最大正整數)
解法:
步驟1.[找出餘數] 求出m除以n的餘數,並記錄於r。
步驟2.[餘數為0嗎?] 如果r=0則停止,輸出n為GCD。
步驟3.[換被除數與除數] 設定m=n,n=r,並跳至步驟1。
C++
#include <iostream>
using namespace std;
int EuclidGCD(int m, int n){
int r=m%n;
while (r!=0) {
m=n;
n=r;
r=m%n;
}
return n;
}
int main() {
int m,n;
cout<<"請輸入二個正整數m與n: ";
cin>>m>>n;
cout<<"整數"<<m<<"與整數"<<n<<"的最大公因數為"<<EuclidGCD(m,n);
}