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}\]
  • 遞迴函數程式碼
#include<iostream>
using namespace std;
int gcd(int a, int b)
{
    if(a % b == 0) return b;
    return gcd(b, a % b);
}
int main()
{
    int a, b;
    cin >> a >> b;
    int ans = gcd(a, b);
    cout << ans << '\n';
    return 0;
}
  • Ex104輾轉相除法練習：網址

河內塔問題

問題介紹

典型的三圓盤河內塔，以下為規則

  • 一次只能移動一個圓盤
  • 任何時刻，大圓盤不能在小圓盤上面
  • 所有圓盤都要從A柱移到C柱

拆解問題

  • 一個圓盤：直接將圓盤從A移到C即可

  • 兩個圓盤：在兩個圓盤中，需要將中間B柱當成緩衝區，須將最上面那一個圓盤先放置緩衝區，才可將最大的圓盤移至C柱

  • 在此，發現了一個規律，在底層圓盤移動前，上方圓盤必須先全部搬到緩衝區

  • 下一步，可建立一個函數move(discs, from, buffer, to)，discs為我們須將$1~discs$由from移到to

  • 換句話說，當$discs=1$時，代表不用在乎buffer直接將目前的盤子從from移動到to即可

  • 當 $n=1$ 時

    • move(1, A, , C)將1由A放置C
    • 完成

  • 當 $n=2$ 時

    • move(2, A, B, C)
      • move(1, A, , B)
      • 將在A柱中最下方圓盤移到C柱
      • move(1, B, , C)

  • 當 $n = 3$ 時(上到下編號1、2、3)

    • move(3, A, B, C)
      • move(2, A, C, B)
        • move(1, A, , C)
        • 將2號從A柱移到B柱
        • move(1, C, , B)
      • 將3號圓盤從A移至C
      • move(2, B, A, C)
        • move(1, B, , A)
        • 將2號柱從B柱移到C柱
        • move(1, A, , C)
    • 總結：若要將1~3由A移到C，要先將1~2由A移到B，接下來將3從A移到C，再將1~2由B移到C

  • 藉由上方關係，可利用程式寫成一函數，程式碼如下

    void move(int discs, char from, char buffer, char to) 
{
    if(discs==0)
        return;
    move(discs-1, from , to, buffer);
    printf("move disc %d from %c to %c\n", discs, from, to);
    move(discs-1, buffer, from, to);
 }

  • Ex104河內塔：題目連結

快速冪

快速冪為快速計算$x^y$的方法，通常這個數字會很大，超過整數變數的範圍，所以會額外給你一個$p$，代表要對這個數字取$p$的餘數。換句話說，也就是給定$x, y, p$，要計算$x^y(\% p)$的結果。

  • Ex105快速冪
    • 題目連結
    • 最直觀的做法就是直接使用for迴圈暴力乘法，如以下程式碼
    #include<iostream>
using namespace std;
int main()
{
    int x, y, p;
    cin >> x >> y >> p;
    int ans = 1;
    for(int i = 0; i < y; i++) {
        ans = (ans * x) % p;
    }
    cout << ans << '\n';
    return 0;
}
    • 若$y=10^9$，這樣會導致程式超時，可以利用一些概念，優化程式，設計出只要$\log _2 x$次乘法的方法，以下是他的遞迴關係式 \[F(x, y, p)= \begin {cases} (F(x, y / 2, p) \% p \times F(x, y / 2, p) \% p) \% p & \text{if }x\% 2=0 \\ (F(x, y - 1, p) \% p \times x) \% p & \text{if } x\% 2=1\end{cases}\]
    • 快速冪程式碼
    long long exp(long long a, long long b, long long N)
{
    if(b == 0) return 1;
    if(b & 1) return ((exp(a, b - 1) % N) * a) % N;
    else return ((exp(a, b / 2) % N) * (exp(a, b / 2) % N)) % N;
}
Back to top