tags: tgirc早修book

經典遞迴題型

本篇整理了幾種遞迴的經典題型。

最大公因數

最大公因數通常是利用 輾轉相除法 的方式來實作。每次讓 a 與 b 兩者交替互相取餘數。
以下是 Top-down 的作法。

int GCD(int a, int b){
    if(b == 0){
        return a;
    }
    
    return GCD(b, a%b);
}

Bottom-up的作法則是如下：

while(b != 0){
    int temp = a;
    a = b;
    b = temp % a;
}

cout << a;

費波納契數列

費波納契數列，又稱費式數列。
該數列第零項為 0，第一、二項為 1，之後每一項都是其前兩項的和，也就是如下：

f(n) = 1                (n = 1 or 2)
f(n) = f(n-1) + f(n-2)  (n > 2)

Top-down 的作法如下：

int fib(int n){
    if( n==0)                return 0;
    else if( n==1 || n==2 )  return 1;
    else                     return f(n-1) + f(n-2);
}

Bottom-up的作法則是如下，一般會建立一個陣列來儲存所有值：

int arr[n];
arr[0]=0;
arr[1]=1; arr[2]=1;

for(int i=3; i<n; i++){
    arr[n] = arr[n-1] + arr[n-2];
}

cout << arr[n];

字元排列組合

若有 n 個字元，輸出其所有排列方式。

假設今天的字元有 a, b, c 三個，把它的所有排列方式表示為 (a, b, c)，那它的所有排列方式就是：

(a,b,c) = [a + (b,c)] + [b + (a,c)] + [a + (b,c)]

也就是說，讓所有字元各擔任一次字串開頭，後面接剩下的字元的所有排列方式，而剩下的字元的所有排列方式又可用相同方式處理。

直到剩下一個字元時，單一個字元的排列方式只有一種，此時即可停止。

string str;

void Perm(int i, int n){
    if(i == n){
        cout << str << "\n";
    }
    else{
        for(int j=i; j<n; j++){
            swap(str[i], str[j]); //把j字元換到開頭
            Perm(i+1, n);         //剩下的字元作排列組合
            swap(str[i], str[j]); //把j字元放回原位
        }
    }
}

河內塔

河內塔是一個大盤子在下，小盤子在上，總共三根柱子可以放盤子的裝置。
目標是將 A 柱子上的所有盤子按照順序移到 C 柱子上，一次只能移一個盤子，且大盤子不能放在小盤子上，按照順序輸出移動步驟。

首先觀察只有 2 個盤子的情況，先將小盤子由 A 移到 B，再把大盤子由 B 移到 C ，最後把小盤子由 B 移到 C。

其實可以想成是把最大的盤子以上的小盤子全部移到 B 柱子上，再把最底下的移到 C 柱子，最後把 B 柱子的盤子全部移到 C 柱子上。

此時我們把 A 稱為起始柱，B 為中間柱作為轉運站，C 則是終點柱。所有的 n 層塔都可拆為以下步驟：

1. 將 起始柱 上 n-1 個盤子移到 中間柱
2. 將 起始柱 最底下剩餘的 1 個盤子移到 終點柱
3. 將 中間柱 上 n-1 個盤子移到 終點柱

而 n-1 個盤子的移動方式，又可按照這個步驟執行下去。
移動至剩下一個盤子時，就只需將那個盤子直接由起點柱移到終點柱。

流程圖

void Hanoi(int n, char A, char B, char C){
    //把n個盤子由A柱子移至C柱子
    //A為起點柱，B為中間柱，C為終點柱
    
    if( n==1 ){
        cout << A << " -> " << C;
    }
    //如果只有一個盤子，就直接由起點柱移到終點柱
    
    else{
        Hanoi(n-1, A, C, B);
        //將n-1個盤子由起點柱移到中間柱
        Hanoi(1, A, B, C);
        //將最底下的1個盤子由起點柱移到終點柱
        Hanoi(n-1, B, A, C);
        //將n-1個盤子由中間柱移到終點柱
    }
}