Skip to main content

1.2 遞迴應用

輾轉相除法

輾轉相除法在求兩數的最大公因數(GCD)，是一種非常有效率的方法，我們不需要分別找出每個質因數，就可以找到其最大公因數，以下以求330, 210兩數的最大公因數為例

步驟 圖片 解釋
1 將330,210兩數併排寫下，並用3條直線做分隔
2 用 330 除以 210，得到商為 1，餘數為 120。(重點是那個餘數)
3 用前一次的除數(210)除以前一次的餘數(120)，得到商為1，餘數為 90。
4 用前一次的除數(120)除以前一次的餘數(90)，得到商為 1，餘數為 30。
5 用前一次的除數(90)除以前一次的餘數(30)，得到商為 3，餘數為 0。當餘數為 0 時，除數30 即為 330 和 210 的最大公因數。
  • 如果以橫式來呈現除法過程會更容易看出輾轉的過程
  • 被除數=除數$\times$商+餘數
    1. $330 = 210 \times 1 + 120$
    2. $210 = 120 \times + 90$
    3. $120 = 90 \times 1 + 30$
    4. $90 = 30 \times 3 + 0$
  • 可以發現以下性質
    1. 前一回合的除數是下一回合的被除數。
    2. 前一回合的餘數是下一回合的除數。
    3. 若餘數為 0，則該回合的除數即為最大公因數。
  • 最後，就可以藉由上述結果建立遞迴關係式 \[GCD(x, y)= \begin {cases} GCD(b, a % b) & \text{if }a% b!=0 \\ b & \text{if } a % b == 0\end{cases}\] \[GCD(x, y)= \begin {cases} F(x-1)+F(x-2)GCD(b, a % b) & \text{if }x>1 \\ 1 & \text{if } x = 1 \\ 2 & \text{if } x = 2\end{cases}\]
Back to top