# week 5 note

## 例題一
印出所有用'A', 'B'排列出的字串，長度為三
'AAA', 'AAB', 'ABA', 'ABB'....'BBB'

先仿照費氏數列，畫出下圖，印出類似的東西

* 圖裡面紅色9畫錯，是10

void f(char c) {
	cout << "in: " << c << ")\n";
	f('A');
	f('B');
	cout << "out: " << c << ")\n";
}

int main() {
    f('A');
    f('B');
}

> 問題： 會印出什麼？遇到什麼狀況
> A: 沒有終止條件

加上“第幾個字母”這個變數(lev)

void f(int lev, char c) {
	if(lev == 4) return;
	cout << "in: (" << lev << ", " << c << ")\n";
	f(lev + 1, 'A');
	f(lev + 1, 'B');
	cout << "out: (" << lev << ", " << c << ")\n";
}

int main() {
    f(1, 'A');
    f(1, 'B');
}

印出排列:
每次進入f就把字母加到vector尾端
每次出function就把字母從vector尾端拿出來
可以配合圖觀察

vector<char> v;
void f(int lev, char c) {
	
	cout << "in: (" << lev << ", " << c << ")\n";
	v.push_back(c);
	
	if(lev == 3) {
		for(char t : v) cout << t << ' ';
		cout << endl;
		
		cout << "out: (" << lev << ", " << c << ")\n";
		v.pop_back();
		
		return;
	}
	
	f(lev + 1, 'A');
	f(lev + 1, 'B');
	
	cout << "out: (" << lev << ", " << c << ")\n";
	v.pop_back();
}

vector<int> v;
v.push_back(10); // v = {10}
v.pop_back(); v = {}

## 數字全排列
給你數字1~n，從n個數字挑m個出來做排列，由小到大
例如:
n=3, m=2
1 2
1 3
2 3

int n = 10, m = 5;
vector<int> v;
void f(int lev, int x) {
	// in
	v.push_back(x);
	if(lev == m) {
		for(int i = 0; i < v.size(); i++) cout << v[i] << ' ';
		cout << endl;
		v.pop_back();
		return;
	}
	for(int i = x+1; i <= n; i++) {
		f(lev+1, i);
	}
//	if(1 > x) f(lev+1, 1);
//	if(2 > x) f(lev+1, 2);
//	if(3 > x) f(lev+1, 3);
//	if(4 > x) f(lev+1, 4);
	v.pop_back();
}

練習!
寫出下圖從node 0開始的dfs序


0(in) 1(in) 3(in) 3(out) 2(in) 6(in) 5(in) 5(out) 4(in) 4(out) 6(out) 2(out) 1(out) 0(out)