# CPP Lecture3
- __學習++陣列++/++字串++、++函式與遞迴++、++const 保留字++__
- __`string` 和 `char[]` 怎麼用？ 差別在哪？__
- __函式如何宣告、使用？ 遞迴又是什麼？__
- __保留字是什麼？ `const` 有什麼功用？__
---
#### 📌 陣列（Array）
<br/>
1. **陣列** 是一組++相同型別++的++變數集合++。
2. 每個元素在記憶體中是++連續存放++的，
因此可以快速存取特定索引位置的元素。
3. 陣列的++大小必須固定++，不能動態擴展。
4. 陣列中元素++索引從 0 開始++ （index = 0）。
> ➣ **如果使用 `STL` 提供的 `<vector>` 結構 是支援動態分配的**
---
### 📜 陣列圖解
---
#### 🛈 陣列宣告及初始化
<br/>
- 以`整數型別`來宣告/初始化陣列：
```cpp[]
int arr1[5]; // 宣告一個大小 5 的整數陣列 元素皆為未初始化的「隨機值」
int arr2[6] = {0, 1, 2, 3, 4, 5}; // 含完整初始化
int arr3[6] = {0, 1, 2, 3}; // 不完整初始化，沒初始化到的元素值？
int arr4[] = {10, 20, 30, 40}; // 不指定大小，C++ 自動推斷大小為 4
```
- 存取（取值）、更動陣列元素：
```cpp[]
int arr[3] = {5, 10, 15};
cout << arr[0] << " "; // 陣列 arr 的第0個元素為 5
arr[1] = 1;
cout << arr[1] << " "; // 陣列 arr 的第1個元素變為 1
cout << arr[2] << " "; // 陣列 arr 的第2 個元素還是 15
cout << arr[3] << " "; // 輸出 ??? (編譯器不會報錯喔！)
cout << endl;
```
---
#### ➰ 迭代陣列中元素 - 範圍內取值
<br/>
- ++範圍內++迭代：
```cpp[]
int arr[5] = {1, 2, 3, 4, 5};
for (int i = 0; i < 5; i++) cout << arr[i] << " ";
cout << endl; // 輸出：1 2 3 4 5
```
```cpp[]
int arr[5] = {1, 2, 3};
for (int i = 0; i < 5; i++) cout << arr[i] << " ";
cout << endl; // 輸出：1 2 3 0 0
```
```cpp[]
int arr[5];
for (int i = 0; i < 5; i++) cout << arr[i] << " ";
cout << endl; // 輸出：? ? ? ? 0
```
為何會有這樣的現象呢（有零有亂數）❓
---
#### ➰ 迭代陣列中元素 - 範圍外取值
<br/>
- 迭代到++範圍外++：
```cpp[]
int arr[5] = {1, 2, 3, 4, 5};
for (int i = 0; i < 8; i++) cout << arr[i] << " ";
cout << endl; // 輸出：1 2 3 4 5 0 ? ?
```
```cpp[]
int arr[5] = {1, 2, 3};
for (int i = 0; i < 8; i++) cout << arr[i] << " ";
cout << endl; // 輸出：1 2 3 0 0 0 ? ?
```
```cpp[]
int arr[5];
for (int i = 0; i < 8; i++) cout << arr[i] << " ";
cout << endl; // 輸出：? ? ? ? 0 0 ? ?
```
<br/>
所以可見陣列是 **連續的記憶體**
但我們++不能確定++範圍外接續的記憶體的內容
---
#### ➰ 迭代陣列中元素 - 更動元素值
<br/>
```cpp[]
int array[8];
for (int i = 0; i < 8; ++i) array[i] = i + 1;
for (int i = 0; i < 8; ++i) cout << array[i] << " ";
cout << endl;
// 輸出：1 2 3 4 5 6 7 8
```
```cpp[]
int array[8];
for (int i = 0; i < 8; i = i + 2)
array[i] = i + 1;
for (int i = 0; i < 8; ++i) cout << array[i] << " ";
cout << endl;
// 輸出：1 ? 3 ? 5 ? 7 ?
```
<br/>
可以看到沒有初始化 就算後續有賦值的動作
未定義的元素依然是 ++不可預期 （亂數）++ 並非 0
---
#### ➰ 迭代陣列中元素 - 大小設定謬誤 ⚠
<br/>
```cpp[]
int size = 7;
int arr[size];
for (int i = 0; i < size; i++) {
arr[i] = i * 2;
cout << arr[i] << " ";
}
cout << endl;
// 輸出：0 2 4 6 8 10 12 （沒有任何 issue）
```
```cpp[]
int size; // ⚠
int arr[size];
size = 7;
for (int i = 0; i < size; i++) {
arr[i] = i * 2;
cout << arr[i] << " ";
}
cout << endl;
// Error！ （這跟上面正常運作的差在哪裡？）
```
---
#### ⓘ 不同型態的陣列（宣告/初始化/大小）
```cpp[]
#include <iostream>
#include <string>
using namespace std;
int main() {
// 整數陣列
int int_arr[3] = {1, 2, 3};
int int_arr_size = sizeof(int_arr) / sizeof(int_arr[0]);
cout << "整數陣列陣列大小：" << int_arr_size << endl; // 3
// 長整數陣列
long long_arr[3] = {111111111, 222222222222, 3333333333};
int long_arr_size = sizeof(long_arr) / sizeof(long_arr[0]);
cout << "長整數陣列陣列大小：" << long_arr_size << endl; // 3
// 浮點數陣列
float float_arr[3] = {1.0, 2.0, 3.0};
double double_arr[3] = {1.01, 2.02, 3.03};
int float_arr_size = sizeof(float_arr) / sizeof(float_arr[0]);
int double_arr_size = sizeof(double_arr) / sizeof(double_arr[0]);
cout << "單精度浮點數陣列大小：" << float_arr_size << endl; // 3
cout << "雙精度浮點數陣列大小：" << double_arr_size << endl; // 3
// 布林陣列
bool bool_arr[3] = {true, false, true};
int bool_arr_size = sizeof(bool_arr) / sizeof(bool_arr[0]);
cout << "布林陣列大小：" << bool_arr_size << endl; // 3
// 字元陣列
char chr_arr[3] = {'a', '\n', '\0'}; // '\0' 字元陣列結尾符號
int chr_arr_size = sizeof(chr_arr) / sizeof(chr_arr[0]);
cout << "字元陣列大小：" << chr_arr_size << endl; // 3
// 字串陣列（需要 <string> 標頭檔）
string str_arr[3] = {"apple", "bubble", "candy"};
int str_arr_size = sizeof(str_arr) / sizeof(str_arr[0]);
cout << "字串陣列大小：" << str_arr_size << endl; // 3
return 0;
}
```
理論上每種型態都能以陣列儲存，但要注意：
- `char` 陣列記得確保 `'\0'` 結尾，否則可能導致非預期的行為（亂碼）。
- `string` 陣列是 ++`string` 類別的陣列++，每個元素都是一個 ++`string` 物件++，而==非== `char` 陣列。
---
### ⚔ 字元陣列 v.s. 字串
兩種對於 C++ 來說都是字串：
- C-style 字串 (`char[]`)
```cpp[]
char str1[] = "Hello";
cout << str1 << "\n"; // Hello
cout << sizeof(str1) / sizeof(char); // 長度為 6 !
```
- `char[]` 結尾會有一個 `null` 結尾字元 `'\0'`，用來++標記字串結束++
- 不支援 `+` 直接++連接字串++（不像 `string`）
- C++ `string` 類別（建議使用）
```cpp[]
string str2 = "Hello";
cout << str2 << ", " << str2.length() << endl; // Hello 5
```
- 支援 `.length()` 取得長度，以及許多方法
---
### 📝 小練習1 - 字元陣列
<br/>
請把以下`字元陣列`
所有元素的 ++ASCII CODE++ 加總：
- 模板：
```cpp[]
#include <iostream>
using namespace std;
int main() {
char list[] = { 'a', 'A', 'b', 'b', '.',
'\'', '\"', '\n', '\0'};
return 0;
}
```
:::spoiler ▼ 解答
```cpp[]
int sum = 0;
for (const auto& chr : list) sum += static_cast<int>(chr);
cout << sum << endl; // 487
```
:::
---
### 📝 小練習2 - 字串陣列
<br/>
請把以下`字串陣列`
所有元素中的每個字元的 ++ASCII CODE++ 加總：
- 模板：
```cpp[]
#include <iostream>
#include <string>
using namespace std;
int main() {
string list[] = {"apple", "ball", "candy"};
return 0;
}
```
:::spoiler ▼ 解答
```cpp[]
int sum = 0;
for (const auto& str : list)
for (const auto& chr : str) sum += static_cast<int>(chr);
cout << sum << endl; // 1468
```
:::
---
### ⛮ 基本字串處理1
- `substr(start, length=預設總長)` 取得子字串
```cpp[]
string s = "HelloWorld";
cout << s.substr(4) << endl; // "oWorld"
cout << s.substr(0, 5) << endl; // "Hello"
```
- `find(string)` 查找（子）字串
```cpp[]
string s = "hi, you and you";
cout << s.find("hi") << endl; // 0（回傳 hi" 的起始索引）
cout << s.find("you") << endl; // 4（回傳第一個 "you" 的起始索引）
cout << s.find("me") << endl; // ?（找不到，亂碼）
```
<br/>
- `replace(start, length, string)` 替換子字串
```cpp[]
string s = "Hello World";
s.replace(6, 5, "C++"); // 從索引 6 開始，長度 5，替換成 "C++"
cout << s << endl; // "Hello C++"
cout << s.length() << endl; // 長度變為 9
```
---
### ⛮ 基本字串處理2
- `append(string)` 附加字串
```cpp[]
string s = "Hello";
s.append(" World");
cout << s << endl; // "Hello World"
```
- `+` 加號來串接字串
```cpp[]
string s = "Hello";
s += " World";
cout << s << endl; // "Hello World"
```
<br/>
- `.size()` / `.length()` 取得字串大小
```cpp[]
string s = "This is a sentence";
cout << s.size() << endl; // 18
cout << s.length() << endl; // 18
```
---
### 📝 小練習3 - 字串處理（`string`）
請用學到範圍內的方法來達成字串反轉：
```
e.g: "hello" -> "olleh" 或是 "a" -> "a"
```
- 模板：
```cpp[]
#include <iostream>
#include <string>
using namespace std;
int main() {
string input; cin >> input; // input 已確保不會有空格
int len = input.length();
// 你的程式碼...
cout << input << endl; return 0;
}
```
:::spoiler ▼ 解答
```cpp[]
for (int i = 0; i < len / 2; ++i) {
char temp = input[i];
input[i] = input[len - 1 - i];
input[len - 1 - i] = temp;
}
```
:::
---
### 📝 小練習4 - 字串處理（`char[]`）
沒錯就跟上一題一樣 但是這次沒有 `<string>`：
```
e.g: "hello" -> "olleh" 或是 "a" -> "a"
```
- 模板：
```cpp[]
#include <iostream>
#define MAX_SIZE 101 // input 已確保不會超過長度 100
using namespace std;
int main() {
char input[MAX_SIZE]; cin >> input;
// 你的程式碼... int len = ?
cout << input << endl; return 0;
}
```
:::spoiler ▼ 解答
```cpp[]
int len = 0;
while (input[len++] != '\0'){} len -= 1;
for (int i = 0; i < len / 2; ++i) {
char temp = input[i];
input[i] = input[len - 1 - i];
input[len - 1 - i] = temp;
}
```
:::
---
### 📝 進階練習題（++Medium++）
（**_[LeetCode：Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)_**）
<br/>
給定一個字串，找出++最長++的`回文`子字串
```latex
example 1："babad" -> "bab" 是其最長的回文子字串，"aba" 也是
example 2："cbbd" -> "bb" 是其最長的回文子字串
```
> 如果一個字串正讀和反讀都一樣，那麼它就是`回文字串`。
> 💡提示：用 `substr()` 來提取子字串，然後檢查是否是回文。
<br/>
<!-- --- -->
#### ⚡$O(n^2)$ 解法：[CPP Solution](https://leetcode.com/submissions/detail/1588965379/)
---
### ⌱ 多維陣列
<br/>
- ++多維陣列++（Multidimensional Array）
- 一種用來儲存多維資料的`陣列`結構。
- 其中最常見的是++二維陣列++（2D Array）。
- 三維或更高維度的陣列則可視為嵌套的結構。
常見用途包含：
- ☑ 矩陣運算（Matrix Operations）
- ☑ 表格與數據儲存（Tabular Data Storage）
- □ 圖像處理（Image Processing）
- □ 地圖與遊戲開發（Maps & Game Dev）
---
### 二維陣列 （2D-Array）
> 我們知道++一維陣列++就是一個單純的一個串列 其中每個內容都是單一個元素。
>
> 那++二維陣列++就其實也是一個串列 其中每個元素也是一個串列。
- 宣告與初始化：
```cpp[]
int matrix[2][3] = {{1, 2, 3}, {4, 5, 6}};
/* 左邊 [2] 代表裡面含2個串列，右邊 [3] 代表他每個串列的長度為3 */
cout << matrix[0][1] << "\n"; // 2
cout << matrix[1][2] << "\n"; // 6
```
```cpp[]
int 2D_Array[3][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
cout << "2D_Array[0][1] = " << 2D_Array[0][1] << endl; // 訪問元素：？
cout << "2D_Array[1][2] = " << 2D_Array[1][2] << endl; // 訪問元素：？
cout << "2D_Array[2][3] = " << 2D_Array[2][3] << endl; // 訪問元素：？
```
---
#### 🚀 遍歷二維陣列
```cpp[]
int arr[4][5] = {
{0, 2, 4, 6, 8},
{-2, -8, -14, -20, -26},
{4, 8, 12, 16, 20},
{-8, -16, -24, -32, -40},
};
```
要如何遍歷呢❓
<br/>
- 那一定是++巢狀迴圈++ （多層迴圈：兩層）
- 是要用 `for` loop？
- 或是 `while` loop？
- 還是 `do-while` loop？
:::spoiler ▼ 答案
==都可以== 但最++簡單++的做法是 `for` 迴圈
:::
---
#### 🚀 遍歷二維陣列 - `for` loop
<br/>
```cpp[]
int row = 4, col = 5;
int arr[row][col] = {
{0, 2, 4, 6, 8},
{-2, -8, -14, -20, -26},
{4, 8, 12, 16, 20},
{-8, -16, -24, -32, -40},
};
// index 方法
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
arr[i][j] = i * j; // 更新索引位置上的元素值
}
}
// auto& 方法（& 代表的是以位址來傳遞 而不是做一份陣列的 copy）
for (auto& row : arr) {
for (auto& number : row) {
cout << number << " ";
}
cout << endl;
}
```
---
#### 🛠️ 二維陣列 - 常見錯誤
<br/>
- 確保索引++正確範圍++：
```cpp[]
int arr[3][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
arr[2][4] = 13; // 錯誤！陣列索引超出範圍
```
- 確保++正確維度++：
```cpp[]
int arr[2][3];
cout << arr[3][2] << endl; // 超出行數
```
- 確保++正確初始化++：
```cpp[]
int arr[3][3]; // 未初始化，可能含有垃圾值！
cout << arr[0][0] << endl;
// => int arr[3][3] = {0};
```
---
### 📝 小練習5 - 最大陣列
請寫程式來找出下方的二維陣列
總和最大的子陣列 並輸出數值及行數：
```cpp[]
int list[][5] = { // 第一個 dimension 可以不寫 會自動判斷
{2, 3, -5 , -10, 100},
{3, 4, 92, -30, -81},
{5, -6, 42, 11, -19},
{-7, 8, 30, 60, 87},
{9, 10, 75, -109, 47},
{11, 12, 21, 39, -99},
};
```
:::spoiler ▼ 解答
```cpp[]
// #include <climits>
// int max = -INT_MIN;
int max = -2147483648, max_index = -1, rows = sizeof(list) / sizeof(list[0]);
for (int i = 0; i < rows; ++i) {
int sum = 0;
for (auto num : list[i]) sum += num;
if (sum > max) { max = sum; max_index = i; }
} cout << max_index << " " << max << endl;
```
:::
---
### 📌 函式（Function）
<br/>
函式是++封裝++一段邏輯，可以==重複使用==的++程式碼塊++。
- 函式的基本語法：
```cpp[]
#include <iostream>
using namespace std;
// 定義函式
void printHello() { // 一個印出 "Hello Word!" 的函式
cout << "Hello Word!" << endl;
return; // return 跳脫語句 （如 break、continue），用來結束函式
cout << "this line here will not show" << endl;
}
int main() {
printHello(); // 使用函式：輸出 Hello Word!
return 0; // main() 也會有自己的 return
}
```
- ``printAdd(int a, int b)`` → 參數 a 和 b 是int
- `main()` → 本身也是函式，呼叫了 `printAdd()`
---
### 🚚 函式參數傳遞
函式參數可有可無，但如果需要就需要++給定型態++
範例：
```cpp[]
void printAdd1(int a, int b) { // 要求兩個傳入參數 a, b 皆為整數型態
cout << a + b << endl;
}
void printAdd2(int a, char b) { // 要求傳入參數 a 為整數, b 為字元
cout << a + b << endl;
}
void printAdd3(auto a, auto b) { // 要求傳入參數 a, b 型態編譯器判斷
cout << a + b << endl;
}
// => 試著帶入以下 cases 到以上函數看看
```
| | Case 1 | Case 2 | Case 3 |
|-|-|-|-|
| `a` | 65 | 65 | 'A' |
| `b` | 66 | 'B' | 'B' |
| | | | _發現什麼了嗎?_|
---
### ⛟ 函式參數傳遞方法
| 方式 | 說明 | 範例 |
|-|-|-|
| 傳遞值 | 建立變數副本，不影響原值 | `void func(int a)` |
| 引用傳遞 | 直接操作原始變數，較安全 | `void func(int *b)` |
| 傳遞指標 | 修改變數內容，可能產生++空指標++問題 | `void func(int &c)` |
➤ 為何會需要三種傳遞方式呢？
1. ++影響範圍++ 函式內變數更動 是否影響外部
2. ++效率問題++ 製作一份 copy 就是一個開銷
3. ++考量用途++ 陣列的傳遞就會需要指標只向開頭
> `指標`本身存的是指向的變數 ++的地址++
> 但其本身也會有這個++存地址的變數++ 的地址 這的部分可以等學到再細說
---
#### ⦾ 函式傳遞參數/使用 - 範例
```cpp[]
#include <iostream>
using namespace std;
void modify_with_copy(int x) { x = 6; }
void modify_with_reference(int *x) { *x = 66; } // (*)用來取值
void modify_with_pointer(int &x) { x = 666; }
int main() {
int num1 = 1, num2 = 2, num3 = 3;
modify_with_copy(num1);
cout << num1 << endl; // 輸出 1 因為函式更動的值是副本的
modify_with_reference(&num2); // 引用所以必須 (&)傳遞地址
cout << num2 << endl; // 輸出 ?
modify_with_pointer(num3);
cout << num3 << endl; // 輸出 ??
return 0;
}
```
可以看到只有++傳遞值++的方法不會影響傳入的變數值
<br/>
函式還有一個部分還沒有討論到！
- 那函式名稱前面的 `void` 又是什麼呢？
- `main()` 函式前面的 `int` 又代表什麼意思呢？
➤➤➤
---
#### ☆ 函式回傳（`return`）
> 我們知道基本上 C++ 程式 是從上到下 由左到右來讀取/執行 代碼的
> 那使用到 `函式` 就可以將高度重複的代碼重複利用/或是邏輯分離。
假如我們今天想要找一個整數的最大質因數，
可把++計算過程寫在函式++以找多個不同變數質因數，
外部只需要要呼叫函式來獲取答案，可以怎麼做`？`
1. 函式回傳？
- 是要函式內部還是外部需要答案?
- 是外部，那如何接收到計算出的答案?
2. `return` 語法：
- 在定義函式時，函式名稱前加上型態：
- `double`、`int`、`int[]`、`char`、`char[]`
- 或是 `void`（空值、不回傳的型態）
- 語法：`return 值;`（值形態需匹配）
- ++沒有寫++ `return` 的函式++預設++會回傳空值
---
### 函式回傳 - 𝑓（找最大質因數）
我們就來定義一個函式 ++`int getMaxFactor(int x);`++
```cpp[]
#include <iostream>
using namespace std;
// 函式純粹宣告（編譯器接受不馬上接著寫實踐 道理跟變數宣告一樣）
int getMaxPrimeFactor(int x);
int getMaxPrimeFactor(int x) { // 可以看到函式的功能實踐可以寫在其他地方
// 找最大質因數的代碼
// return ?; // return 答案給外部
}
int main() {
int max_prime_factor_of_ten;
max_prime_factor_of_ten = getMaxPrimeFactor(10); // 透過接收 return 值 外部就可以自由利用
cout << "Max prime factor of 10 is: " << max_prime_factor_of_ten << endl;
cout << "Max prime factor of 100 is: " << getMaxPrimeFactor(100) << endl; // 重複利用!
return 0;
}
// 函式的功能實踐也是可以寫在 main 下方
// int getMaxFactor(int x) { 找最大質因數的代碼 }
```
`main()` 主函式中就利用預先邊寫好的功能
方便獲取一個數的最大質因數
現在輪到你來實踐函式內容了
---
### 📝 小練習6 - 最大質因數
與前面範例小小的不同
現在我們的函式++不能有回傳值++（`void function`）
但是外部同樣可以正確的打印出出答案：
請撰寫一個程式把傳入的 int 變數
更新成自己的最大質因數 →
```cpp[]
void beMaxPrimeFactor(...) {
// 你的代碼
}
```
:::spoiler ▼ 解答
```cpp[]
void beMaxPrimeFactor(int &x) {
for (int i = x; i > 0; --i) {
int factorCount = 0;
for (int j = 2; j < i; ++j) {
if (!(i % j)) { factorCount = 1; break; }
}
if (!factorCount) { x = i; return; }
}
}
```
:::
---
### 📝 小練習7 - 矩陣完全平方篩選
請撰寫一個接收一維 int 陣列為參數的函式
`int result[]` 來存只剩下完全平方數的版本 →
```cpp[]
#include <iostream>
#include <cmath> // sqrt(x) -> x 的平方根
using namespace std;
// 返回原本矩陣的完全平方數個數（模板）
int getPerfectSquareArray(const int arr[], int n, int result[]) { // 參數: 原陣列、大小、結果陣列
int count = 0;
// 你的代碼
return count;
}
int main() {
int array[] = {2, 4, 5, 6, 7, 9};
int size = sizeof(array) / sizeof(int);
int res[size];
int num = getPerfectSquareArray(array, size, res);
for (int i = 0; i < num; ++i) cout << res[i] << endl;
return 0;
}
```
:::spoiler ▼ 解答
```cpp[]
int getPerfectSquareArray(const int arr[], int n, int result[]) {
int count = 0;
for (int i = 0; i < n; ++i) {
int square_root = sqrt(arr[i]);
if (arr[i] == square_root * square_root) result[count++] = arr[i];
} return count;
}
```
:::
---
### 📝 小練習8 - 旋轉矩陣函式
如上圖所示，將方形矩陣++順時針旋轉 90°++，
請撰寫函式來更新輸入的++2D矩陣++為其旋轉矩陣 →
- 模板
```cpp[]
#define SIZE 4
void rotateMatrix(int matrix[][SIZE]);
```
:::spoiler ▼ 詳解
```cpp[]
void rotateMatrix(int matrix[][SIZE]) {
int temp[SIZE][SIZE];
for (int i = 0; i < SIZE; ++i) {
for (int j = 0; j < SIZE; ++j) temp[j][SIZE - 1 - i] = matrix[i][j];
}
for (int i = 0; i < SIZE; ++i) {
for (int j = 0; j < SIZE; ++j) matrix[i][j] = temp[i][j];
}
}
```
:::
---
### ∞ 遞迴（Recursion）
<br/>
`遞迴` 是函式呼叫自己的方式，常用於解決：
- 數學問題（費氏數列、階乘）
- 樹的遍歷 （樹狀結構）
- 深度優先搜尋（DFS）
- 背包問題 （[Knapsack Problem](https://web.ntnu.edu.tw/~algo/KnapsackProblem.html)）
這些用法都是在解決深度不確定的問題，
那其實遞迴能解決的問題 ++迴圈++也同樣能夠
遞迴的概念 需要培養他的思考邏輯
（畫圖是一個好方法）
使用時 要小心當++函式終止條件++始終不能滿足時
就會造成==無窮遞迴== 沒錯 跟++無窮迴圈++是相似的概念
---
### ⁍ 遞迴的基本結構
```cpp[]
void recursion1(int n) {
cout << n << endl;
if (n == 0) return; // 終止條件 也稱為基礎條件（Base Case）
recursion1(n - 1); // 遞迴呼叫 -> 遞迴關係（Recursive Case）
}
```
➛ `recursion1` 可以寫成以下 `loop1`
```cpp[]
void loop1(int n) {
for (int i = n; i >= 0; --i) cout << i << endl;
}
```
<br/>
```cpp[]
int recursion2(int n) {
if (n == 0) return 0; // 終止條件
return n + recursion2(n - 1); // 返回遞迴呼叫結果
}
```
➛ `recursion2` 可以寫成以下 `loop2`
```cpp[]
int loop2(int n) {
int accumulate = 0;
for (int i = n; i >= 0; --i) accumulate += i;
return accumulate;
}
```
---
#### 常見的遞迴1 - `費式數列`（Fibonacci Sequence）
<br/>
定義一個++數列++的第一項 $a_1$ = 第二項 $a_2$ = 1
==When $n > 2, a_n = a_n-1 + a_n-2$==
可以來練習遞迴了 →
```cpp[]
int fibonacci(int n) { // 參數 n: 第 n 項（已確保 n > 0）
if (n <= 2) return 1; // 第一項、第二項 都等於 1
return __(?)__; // 回傳費式數列 第 n 項的值
}
```
‣ 看一下迴圈怎麼做的：
```cpp[]
int fibonacci_loop(int n) {
int last1 = 1, last2 = 1, val = 0;
if (n <= 2) return 1;
for (int i = 1; i <= n; ++i) {
if (i <= 2) continue;
val = last1 + last2;
last1 = last2;
last2 = val;
}
return val;
}
```
---
#### 常見的遞迴2 - `階乘!`（Factorial）
<br/>
定義 ==$n! = 1 * 2 * ... * (n -1) * n$==
想一下遞迴要怎麼達成 →
```cpp[]
int factorial(int n) { // 已確保 n >= 1
if (n == 1) return 1; // 1! = 1
return __(?)__;
}
```
> 概念跟`累加`很像，不懂可以畫圖++層層展開++
<br/>
‣ 迴圈作法：
```cpp[]
int factorial_loop(int n) {
int val = 1;
for (int i = n; i >= 1; --i)
val *= i;
return val;
}
```
---
### 💾 `const` 保留字
<br/>
首先什麼++保留字++（keyword）❔[關鍵字 (C++)](https://learn.microsoft.com/zh-tw/cpp/cpp/keywords-cpp?view=msvc-170)
- 有特殊意義/功能的++預先定義++保留識別項。
- ==不能==在程式中將關鍵字當做識別碼使用。
- 像是以下這些都不能拿來命名變數/函數：
- `if`、`for`、`goto`、`this`、`class` ...
- `int`、`char` 還有 `const` 也都是
- `const` 關鍵字的功用❓
- 來指定變數值為常數，告知編譯器禁止修改。
---
### `const` 用法
- 語法：
```cpp[]
const 變數 = 初始值;
```
- 範例：
```cpp[]
const int MAX_SIZE = 100; // 定義一個常數變數
MAX_SIZE = 200; // ❌ 錯誤，const 變數無法更改
```
- 編譯器++報錯++：
```
Output:
test.cpp: In function ‘int main()’:
test.cpp:8:10: error: assignment of read-only variable ‘MAX_SIZE’
8 | MAX_SIZE = 200;
| ~~~~~~~~~^~~~~
```
我們宣告的 const 變數 被當作是 ++read-only++ 的對象
---
#### ☴ `const` 其他用法 - 函式參數
<br/>
1. `const` 參數：
```cpp[]
void printMessage(const string &msg) {
cout << msg << endl;
}
```
```cpp[]
void printValue(const int &val) {
val++; // 編譯器不會允許修改
cout << val << endl;
}
=> error: increment of read-only reference ‘val’
```
當函數參數被傳入時設定為 `const` 的引用，
這樣就可以確保函式內部++不會更動到引用的值++
---
#### ☴ `const` 其他用法 - 指標
> **++指標++、++成員函式++ 這些先大致看過就好**
<br/>
2. `const` 指標：
```cpp[]
int a = 10, b = 20;
const int *ptr = &a; // 指標指向的值不能改變
ptr = &b; // ✅ 可以更改指標指向的位置
*ptr = 30; // ❌ 錯誤，不能修改 ptr 指向的內容
int *const ptr2 = &a; // 指標本身不能改變，但內容可變
ptr2 = &b; // ❌ 錯誤
*ptr2 = 40; // ✅ 可修改 ptr2 指向內容
```
> ++指標++本身是一個指針 指向一個變數的地址 (往後細講)
---
#### ☴ `const` 其他用法 - 成員函式
> **++指標++、++成員函式++ 這些先大致看過就好**
<br/>
3. `const` 成員函式：
```cpp[]
class Example {
public:
void show() const { // const 確保外部無法重新定義 Example.show()
cout << "這是 const 函式，無法改變物件內容" << endl;
}
};
```
> 此處 `Example` 是一個 `class`，`show()` 則為 `Example` 中的一個++成員函式++
---
#### 📝 基礎題 - 合法括號（[Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)）
有一行 input string 字串，請撰寫函示判斷是否
所有括號皆有封閉（只會有 左括號`(` 和 右括號 `)`）
:::spoiler ▼ 詳解
```cpp[]
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
bool validParentheses(string input) {
int index = 0;
while (input[index] == ')') { index++; } // 檢查不能以右括號開頭
if (index) return false;
int count = 0;
for (const auto& c : input) {
switch (c) {
case '(': ++count; break;
case ')': --count; break;
}
}
return count == 0;
}
int main() {
string str;
cin >> str;
cout << validParentheses(str) << endl;
return 0;
}
```
:::
<br/>
- 進階版本：[LeetCode - Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)
- 有多種括號：`'('`, `')'`, `'{'`, `'}'`, `'['`, `']'`
- 解答: [switch-case 解法](https://leetcode.com/submissions/detail/1591260870/)
---
#### 📝 進階題 - 樓梯問題（Climbing Stairs）
輸入一個 `n`，代表有 `n` 階樓梯，你一次可以爬 ++1 階或 2 階++，請問有幾種爬法？
> 題示: 遞迴 `f(n) = f(n-1) + f(n-2)` 來解
- 模板：
```cpp[]
int climbingStairs(int n) {
// 你的程式碼
return __(?)__;
}
```
:::spoiler ▼ 詳解
```cpp[]
int climbingStairs(int n) {
if (n == 1) return 1;
else if (n == 2) return 2;
return climbingStairs(n - 1) + climbingStairs(n - 2);
}
```
:::
---
### 🖊️ 習題練習 （LeetCode）
- [Find the Index of the First Occurrence in a String](https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/)
> 提示：善用 `substr()`
<br/>
解答：[string.substr() 解法](https://leetcode.com/submissions/detail/1591277535/)
{"title":"CPP Lecture3","description":"CPP Lecture3.","image":"https://hackmd.io/_uploads/HJKOkQjnkx.png","contributors":"[{\"id\":\"08ecf684-cada-47c1-ad99-984ab62fb65e\",\"add\":25498,\"del\":4577}]"}