# 最大公因數(GCD)
:::success
使用輾轉相除法，反覆計算到餘數為$0$為止，也稱為歐幾里得定理(Euclid's Algorithm)
:::
1. 定義:
$GCD(M,\ N)=\left\{
\begin{array}{c}
M\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ,\ n = 0 \\
GCD(N, M \% N), \ n \gt 0
\end{array}
\right.$
2. GCD遞迴運算
- $n = 0$，傳回$GCD = M$
- $n \gt 0$，傳回$GCD = (N, M\%N)$

3. 推導$GCD(3155, 2545)$的遞迴過程
$GCD(3155, 2545) \\
=GCD(2545, 3155\%2545) \\
=GCD(2545, 610) \\
=GCD(610, 2545\%610) \\
=GCD(610, 105) \\
=GCD(105, 610\%105)\\
=GCD(105, 85)\\
=GCD(85, 105\%85)\\
=GCD(85, 20)\\
=GCD(20, 85\%20)\\
=GCD(20, 5)
=GCD(5, 20\%5)\\
=GCD(5, 0)\\
=5$

## 構思
1. 遞迴結束條件(Stopping): $n = 0$傳回$GCD$值為$M$
2. 遞迴執行部分(Step): $n \gt 0$傳回$GCD(N, M\%N)$

### 參考程式

#include <iostream>

using namespace std;

int GCD_Recursive(int m,int n)
{
    if(!n) return m;
    else return GCD_Recursive(n,m%n);
}
int GCD_Loop(int m, int n)
{
    while(n){
        int r=m%n;
        m=n;
        n=r;
    }
    return m;
}
int main()
{
    int m, n;
    while(cin>>m>>n){
        cout<<"Recursive:"<<GCD_Recursive(m, n)<<"\n";
        cout<<"Loop:"<<GCD_Loop(m, n)<<"\n";
    }
    return 0;
}

# 巴斯卡三角形(Pascal's Triangle)

1. 定義:
$P(i,\ j)=\left\{
\begin{array}{c}
1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ,\ i = j\ \ or\ \ j = 0\\
P(i-1,\ j-1)+P(i-1,\ j), \ i \gt j
\end{array}
\right.$

2. Pascal's Triangle 遞迴運算
- $i = j\ \ or\ \ j = 0$，傳回$P(i,\ j) = 1$
- $i \gt j$，傳回$P(i-1,\ j-1)+P(i-1,\ j)$

3. 推導$P(4, 2)$的遞迴過程
$P(4, 2)\\
=P(3,1)+P(3,2)\\
=(P(2,0)+P(2,1))+P(3,2)\\
=(1+P(2,1))+P(3,2)\\
=(1+(P(1,0)+P(1,1))+P(3,2)\\
=(1+(1+1)+P(3,2)\\
=3+P(3, 2)\\
=3+(P(2, 1)+P(2, 2))\\
=3+((P(1, 0)+P(1,1))+P(2, 2))\\
=3+((1+1)+P(2, 2))\\
=3+(2+1)\\
=3+3\\
=6$
## 構思
1. 遞迴結束條件(Stopping): $i = j\ \ or\ \ j = 0$，傳回$P(i,\ j) = 1$
2. 遞迴執行部分(Step): $i \gt j$，傳回$P(i-1,\ j-1)+P(i-1,\ j)$