# 遞迴與窮舉

## 遞迴定義

遞迴是一種程式設計中常見的思維模式，其定義為函式(又稱副程式)以直接或間接呼叫自己。以縮小問題規模做為解題思維。遞迴並不容易理解，卻是後續許多演算法與資料結構的基礎，例如：分治、動態規劃、線段樹。所以遞迴絕對是在學完基礎語法後很重要的環節。以下我們有一個教學上很常見的範例。

### P_1_1階乘

這個大家應該聽過，常見的解法會是用for迴圈從1跑到n，然後把全部都乘起來，然若用遞迴的思想解題。我們可以將其分解如下式
$f(n)=1×2×…×n$
這也就可以將$f(n)$表示為$f(n-1)×n$，因$f(n-1)=1×2×…×(n-1)$。用$f(3)$為例，它的計算過程如下
1. $f(3)=3×f(2)$
2. $f(2)=2×f(1)$
3. $f(1)=1$

以此回推

4. $f(2)=2×1=2$
5. $f(3)=3×2=6$

最後得到答案為6，(某些題目會卡時間，若用迴圈較快的話盡量用迴圈)，程式碼看起來很容易。如下

int f(int n){
    if(n==1) return 1;
    else return f(n-1)*n;
}

---

沒有人規定只能有一個遞迴項，也可以有兩個，甚至更多，不過數字一大就要跑很久了。來看下一個範例：費氏數列

### P_1_2費氏數列

費氏數列原本的定義就是遞迴式了。

$f(1)=1, f(2)=1$
$f(n)=f(n-1)+f(n-2), n>2$

若直接照著此式實做的話就會像這個樣子

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

用這樣的方式實作複雜度接近$O(1.6^n)$，因為每個節點都有一大一小的分支，看的出來其實會有許多重複且不必要的計算，這題依舊是迴圈較佔優勢。以下是迴圈解

int ff[50];

int f(int n){
    ff[1]=ff[2]=1;
    for(int i=3;i<=20;++i){
        ff[i]=ff[i-1]+ff[i-2];
    }
    return ff[n];
}

後面會提到一些不用遞迴反而會比較慢的題目，不過多數題目還是用迴圈比較好。

## 一切演算法的基礎-窮舉
窮舉法是最基本的演算法，用白話文說的話就是列出所有可能性並一一檢查。以下是一個範例。

### P-1-3 三角形

#### 題目敘述 :
有$n$支木棒，第$i$支木棒的長度為$a_i$。我們想從這些棒子中挑出三支，組成三角形。
求總共有幾種挑法。

#### 輸入說明 :
輸入第一行有一個數字 $n$ ，下一行有 $n$ 個數字代表$a_1,a_2 ... a_n$。
$n \leq 100 , a_i \leq 100000$

#### 輸出說明 :
輸出有幾種挑法

#### 範例輸入 1 :

4
2 3 4 5

#### 範例輸出 1 :

3

#### 解答 :
我們可以用三層迴圈找出所有可能性，再判斷解答是否合理。

#include<bits/stdc++.h>
using namespace std;

int a[105];
int main(){
    //IO 加速
    ios::sync_with_stdio(0);cin.tie(0);

    int n;
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>a[i];
    }
    int ans=0;//組合數
    for(int i=0;i<n-2;++i){
        for(int j=i+1;j<n-1;++j){
            for(int k=j+1;k<n;++k){
                int total=a[i]+a[j]+a[k];    //周長
                int mx=max({a[i],a[j],a[k]});//求最大值
                int other=total-mx;          //另外兩邊和

                if(other>mx){
                    ans++;
                }
            }
        }
    }

    cout<<ans;//記得輸出解答
}

## 用遞迴窮舉

在一些情況下，用迴圈的方式不容易進行窮舉，這時候除了想到用其他演算法之外，遞迴就可能是一個好選擇。即便不一定可以拿到所有分數，在競賽的時候有不失為一個好的~~偷分~~技巧。以下為一個例題。

### 井字遊戲(110東區模擬賽)

#### 題目敘述 :

熟悉博士為了改變未來所以想要預測未來，雖然他知道世界上許多元素現在的狀態，但是他的魔法還不足以運算出所有的可能性，於是他決定從基礎的井字遊戲開始訓練。熟悉博士認為如果能夠預測出井字遊戲的每一種結果，距離預測未來也不遠了吧！井字遊戲作為一個國際雙人競技項目而家喻戶曉，其規則如下：

1. 給予一個大小為 3 × 3 的棋盤，棋盤每格的初始狀態皆為空，且只能夠被填入一個符號。
2. 兩位玩家分別使用 'o'、'x'，輪流把自己所屬的符號填入棋盤中。
3. 當任一玩家的三個符號在棋盤上連成一條橫、直、或是斜線，該玩家獲勝並遊戲結束。
4. 如果棋盤每一格都已被填入符號，遊戲結束且兩玩家平手。

你身為熟悉博士的頂級隨從 Maowu，不只上知天文下知地理還是個頂尖的 Coder，而熟悉博士有時對自己的預測結果感到不安，於是他請你幫助他驗證答案。

熟悉博士會給你井字遊戲目前的狀態，假設雙方輪流隨機把符號填入，請你告訴熟悉博士所有可能的結果中，使用 'o' 一方贏的次數、使用 'x' 一方贏的次數、以及雙方平手的次數。

#### 輸入說明 :
輸入總共 3 行，每行有 3 個以空白隔開的字元表示給定棋盤的狀態，'-' 表示該格尚未被填入，'o'、'x' 則表示該格已被該方填入。保證輸入棋盤為 'o' 先手且盤面合法。

#### 輸出說明 :
輸出共 1 行，包含 3 個整數，分別代表 'o' 一方贏的次數、'x' 一方贏的次數、以及雙方平手的次數，數字之間以空格隔開。

#### 範例輸入 1 :

o - x
x o o
- o x

#### 範例輸出 1 :

1 0 1

#### 範例輸入 2 :

x o o
- - -
x x o

#### 範例輸出 2 :

2 1 2

#### 解答 :

#include<bits/stdc++.h>
using namespace std;

char mp[5][5];
int ct[5];

//判斷盤面局勢
int check(){
    for(int i=0;i<3;++i){
        // o-- -o- --o
        // o-- -o- --o
        // o-- -o- --o
        if(mp[i][0]==mp[i][1] && mp[i][1]==mp[i][2]){
            if(mp[i][0]=='o'){
                return 0;
            }else if(mp[i][0]=='x'){
                return 1;
            }
        }

        // ooo --- ---
        // --- ooo ---
        // --- --- ooo
        if(mp[0][i]==mp[1][i] && mp[1][i]==mp[2][i]){
            if(mp[0][i]=='o'){
                return 0;
            }else if(mp[0][i]=='x'){
                return 1;
            }
        }
    }
    
    // o-- 
    // -o-
    // --o
    if(mp[0][0]==mp[1][1] && mp[1][1]==mp[2][2]){
        if(mp[0][0]=='o'){
            return 0;
        }else if(mp[0][0]=='x'){
            return 1;
        }
    }

    // --o
    // -o-
    // o--
    if(mp[0][2]==mp[1][1] && mp[1][1]==mp[2][0]){
        if(mp[0][2]=='o'){
            return 0;
        }else if(mp[0][2]=='x'){
            return 1;
        }
    }

    //is tie?
    bool isfull=true;
    for(int i=0;i<3;++i){
        for(int j=0;j<3;++j){
            if(mp[i][j]=='-'){
                isfull=false;
            }
        }
    }

    if(isfull){
        return 2;
    }else{
        return -1;
    }
}

void ttt(int step){
    int ck=check();
    if(ck!=-1){
        ct[ck]++;
        return;
    }

    for(int i=0;i<3;++i){
        for(int k=0;k<3;++k){
            if(mp[i][k]=='-'){
                //奇數次下一個人是'x'
                if(step&1){
                    mp[i][k]='x';
                }else{
                    mp[i][k]='o';
                }

                ttt(step+1);
                mp[i][k]='-';
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int step=0;
    for(int i=0;i<3;++i){
        for(int j=0;j<3;++j){
            cin>>mp[i][j];
            if(mp[i][j]!='-') step++;
        }
    }

    ttt(step);
    for(int i=0;i<3;++i){
        cout<<ct[i]<<" ";
    }
    cout<<"\n";
}

## 習題

### AP325

###### tags: `APCS與競賽入門`