---
# System prepended metadata

title: '一、遞迴:'

---

資工三甲_10713226_王子楢筆記


# 一、遞迴:



- 遞迴（Recursion），是指在函式中使用函式自身的方法。

- 遞迴函式必須有終止條件，才能被計算。

- 遞迴可用來解決複雜且重複性高的問題，透過遞迴可以將複雜問題拆解成很多個細小的步驟

 Ex: 階層
 ![](https://i.imgur.com/y6ZCQqf.png)
 
```
 #include<iostream>
using namespace std;

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

int main(){
    int n;
    while( cin >> n ){
        cout << f(n) << endl;
    }

    return 0;
}
```

範例:Fibonacci

![](https://i.imgur.com/V7n3S2H.png)

```
#include <iostream>

using namespace std;
int ans =0;

int fibo(int a){

    if ( a == 1 || a == 2)  return 1;
    if ( a >= 3){

       return fibo( a -1) + fibo(a -2);
    }
}

int main(){

    int a;
    while( cin >> a)  cout << "答案: " << fibo(a) << endl;
    

    return 0;
}


```

EX:河內塔

![](https://i.imgur.com/mDePig1.gif)

```
#include <iostream>

using namespace std;
int moved = 0 ;
//                 起點              終點
void hanoi( int n, char a, char b, char c){
     if ( n == 1){
          cout << "Move sheet from " << a << " to " << c << "\n"  ;
          moved++ ;
     }

     else{
          hanoi(n-1, a, c, b); // 把最下面以外的盤子從A移到B
          hanoi(1, a, b, c); // 把最下面盤子從A移到C
          hanoi(n-1, b, a, c); // 把其他盤子從B移到C
     }

}

int main(){
    int n = 0 ;
    char a, b, c ;
    cin >> n ;
    cout << "A: 3 2 1 \n";
    cout << "B:\n";
    cout << "C:\n";
    hanoi( n, 'A', 'B', 'C');
    cout << "\nTotal moved "  << moved << " steps\n\n" ;


}


```

# 二:資料抽象化:

#### 物件導向:

​       物件導向的基本概念是「透過物件來模擬任何事物」。

物件本身包含了「資料」和「方法」，如果以真實世界的事物來說，「資料」就是事物的特質、資訊或屬性，而「方法」就是該事物與其他事物互動的方式。

#### 三大特性(封裝、繼承、多型):

**封裝 (Encapsulation)**:

即是將物件內部的資料隱藏起來，只能透過物件本身所提供的介面(interface)取得物件內部屬性或者方法，這樣可以防止重要數據洩漏

**繼承 (Inheritance)**:

類別可以透過繼承其他類別來獲得其屬性以及方法，可減少程式碼量。

**多型 (Polymorphism)**

簡單來說就是相同名稱的方法(Method)，**多個相同名稱的方法，傳入不同的參數，會執行不同的敘述****。**多型(Polymorphism)則包含多載(Overloading)和複寫(Overriding)。



**抽象資料型別**

在電腦科學中，抽象資料型別(Abstract Data Type)是一種**理論上的觀念**，它主要是用於設計與分析演算法、資料結構及軟體系統當中，而一個抽象資料型別通常定義了**資料型別(values)和操作方式(operations)**，舉例來說，整數(`Integer`)就是一個抽象資料型別，他定義了在這個ADT底下，其資料型別(value)為整數(-2, -1, 0, 1, 2等)且操作方式(operation)有加、減、乘、除等。此外，抽象資料型別的這個概念並沒有限定於特定的程式語言，換言之，不同的程式語言都可以**實作**抽象資料型別的**概念**，而且單一種ADT也可以透過**多種不同的方式**來進行實作，例如`Bit vectors`或`Hexadecimal vectors`這兩種資料結構都是`Integer`的實作(Implementation)。

### 抽象資料型別

#### 1. Set

數據不重複 

每個key(鍵)都是唯一的

可以插入或刪除但不能更改且數據有排序(預設升序)

##### 常見操作:

st.insert() :插入數據

st.begin( ):  返回指向set第一個元素的迭代器

st.end()  :  返回指向末尾的迭代器。

st.empty() 如果set為空則返回true

st.erase() 刪除數據

```
#include <iostream>
#include <set>
using namespace std;

int main(){
    set <int> st;
    for( int i = 0; i < 5; i++){
        st.insert( i+1);
    }
    std::set<int>::iterator it = st.begin();

    for( it; it != st.end(); it++){
        cout << *it << " ";
    }
    return 0;
}

```
#### 2. Dictionary/Map

key, value 為鍵值對的資料結構

ex:

map<int, string> mp ={

{1,"E04"},

{2,"e04"},

{3,"c8c8"}

};

map.find(3): 如果此鍵(key)不存在map裡面則會引用map.end() 

常見操作:

mp.begin() 返回指向map第一個元素的迭代器

mp.end() 返回指向map最後一個元素的迭代器

mp.empty()查詢是否為空 若為空返回true

mp.size() 返回map中的數據數量

mp.insert() 插入數據

mp.emplace() : 創造新元素並插入map

mp.clear() :刪除所有元素

遍歷map的各種方法:
```
#include <iostream>
#include<map>
using namespace std;

int main(){
    map <int, string> mp={

    {1,"幹的好啊"},{2,"大明王朝"},{3,"慘絕人寰"}

    };


    for( int i =0; i < mp.size(); i++){
        cout << i << ": " <<  mp[i] << "\n";
    }

    cout << "\n";
    cout << "迭代器:\n";
    map<int, string>::iterator it =mp.begin();
    for( it =mp.begin(); it!=mp.end(); it++){
        cout << it -> first << " " << it -> second ;
    }


    cout << "\n第三種\n";
    for ( it =mp.begin(); it!= mp.end(); it++) {
        cout << (*it).first << " : " << (*it).second << "\n";
    }
    return 0;
}
```
#### 3. Stack

堆疊(棧):先進後出

![](https://i.imgur.com/yhNxOPz.png)


宣告:
```
#include<stack>
#include<iostream>


stack <int> stk;
int x =3;
stk.push(x);

```

##### 常用操作:

stk.empty() 查詢是否為空 空則返回true

stk.size():查詢stack的大小

stk.push(): 在stack頂部插入元素

stk.pop():stack頂部彈出(刪除)一個數據


#### 4. Queue

queue就是隊列，就像排隊一樣，先進先出

![](https://i.imgur.com/sHtO32y.png)

常用操作:

```
#include <iostream>
#include<queue>

using namespace std;

int main(){
    queue <int>q;
    int i;
    cin >> i;
    q.push(i); // 在末尾插入一個元素
    q.back(); // 返回最後一個元素
    q.front(); // 返回第一個元素
    q.size(); // 返回queue中元素個數
    q.empty(); // 查詢是否是空的
    return 0;
}

```

#### 6. Priority Queue


與Queue相同，但是每個Elements都會自帶一個『優先度』(priority)

在新增Element(Enqueue)時，與Queue的的方式相同

但在取出Element(Dequeue)時，會尋找**優先度最高**的Element先行取出



priority_queue<int>  p;默認為最大的值優先取出

priority_queue<int, vector<int>, less<int>>  p; 同上一行

priority_queue<int,vector<int>,greater<int>>  p;設為最小的優先取出



p.push(x); 插入元素

p.pop();從priority_queue最前面取出元素 並刪除此元素

p.top(); 讀取最上面元素 但不刪除此元素

p.empty(); 檢查是否是空的 空的回復true 否則回傳false

p.size();回傳priority_queue目前儲存元素的數量
    

# 三.鏈結串列

Linked list(連結串列)是一種常見的資料結構，其使用**node(節點)**來記錄、表示、儲存資料(data)，並利用每個node中的**pointer**指向下一個node，藉此將多個node串連起來，形成Linked list，並以`NULL`來代表Linked list的終點。

    
![](https://i.imgur.com/078ztHV.png)


**優點**：

1. 新增/刪除資料較Array簡單，只要對node(所有與欲新增/刪除的node有pointer

​       相連的node)調整pointer即可，不需要如同Array搬動其餘元素。

​       

​       若要刪除特定node，或者在特定位置新增node，有可能需要先執行O(NN)的「搜尋」。

2. Linked list的資料數量可以是動態的，不像Array會有**resize**的問題。



**缺點**：

- 因為Linked list沒有**index**，若要找到特定node，需要從頭遍歷開始找起。
- 需要額外的記憶體空間來儲存**pointer**。

**適用時機**：

1. 無法預期資料數量時，使用Linked list就沒有**resize**的問題。
2. 需要頻繁地新增/刪除資料時。
3. 不需要快速查詢資料。

# 四.遞迴解題

前序:把運算子放到最前面 

ex: + 1 1, * 3 8

中序: 運算子在中間

ex: 2 + 5, 5 * 9

後序:運算子放在最後面

ex: 3 5 +, 4 8 *

#### 回溯法

回溯法的處理方式就像窮舉法，將所有可能的路徑都窮舉出來，接著每條岔路都派人走下去。

但如果把每條路都確實走過，這樣的作法的時間複雜度相當高，所以回溯法有時可以使用剪枝 的技巧提高效率，不用將所有解法都窮舉出來。

回溯法大部份用來解決廣義的搜索問題

回溯法適合以遞迴  來解
    
```
#include <iostream>
#include<vector>

vector<vector<int>> result;
void backtrack (路徑, 下一步選擇清單){
    if ( 終止條件 )
        result.add (路徑);
        return;
    for 下一步 in 選擇清單
        做選擇
        backtrack (路徑, 下一步選擇清單)
        撤銷選擇
} 
```

##### 八皇后問題
    
    
1. 每行每列恰好放一個皇后。我們可以逐行放，不用考慮橫向攻擊。
2. 使用回溯法：若當前步驟沒有合法選擇，則回到遞迴的上一層。
3. 判斷對角線的方式:同一條對角線的x+y值相同(左下右上)、x-y值相同(左上右下)。
4. 用 put[x] 表示第 x 行皇后的 y 位置。
5. 用 visited記錄所在的列、兩個對角線是否已有皇后。(i=0:列, i=1:左下右上, i=2:左上右下)(因x-y值會出現負值，所以要+n)

```
#include <iostream>
using namespace std;
int n, ans=0, put[100], visited[3][100];
void search(int now){
    if(now == n) ans++; //跑到最後一行了，代表這組解ok
    else for(int i=0; i<n; i++){
        if(!visited[0][i] && !visited[1][now+i] && !visited[2][now-i+n]){
            //比直的；比x+y對角線(x是now,y是i)；比x-y對角線(因為會出現負值所以+n)
            put[now] = i; //把第now行的皇后放在第i列
            visited[0][i] = visited[1][now+i] = visited[2][now-i+n] = 1;
            search(now+1);
            visited[0][i] = visited[1][now+i] = visited[2][now-i+n] = 0; //改回來
        }
    }
}
int main(){
    cin >> n;
    search(0);
    cout << ans << '\n';
} 
    
```

