資工三甲_10713226_王子楢筆記
# 一、遞迴:
- 遞迴（Recursion），是指在函式中使用函式自身的方法。
- 遞迴函式必須有終止條件，才能被計算。
- 遞迴可用來解決複雜且重複性高的問題，透過遞迴可以將複雜問題拆解成很多個細小的步驟
Ex: 階層
```
#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
```
#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:河內塔
```
#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
堆疊(棧):先進後出
宣告:
```
#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就是隊列，就像排隊一樣，先進先出
常用操作:
```
#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的終點。
**優點**：
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';
}
```
Sign in with Wallet
Connect another wallet