<style>
.reveal .slides {
text-align: left;
font-size:30px;
}
</style>
## Struct and Recursive
----
* 結構體 (struct)
* 遞迴 (全域變數)
----
## Struct
* 性質
* 用法
* 實作
----
## 性質
大家應該或多或少有聽說過物件導向，那所謂物件導向是class裡面會有私有成員(private) : 不被其他函式所使用 以及 公開成員(public) : 可被其他函數所調用
struct跟class常常被拿來做比較，跟class的差別就是裡面的元素都是public的，也不需要給他額外的宣告，只需要在裡面宣告型態類別就好
struct就可以宣告結構，結構就是可以自訂不同的資料型態綑在一起，他們就會是一個共同的整體，裡面的變數是塞什麼都可以，像是上禮拜學到的STL那些容器等，也都可以放進去
----
## 用法
具體的用法有兩種，可以把它整體看成一個大的自訂型態，然後分別有兩種宣告方式。
```cpp=
struct node{
int a,b,c;
}v[MXN];
```
```cpp=
struct node{
int a,b,c;
};
int main(){
node v;
}
```
----
struct有非常多常用的用法，因為它可以把大部分的東西都包在一起，尤其是之後學習到資料結構時，將大部分的函式也包進去是一個很常見的用法，就相當於你自訂了一種新的資料型態叫做node。
example : BIT(樹狀數組) , MaxClique , Flow ...
而且它也能大幅縮短很多問題的實作碼量。
----
## 實作
假設我們有很多筆資料，可能是學號，姓名等，然後我們需要對它排序
```txt
5
4 LeeShoW
5 Jakao
2 leeshow
3 LeeShow
1 Leeshow
```
那我們要怎麼快速的對其進行排序呢?
----
也就是說 當你同一筆資料有許多維度的時候，你就會需要使用struct把他們綑成一團，使得程式實作方便，另外排序當然也可以自己宣告，以下是自己宣告的做法 :
```cpp=
struct node{
int a,b,c; //對它的1 2 3維度去排序
}v[MXN];
bool cmp(node x,node y){
if(x.a!=y.a) return x.a<y.a;
else if(x.b!=y.b) return x.b<y.b;
else return x.c<y.c;
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>v[i].a>>v[i].b>>v[i].c;
sort(v,v+n,cmp);
}
```
----
那如果是在裡面放函式呢?
```cpp=
struct student{
int id;
string name;
void new_student(int now,string str){
for(int i = 0; i<str.size(); i++){
str[i] = toupper(str[i]);
}
cout<<now<<" "<<str<<"\n";
}
}Function;
int main(){
string str;
int cnt;
cin>>cnt>>str;
Function.new_student(cnt,str);
}
```
就要在呼叫它的時候增加call的名稱
----
那當然也可以用pair去處理
```cpp=
struct student{
pair<int,string> p;
void new_student(pair<int,string> p){
for(int i = 0; i<p.second.size(); i++){
p.second[i] = toupper(p.second[i]);
}
cout<<p.first<<" "<<p.second<<"\n";
}
}Class;
int main(){
string str;
int cnt;
cin>>cnt>>str;
Class.new_student({cnt,str});
}
```
所以當然裡面想要放什麼都可以。我們也可以在裡面加入各式各樣的函式，端看你想要return什麼，然後再去作出許多方便的操作，以後上到模板的時候就會有很多example，當然網路上也有許多參考資料。
---
## 全域變數,遞迴
----
## 全域變數
----
全域變數就是指在每一個函數中都可以使用的變數，且值是互通的，也不需要在額外宣告一次。而與全域變數相對的就是區域變數，它只能夠在每個宣告過它的函式中進行使用。
----
那一開始先實作一些簡單的例子
```cpp
int MAX(int x,int y){
if(x>y) return x;
else return y;
}
int main(){
int a,b;
cin>>a>>b;
cout<<MAX(a,b);
}
```
這個應該是大家會的東西
----
那如果函式沒有要傳遞東西的話，當然也可以這樣寫
```cpp
int a,b;
int MAX(){
if(a>b) return a;
else return b;
}
int main(){
cin>>a>>b;
cout<<MAX();
}
```
這樣就是使得 $a$ 和 $b$ 變成每個函式都可以使用的變數
----
那在APCS觀念題裡面，有許許多多類似這樣的題目，詢問你輸出是多少，由此可知，不要重複命名也是很重要的 point !
```cpp=
int a = 6;
void print(){
cout << a << endl;
}
int main(){
int a = 3;
cout << a << endl;
print();
}
```
----
其中全域變數的順序很重要，因為考慮到它是個別獨立的區塊，所以你當前函式需要用到的其他函式，需要放在當前函式的前面，以下為例子。
```cpp=
bool cmp(node x,node y){
return x.a<y.a;
}
struct node{
int a,b,c;
}v[MXN];
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>v[i].a>>v[i].b>>v[i].c;
sort(v,v+n,cmp);
}
```
----
若把陣列開在全域變數，相比把陣列開在區域變數裡，可以開的更大，所以好習慣就是把陣列開在全域。
因為他還會自動幫你清零，若開在區域他的初始值會亂跳，因為開在區域變數會變成動態宣告陣列。
----
## 枚舉
----
## 窮舉排列(不會出現重複數字)
----
如果我們今天要求出 1-2-3-4-5 的全排列呢(按照字典序)?
- next_permutation
- 自己實作
那因為今天是窮舉的課程，而且也不是每種情況都可以用next_permutation，所以我們就實作看看
----
首先我們會需要儲存進陣列 (array) 然後排序，這樣不管數字是多少都可以排序它。
然後要生成一個用來記錄答案的陣列 (ans)
接下來就要記錄每一個位置是否出現過這個數字 (vis)，而當目前衍生的遍歷完後，要記得回朔。
然後理所當然的要從第一項開始遍歷
----
首先是讀入以及排序，然後呼叫遞迴函數
```cpp=
int arr[N]={};
int ans[N]={};
bool vis[N]={};
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>arr[i];
sort(arr+1,arr+n+1); //排序
dfs(1); //呼叫遞迴函數
}
```
----
第二步呼叫函數後，會需要做的事情是檢查每一項是否有跑過，沒跑過的話就增加到當前傳遞的ans數組。
```cpp=
for(int i=1;i<=n;i++){
if(!vis[i]){ // 檢查當前這項是否在ans裡
ans[index]=arr[i]; // 將當前這項加入ans裡
vis[i]=1; // 標記為有在裡面
dfs(index+1); // 呼叫下一個遞迴
ans[index]=0; // 把答案移除
vis[i]=0; // 這個遞迴結束後移除標記
}
}
```
----
那千萬不能忘記我們需要設下終止條件，那就是當目前的index已經超過n的範圍的時候，我們就不需要再繼續遍歷了，並且輸出答案
```cpp=
if(index>n){ // 超過陣列範圍
for(int i=1;i<=n;i++){ // 輸出答案
cout<<ans[i]<<" \n"[i==n];
}
}
```
----
若是對遞迴的過程不了解，可以在每次遞迴時嘗試輸出index和vis數組了解它到底發生甚麼事情
```cpp=
cout<<index<<"\n";
for(int i=1;i<=n;i++){
cout<<vis[i]<<" \n"[i==n];
}
```
----
會發現它其實就是對vis的每一項去作0/1的組合，只是順序不一樣
*vis的輸出狀態
----
```cpp
#include<algorithm>
#include<iostream>
using namespace std;
const int N=1e5+5;
int arr[N]={};
int ans[N]={};
bool vis[N]={};
int n;
void dfs(int index){
if(index>n){ // 超過陣列範圍
for(int i=1;i<=n;i++){ // 輸出答案
cout<<ans[i]<<" \n"[i==n];
}
}
for(int i=1;i<=n;i++){
if(!vis[i]){ // 檢查當前這項是否在ans裡
ans[index]=arr[i]; // 將當前這項加入ans裡
vis[i]=1; // 標記為有在裡面
dfs(index+1); // 呼叫下一個遞迴
ans[index]=0; // 把答案移除
vis[i]=0; // 這個遞迴結束後移除標記
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>arr[i];
sort(arr+1,arr+n+1); //排序
dfs(1); //呼叫遞迴函數
}
```
----
## - 窮舉排列(會出現重複數字)
----
如果會出現重複數字，那剛剛那種枚舉方式就會錯，因為我們會需要避免index一樣但是數字重複的情況，我們需要避免在同一個位置填入相同的數字。
----
所以我們要做的其實就是紀錄上一個出現的數字，避免在最新遞迴到的那一個重複出現就好 !
```cpp=
void dfs(int index){
int pre=0; // 每次都要初始化最後出現的數字
}
```
----
在判斷的地方加上當前這個數字是否與前一個相同
```cpp=
for(int i=1;i<=n;i++){
if(!vis[i]&&arr[i]!=pre){ // 沒出現過，且與前一個不相同
pre=arr[i]; // 因為採用了，所以取代掉上一個數字
vis[i]=1;
ans[index]=arr[i];
dfs(index+1);
vis[i]=0;
ans[index]=0;
}
}
```
----
```cpp
#include<algorithm>
#include<iostream>
using namespace std;
const int N=1e5+5;
int arr[N]={};
int ans[N]={};
bool vis[N]={};
int n;
void dfs(int index){
int pre=0;
if(index>n){ // 超過陣列範圍
for(int i=1;i<=n;i++){ // 輸出答案
cout<<ans[i]<<" \n"[i==n];
}
}
for(int i=1;i<=n;i++){
if(!vis[i]&&arr[i]!=pre){ // 沒出現過，且與前一個不相同
pre=arr[i]; // 因為採用了，所以取代掉上一個數字
vis[i]=1;
ans[index]=arr[i];
dfs(index+1);
vis[i]=0;
ans[index]=0;
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>arr[i];
sort(arr+1,arr+n+1); //排序
dfs(1); //呼叫遞迴函數
}
```
----
## 枚舉子集
----
對於一個集合，枚舉出它所有的子集(subset)，那這就其實也不難，因為對於每一個vis來說，就只有取和不取兩種方式。
自然而然也是一樣的起手式，就只是少了一個ans紀錄答案，因為可以直接依照vis的布林值去輸出答案。
```cpp=
int arr[N]={};
bool vis[N]={};
int n;
void dfs(int index){
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>arr[i];
sort(arr+1,arr+n+1);
dfs(1);
}
```
----
第一步也是輸入，排序，呼叫函式
第二步理所當然是跑每一項，繼續呼叫遞迴函式
第三步就是回朔，其中也不能忘記在抵達n後要輸出答案
----
第一步就經典起手
```cpp=
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>arr[i];
sort(arr+1,arr+n+1);
dfs(1);
}
```
----
然後跑每一項的時候繼續呼叫遞迴函式，且在結束後要記得回朔。
```cpp=
vis[index]=1;
dfs(index+1);
vis[index]=0;
dfs(index+1);
```
----
最後在抵達上限的時候輸出
```cpp=
if(index>n){
for(int i=1;i<=n;i++){
if(vis[i]) cout<<arr[i]<<" ";
}
return;
}
```
----
```cpp
#include<algorithm>
#include<iostream>
using namespace std;
const int N=1e5+5;
int vis[N]={};
int arr[N]={};
int n;
void dfs(int index){
if(index>n){
for(int i=1;i<=n;i++){
if(vis[i]) cout<<arr[i]<<" ";
}
cout<<"\n";
return;
}
vis[index]=1;
dfs(index+1);
vis[index]=0;
dfs(index+1);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>arr[i];
sort(arr+1,arr+n+1);
dfs(1);
return 0;
}
```
----
## $n$ 個元素枚舉大小為 $k$ 的子集
其實只需要多傳一個參數，代表現在入隊的人有幾個。
$DFS(x,y)$ 表 現在的index $x$ 以及 現在已有 $y$ 個元素入隊
```cpp=
int main(){
cin>>n>>k;
if(k>n){
cout<<"-1\n";
return 0;
}
for(int i=1;i<=n;i++) cin>>arr[i];
sort(arr+1,arr+n+1);
dfs(1,0);
return 0;
}
```
----
實作內容 : 須注意的點是遞迴函數傳遞的內容以及遞迴函數的停止條件，不然很容易無窮迴圈。
```cpp=
void dfs(int index,int now){
if(now>k||index>n+1) return; // 因為只有剛好恰等於k時輸出
if(now==k){ // 恰等於時輸出
for(int i=1;i<=n;i++){
if(vis[i]) cout<<arr[i]<<" ";
}
cout<<"\n";
return;
}
vis[index]=1;
dfs(index+1,now+1); // 若有選取 則index+1且元素入隊所以now+1
vis[index]=0; // 回朔
dfs(index+1,now); // 沒有則只+index
}
```
----
```cpp
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
const int N=1e5+5;
int vis[N]={};
int arr[N]={};
int n,k;
void dfs(int index,int now){
if(now>k||index>n+1) return; // 因為只有剛好恰等於k時輸出
if(now==k){ // 恰等於時輸出
for(int i=1;i<=n;i++){
if(vis[i]) cout<<arr[i]<<" ";
}
cout<<"\n";
return;
}
vis[index]=1;
dfs(index+1,now+1); // 若有選取 則index+1且元素入隊所以now+1
vis[index]=0; // 回朔
dfs(index+1,now); // 沒有則只+index
}
int main(){
cin>>n>>k;
if(k>n){
cout<<"-1\n";
return 0;
}
for(int i=1;i<=n;i++) cin>>arr[i];
sort(arr+1,arr+n+1);
dfs(1,0);
return 0;
}
```
---
# 回顧上週題目
{"slideOptions":"{\"transition\":\"fade;\"}","title":"Struct and Recursive","contributors":"[{\"id\":\"e4a3af8b-860c-46a0-96f1-558667fdcf41\",\"add\":9779,\"del\":1232},{\"id\":\"19f09ccf-6b99-452f-971f-955cfc1657f3\",\"add\":420,\"del\":6}]","description":"結構體 (struct)"}