---
tags: TGIRC
---

<style>

html, body, .ui-content {
background-color: #333;
color: #ddd;
}

body > .ui-infobar {
display: none;
}

.ui-view-area > .ui-infobar {
display: block;
}

.markdown-body h1,
.markdown-body h2,
.markdown-body h3,
.markdown-body h4,
.markdown-body h5,
.markdown-body h6 {
color: #ddd;
}

.markdown-body h1,
.markdown-body h2 {
border-bottom-color: #ffffff69;
}

.markdown-body h1 .octicon-link,
.markdown-body h2 .octicon-link,
.markdown-body h3 .octicon-link,
.markdown-body h4 .octicon-link,
.markdown-body h5 .octicon-link,
.markdown-body h6 .octicon-link {
color: #fff;
}

.markdown-body img {
background-color: transparent;
}

.ui-toc-dropdown .nav>.active:focus>a, .ui-toc-dropdown .nav>.active:hover>a, .ui-toc-dropdown .nav>.active>a {
color: white;
border-left: 2px solid white;
}

.expand-toggle:hover,
.expand-toggle:focus,
.back-to-top:hover,
.back-to-top:focus,
.go-to-bottom:hover,
.go-to-bottom:focus {
color: white;
}

.ui-toc-dropdown {
background-color: #333;
}

.ui-toc-label.btn {
background-color: #191919;
color: white;
}

.ui-toc-dropdown .nav>li>a:focus,
.ui-toc-dropdown .nav>li>a:hover {
color: white;
border-left: 1px solid white;
}

.markdown-body blockquote {
color: #bcbcbc;
}

.markdown-body table tr {
background-color: #5f5f5f;
}

.markdown-body table tr:nth-child(2n) {
background-color: #4f4f4f;
}

.markdown-body code,
.markdown-body tt {
color: #eee;
background-color: rgba(230, 230, 230, 0.36);
}

a,
.open-files-container li.selected a {
color: #5EB7E0;
}

</style>
# **37th 南女資研社 C++ 講義 - 2**

[題單](https://docs.google.com/spreadsheets/d/1Yw05k1VBrvykWaJTcpDDcRA3GZ2TfKcwRRITbU0G6hE/edit#gid=0)

## <font color="9CCEF2">自定義函數 function</font>

函式就是像 `sort()`、`getline()`、`find()` 這些，它們各自有各自的功能

舉 `find()` 為例子，如果字串 str 內容為 "Hello world!"，想在字串 str 裡尋找 "world"，並輸出它的位置，那程式碼會是這樣：

str="Hello world!";
cout<<"position: "<<str.find("world",0);

而此行程式執行結果會是：

position: 6

而當在程式碼中需要經常使用到某段程式，但又沒有像上述的函數一樣可以使用，此時就可以自己撰寫一份函數出來，每當要使用時就呼叫它，就不用再寫相同的程式碼，要修改時也只要修改函數中的程式碼就好

### **<font color="B1D6CA">基本架構</font>**

這裡舉一個 a+b 的副程式 plus(a,b) 為例，呼叫時傳入 a 與 b，則此程式回傳 a+b 的值
那這個副程式的本體會長這樣：

<font color="F5F6B6">**範例 1**</font>

int plus(int a,int b){
//開頭的 int，代表這個名叫 plus 的函數回傳值會是 int 型態，括號內的兩個是它的參數 a 與 b
//不管傳入的變數叫什麼，在函數內都以它的名稱 a 與 b 進行操作

    int sum;
    //在函數裡也能宣告變數
    
    sum=a+b;
    
    return sum;
    //return 後面接程式的回傳值
}

### **<font color="B1D6CA">宣告與呼叫</font>**

函數的宣告有兩種方式，分別是把函數主體放在主函數前與主函數後
註：主函數就是 `int main()` 那個

* <font color="F5F6B6">**在主函數前**</font>

在主函數前，就先把整個函式本體寫完，優點是不用先宣告一次

#include<iostream>
using namespace std;

//回傳型態為int，所以開頭是用int
//每個參數的型態也別忘了

int plus(int a,int b){
    return a+b;
    //也能直接回傳a+b的運算結果
}

//主程式
int main(){
    cout<<plus(10,5);
    
    return 0;
}

* <font color="F5F6B6">**在主函數後**</font>

這種要先在主函數前宣告一次，主函數後再補上函數整體

#include<iostream>
using namespace std;

//切記！要先在前面這裡宣告過，不然程式會不認得 plus() 這個東東
int plus(int,int);
//這裡還不用宣告參數名稱，只要把每個參數的型態依序列出就好

//主函數
int main(){
    cout<<plus(10,5);
    
    return 0;
}
//函數
int plus(int a,int b){
    return a+b;
}

若要呼叫寫好的函數，只需要在使用時呼叫函數名字，再加上 ( ) 傳遞參數即可
只是要注意傳遞的參數型別與參數的數量是否和當初宣告函數時相同

### **<font color="B1D6CA">void</font>**

return 值有 int、char、bool 等各種型態。
但如果只是要讓副程式做個動作，而不希望它回傳任何東西，那就把函數型態設為 void 就好。
以交換兩變數的值為例：

<font color="F5F6B6">**範例 1**</font>

#include<iostream>
using namespace std;

void swap(int a,int b){
    int temp;
    temp=a;
    a=b;
    b=temp;
    cout<<"a: "<<a<<" b: "<<b<<'\n';
}

int main(){
    int a=2,b=3;
    cout<<"a: "<<a<<" b: "<<b<<'\n';
    cout<<'\n';
    cout<<"swap:\n";
    swap(a,b);
    return 0;
}


### **<font color="B1D6CA">碰到 return 就會結束程式</font>**

有回傳值的程式，會用一個 return 來回傳值

但其實程式只要碰到 return 就會回傳並結束，且一個程式只會 return 一個值，縱使它可能有很多條 return，但它只會回傳第一個可以 return 的，所以可以善用 return 來進行條件判斷與程式中止

以下示範return的運作模式：

<font color="F5F6B6">**範例 1**</font>

int ret_test(){
    return 6;
    //只有這行會被return，後面的程式都不會運行
    
    return 10;
    //因為前面的return已經中止，所以這個return不會被處理
}

int main(){
    cout<<ret_test();
    
    return 0;
}

輸出如下：

6

### **<font color="B1D6CA">函數之間可以互相呼叫</font>**

一個函數可以呼叫另一個函數，甚至可以呼叫自己，這在之後會講的遞迴裡很常使用。

int function_1(int a){
    .
    .
    .
}

int function_2(int a){
    int n;
    function_1(n);
    function_2(n);
}

### **<font color="B1D6CA">一維陣列傳入函數</font>**

宣告時一樣要加上中括號，但不用加上長度，就算加上後，它也會省略不看
陣列在傳遞時以指標方式傳遞，而函數中對陣列的操作會保留下來，也就是若更動陣列中的某個值，那原本的陣列也會一同被更動

* <font color="F5F6B6">**在主函數前**</font>

int function(int x[],char C);

int main(){
    int arr[10]={...};
    char n;
    function(arr,n); //呼叫時直接以指標傳入
    .
    .
    .
    
    return 0;
}

* <font color="F5F6B6">**在主函數後**</font>

int function(int [],char);

int main(){
    int arr[10]={...};
    char n;
    function(arr,n); //呼叫時直接以指標傳入
    .
    .
    .
    
    return 0;
}

int function(int X[],char C){
    .
    .
    .
}

也可以使用 `int *function()` 來宣告，意思相同只是可能會被誤解成其他意思

### **<font color="B1D6CA">多維陣列傳入函數</font>**

因為多維陣列在位址的計算上會需要第一維之外，每一維的大小
所以在宣告時必須加上，並且要相同

<font color="F5F6B6">**範例 1**</font>

#include<iostream>
using namespace std;

int sum(int (*x)[3],int n){
	int num=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++){
			num+=x[i][j];
		}
	}
	return num;
}

int main(){
    int a[2][3]={{1,1,1},{2,2,2}};
    int b[3][2]={{1,1},{2,2},{3,3}};
    cout<<sum(a,2)<<'\n'; 
    cout<<sum(b,3)<<'\n'; //compile error
    return 0;
}

使用 `int (*x)[3]` 宣告一個二維陣列，每一列都有長度為 3 的一維 int 陣列
而因為 b 陣列為每列長度皆為 2 的一維 int 陣列，所以不符合並導致 CE

:::spoiler <font color="FEA0A0">**題目**</font>
副程式基本沒啥特別的練習題，不過如果想練習寫副程式，可以把程式中時常重複出現的部分，試著提出來另外寫成一組副程式。

我覺得副程式這塊除了練習，更重要的是「判斷哪幾段程式可以提出來另外寫」，適時的使用副程式，可以很有效的簡化程式碼。

1. 最大值
2. 絕對值
3. 最大公因數
4. 交換變數
5. [Toj 170 / 各種星星樹](https://toj.tfcis.org/oj/pro/170/)
6. [Kattis DRM Messages](https://open.kattis.com/problems/drmmessages)
:::

## <font color="9CCEF2">變數的生命週期</font>

根據我們宣告的位置不同，會分為全域變數跟區域變數

### **<font color="B1D6CA">全域變數</font>**

宣告在函數外且不在任何區域中的變數，就叫做<font color="F5F6B6">**全域變數**</font>
全域變數的預設值為 0，並且所有的函數都可以使用同一個變數

<font color="F5F6B6">**範例 1**</font>

#include <iostream>
using namespace std;

int b=3;

int f(int n,int m){
    return n+m;
}

int main(){
    int a=10;
    cout<<a-b<<'\n';
    cout<<f(a,b)<<'\n';
    return 0;
}


### **<font color="B1D6CA">區域變數</font>**

區域變數只有在宣告的區域才有效，使用不當可能會遇到 overflow 的情況出現，並且沒有初始值
因為只在宣告的區域中有效，所以離開了宣告的區域後，在不同區域中可以使用同一個變數名稱

for(int i=0;i<3;i++){
    string s="ouob";
    cout<<s<<'\n';
}
cout<<i<<'\n'; //compile error
cout<<s<<'\n'; //compile error

上述程式碼中的 i 跟 s 都是區域變數，所以離開了宣告範圍後，要再使用就會產生 CE

## <font color="9CCEF2">遞迴</font>

遞迴是指在函數中呼叫函數本身，需要訂定終止條件

遞迴適用於各種「可以整理出與前項的關係式」的函式
依個人理解來說，遞迴就是想辦法整理成一個通式，使其每項都固定與前 n 項有關。
整理成數學式就像這樣：

f(n)=a ‧ f(n-1) + b ‧ f(n-2) + …

每一項都會固定是與前幾項有關係，這樣整理出來後，要處理遞迴就方便的多了

<font color="F5F6B6">**範例 1**</font>
有一函數 f(x)=1+2+3…+x，求給定 x 值的 f(x)

#include <iostream>
using namespace std;

int f(int x){
    if(x == 1) return 1;
    //如果x=1，那麼f(x)=1
    
    return f(x-1)+x;
    //如果x不是1，那麼f(x)=f(x-1)+x
    //而f(x-1)就是直接將x-1作為參數傳入f()，回傳f(x-1)的值
    //即使是在f()內也可以呼叫自己
}

int main(){
    int x;
    cin>>x;
    cout<<f(x)<<'\n';
    return 0;
}

這題我們先觀察前幾項

f(1) = 1
f(2) = 1+2 = f(1)+2
f(3) = 1+2+3 = f(2)+3
f(4) = 1+2+3+4 = f(3)+4
.
.
.

可以觀察到如下規律：

f(x) = 1 (x=1)
f(x) = f(x-1) + x (x>1)

第一條式子其實就是邊界條件，這項 f(x) 就不再跟其他項有關聯了。
而第二條式子就是一般情況下，f(x) 所遵循的規則。

所以遞迴大致上就是求 f(x) 的值時，呼叫 f(x)，而因為 f(x) 中需要用到 f(x-1)，所以呼叫f(x-1)，但在 f(x-1) 中可能又會用到 f(x-2)，所以呼叫 f(x-2)...

就這樣一路呼叫到 f(2)=f(1)+2 這條時，遇到 f(1)=1，所以程式回傳 1。
這時 f(2) 就有了 1+2=3 這個值，並將 3 回傳給 f(3)=f(2)+3=3+3=6，然後是f(4)=f(3)+4=6+4=10...

大部分的遞迴都可以拆成這樣的步驟來進行。

<font color="F5F6B6">**範例 2**</font>
費氏數列（費波那契數列） -> [相關介紹](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0)

費氏數列是一段第 0 項為 0、第 1 項為 1，之後的項數都由前面兩項相加而成的數列
-> 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , ...

輸入 x，求費氏數列的第 x 項
<!--

#include <iostream>
using namespace std;

int f(int x){
    if(x == 0) return 0;
    else if(x == 1) return 1;
    
    return f(x-1) + f(x-2);
}

int main(){
    int x;
    cin >> x;
    cout << f(x) << '\n';
    return 0;
}

-->
### **<font color="B1D6CA">Top-down</font>**

先寫出一個能解決問題的函數，再以遞迴方式完成

<font color="F5F6B6">**範例 1**</font>
階乘（！）

階乘的定義如下：
!1 = 1
!2 = 1 ‧ 2
!3 = 1 ‧ 2 ‧ 3
!4 = 1 ‧ 2 ‧ 3 ‧ 4

!n = 1 ‧ 2 ‧ 3 ‧ … ‧ n

輸入 n，求第 n 階的值

int f(int n){
    if(n == 0) return 1;
    return n * f(n-1);  //由f(n-1)繼續回推
}

:::info
因為系統本身是有限制的，當遞迴過深時會導致 overflow
:::

### **<font color="B1D6CA">Bottom-up</font>**

<font color="F5F6B6">**範例 1**</font>
階乘（！）

階乘的定義如下：
!1 = 1
!2 = 1 ‧ 2
!3 = 1 ‧ 2 ‧ 3
!4 = 1 ‧ 2 ‧ 3 ‧ 4

!n = 1 ‧ 2 ‧ 3 ‧ … ‧ n

輸入 n，求第 n 階的值

根據這題而言，Top-down 的作法會是：
n=4 時

f(4) = f(3) * 4
f(3) = f(2) * 3
f(2) = f(1) * 2
f(1) = f(0) * 1
知道 f(1) 的值是 1 * 1 後回傳給 f(2)
f(2) = 1 * 2
f(3) = 2 * 3
f(4) = 3 * 4

透過觀察，其實也可以直接從 第1項 開始往後乘到 4

for(int i=1;i<=n;i++){
    num[i]=num[i-1]*i;
}

相較於 Top-down，Bottom-up 的效率比較好，只有極少數情況才會出錯，並且風險也比較低，所以建議可以多多練習 Bottom-up，但 Top-down 的用法也需學會

### **<font color="B1D6CA">題型範例</font>**

#### <font color="F5F6B6">**字元排列組合**</font>

若有 n 個字元，輸出其所有排列方式。

假設今天的字元有 a, b, c 三個，把它的所有排列方式表示為 (a, b, c)，那它的所有排列方式就是：

(a,b,c) = [a + (b,c)] + [b + (a,c)] + [a + (b,c)]

也就是我們可以讓所有字元各擔任一次字串開頭，然後後面接剩下的字元的所有排列方式。
而剩下的字元的所有排列方式又可用相同方式處理，直到剩下一個字元。

string str;
void Perm(int i,int n){
    if(i == n){
        cout<<str<<"\n";
    }
    else{
        for(int j=i;j<n;j++){
            swap(str[i],str[j]);
            Perm(i+1,n);
            swap(str[i],str[j]);
        }
    }
}

#### <font color="F5F6B6">**河內塔**</font>

河內塔是一個大盤子在下，小盤子在上，總共三根柱子可以放盤子的裝置。
目標是將 A 柱子上的所有盤子按照順序移到 C 柱子上，一次只能移一個盤子，且大盤子不能放在小盤子上，按照順序輸出移動步驟。

首先觀察只有 2 個盤子的情況，先將小盤子由 A 移到 B，再把大盤子由 B 移到 C 最後把小盤子由 B 移到 C。

其實可以想成是把最大的盤子以上的小盤子全部移到 B 柱子上，再把最大的移到 C 柱子，最後把 B 柱子的盤子全部移到 C 柱子上。

此時我們把 A 稱為起始柱，B 為中間柱作為轉運站，C 則是終點柱。所有的 n 層塔都可拆為以下步驟：

1. 將 起始柱 上 n-1 個盤子移到 中間柱
2. 將 起始柱 最底下剩餘的 1 個盤子移到 終點柱
3. 將 中間柱 上 n-1 個盤子移到 終點柱

:::spoiler <font color="F5F6B6">**流程圖**</font>








:::
>

而 n-1 個盤子的移動方式，又可按照這個步驟，一路移動至剩下一個盤子時，就只需將那個盤子直接由起點柱移到終點柱了。

void Hanoi(int n, char from, char mid, char to){
    //把n個盤子由A柱子移至C柱子
    //A為起點柱，B為中間柱，C為終點柱
    
    if( n==1 ){
        cout << from << " -> " << to << "\n";
    }
    //如果只有一個盤子，就直接由起點柱移到終點柱
    
    else{
        Hanoi(n-1, from, to, mid);
        //將n-1個盤子由起點柱移到中間柱
        Hanoi(1  , from, mid, to);
        //將最底下的1個盤子由起點柱移到終點柱
        Hanoi(n-1, mid, from, to);
        //將n-1個盤子由中間柱移到終點柱
    }
}

:::spoiler <font color="FEA0A0">**題目**</font>
1. GCD 最大公因數
輸入 a 和 b，求兩者間的最大公因數
>
2. 平方和
由 1 至 n 的平方和，前幾項如下：

f(1) = 1^2^
f(2) = 1^2^ + 2^2^
f(3) = 1^2^ + 2^2^ + 3^2^
f(4) = 1^2^ + 2^2^ + 3^2^ + 4^2^

輸入 n，求 1 至 n 的平方和
>
3. [Zerojudge c002: 10696 - f91](https://zerojudge.tw/ShowProblem?problemid=c002)
4. [Zerojudge e357: 遞迴函數練習](https://zerojudge.tw/ShowProblem?problemid=e357)
5. [Zerojudge c813: 11332 - Summing Digits](https://zerojudge.tw/ShowProblem?problemid=c813)
6. [Zerojudge d672: 10922 - 2 the 9s](https://zerojudge.tw/ShowProblem?problemid=d672)
7. [Zerojudge d487: Order's computation process](https://zerojudge.tw/ShowProblem?problemid=d487)
8. [Zerojudge a227: 三龍杯 -> 河內之塔](https://zerojudge.tw/ShowProblem?problemid=a227)
9. [Zerojudge d734: 另类Hanoi](https://zerojudge.tw/ShowProblem?problemid=d734)

:::