<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{
color: #9CCEF2;
}
.markdown-body h2,
.markdown-body h3{
color: #B1D6CA;
}
.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>

###### tags: `tgirc早修book`

# Ch.07 題目練習

## 副程式

<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)

:::spoiler <font color="FEA0A0">**題解**</font>
1. 最大值

回傳兩者中比較大的那個，如果 `a > b` 就回傳 `a` ，反之回傳 `b`

int maximum(int a, int b){
    if(a > b){
        return a;
    }
    else{
        return b;
    }
}

2. 絕對值

`n` 小於 0 時回傳 `-n`，否則直接回傳 `n`

int abs(int n){
    if(n >= 0){
        return n;
    }
    else{
        return -n;
    }
}

3. 最大公因數

以輾轉相除法的方式去實作，每次讓 `a` 與 `b` 交換並取餘數。
直到其中一個取餘數為 0 時，就回傳另一個。

int GCD(int a, int b){
    if(b != 0){
        return GCD(b, a%b);
    }
    else{
        return a;
    }
}

4. 交換變數

此處有用到 [參照](http://blog.kenyang.net/2011/11/16/c-reference) 的觀念。
建議可以閱讀補充的 [指標與位址](/@Tamilala/cpp_pointer)

void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

5. [Toj 170 / 各種星星樹](https://toj.tfcis.org/oj/pro/170/)
（待補）
<!--
6. [Kattis DRM Messages](https://open.kattis.com/problems/drmmessages)
-->
:::

## 遞迴

<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)

:::spoiler <font color="FEA0A0">**題解**</font>

1. GCD 最大公因數

int GCD(int a, int b){
    if( b == 0 ) return a;
    else         return GCD(b, a%b);
}

2. 平方和

int f(int n){
    if( n == 1 ) return 1;
    else         return n * f(n-1);
}

3. [Zerojudge c002: 10696 - f91](https://zerojudge.tw/ShowProblem?problemid=c002)

int f91(int n){
	if( n <= 100 ) return f91( f91(n+11) );
	else return n-10;
}

4. [Zerojudge e357: 遞迴函數練習](https://zerojudge.tw/ShowProblem?problemid=e357)

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

5. [Zerojudge c813: 11332 - Summing Digits](https://zerojudge.tw/ShowProblem?problemid=c813)

int G(int n){
	int sum=0;
    
	while( n!=0 ){
		sum += n%10;
		n /= 10;
	}
    
	if( sum<10 ) return sum;
	else         return G(sum);
}

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)

-->

:::