---
# System prepended metadata

title: 資料結構與演算法 習題解答 第1~4章

---

# 資料結構與演算法 習題解答 第1~4章
### 高立圖書：512326  
#### 即時更新請見：https://hackmd.io/@sjshyu/DS_Exercises_Ch1-4
---
## 第一章 基本概念    
### 1. 寫一個程序，將傳入的整數參數 $x$、$y$ 和 $z$ 由小到大印出。此程序的計算時間為多少？

:::spoiler 可利用 bubble sort 的概念：

```cpp=
# include <stdio.h>
# include <iostream>
using namespace std;
void print_nondecreasingly(int x, int y, int z)
{   int t;
    if (x > y) SWAP(x, y, t);
    if (y > z) SWAP(y, z, t);
    if (x > y) SWAP(x, y, t);
    cout << "sorted: " << x << " " << y << " " << z << endl << endl;
}
int main()
{   int x, y, z;
    while (cout << "x y z = ", scanf("%d %d %d", &x, &y, &z), x != 0)
    print_nondecreasingly(x, y, z);
}
```
時間複雜度為 $O(1)$。

/* ---- 執行結果:

x y z = 34 12 9
sorted: 9 12 34

x y z = 23 45 28
sorted: 23 28 45

x y z = 9 2 7
sorted: 2 7 9

x y z = 0 9 11

---- */

![](https://i.imgur.com/FiBk7NR.png)

:::

---
### 2. 二項式係數 (binomial coefficient) 的定義如下： <br> &emsp; $\dbinom{n}{m} = \dfrac{n!}{m!(n-m)!};$ <br> 請用迴圈撰寫程式，計算二項式係數（輸入 $n$，求 <br> &emsp; $\dbinom{n}{m}$，$m=0, 1, 2, …, n$）。 <br> 而該式可用下面的遞迴式表示： <br> &emsp; $\dbinom{n}{m} = \dbinom{n-1}{m} + \dbinom{n-1}{m-1}$ <br> 請用遞迴的技巧撰寫程式，計算二項式係數。試比較兩者的優劣。
$\displaystyle\sum_{k=1}^{n}x(t_k)$
:::spoiler 遞迴版本:

&emsp;請將二項式係數 $\dbinom{n}{m} = \dfrac{n!}{m!(n-m)!}$ 想像成大小為 $n×n$ 的二維陣列 B，B[$n$][$m$] 所存放的內容 (value)，則可解讀為：B[$n$][$m$] = B[$n-1$][$m$] + B[$n-1$][$m-1$]！此式可用迴圈撰寫程式如下：（注意：初始條件的設定：$(n, 0) = 1$ 當 $n ≥ 1$， 且 $(n, k) = 0$ 當 $k ≥ n$）

```cpp=
# define SIZE 50
# include <iostream>
using namespace std;
int B[SIZE][SIZE];

void binomialCoef_NRC(int n)
{   int i, j;
    // if n < 0 return directly
    for (i = 0; i <= n; i++) // setting of initial conditions
    {   B[i][0] = 1;
        B[i][i + 1] = 0;
    }
    for (i = 0; i <= n; i++)
    {   for (j = 1; j <= i; j++)
        {   B[i][j] = B[i - 1][j - 1] + B[i - 1][j];
        }
    }
    for (cout << "Non-recursively: ", i = 0; i <= n; i++)
    {   cout << "(" <<  n << ", " << i << ") = " << B[n][i] << "  ";
    }
    cout << endl;
}

int bino(int n, int m)
{   if ((n == m) || (m == 0)) return 1;
    return bino(n - 1, m) + bino(n - 1, m - 1);
}

void binomialCoef(int n)
{   int i, j;
 	for (cout << "Recursively:     ", i = 0; i <= n; i++)
    {   cout << "(" << n << ", " << i << ") = " << bino(n, i) << "  ";
    }
    cout << endl;
}

int main()
{   int n;
    while (cout << "n = ", cin >> n, n != 0)
    {   binomialCoef_NRC(n);
        binomialCoef(n);
    }
}
```
/* ---- 執行結果:

n = 4
Non-recursively: (4, 0) = 1  (4, 1) = 4  (4, 2) = 6  (4, 3) = 4  (4, 4) = 1
Recursively:     (4, 0) = 1  (4, 1) = 4  (4, 2) = 6  (4, 3) = 4  (4, 4) = 1

n = 5
Non-recursively: (5, 0) = 1  (5, 1) = 5  (5, 2) = 10  (5, 3) = 10  (5, 4) = 5  (5, 5) = 1
Recursively:     (5, 0) = 1  (5, 1) = 5  (5, 2) = 10  (5, 3) = 10  (5, 4) = 5  (5, 5) = 1

n = 7
Non-recursively: (7, 0) = 1  (7, 1) = 7  (7, 2) = 21  (7, 3) = 35  (7, 4) = 35  (7, 5) = 21  (7, 6) = 7  (7, 7) = 1
Recursively:     (7, 0) = 1  (7, 1) = 7  (7, 2) = 21  (7, 3) = 35  (7, 4) = 35  (7, 5) = 21  (7, 6) = 7  (7, 7) = 1
n = 0

---- */

![](https://i.imgur.com/QSMu8LD.png)

利用迴圈可在 $O(nm)$ 的時間內求算 ，$m = 0, 1, 2, …, n$ 。
利用遞迴則效能較差，請見下圖。一般而言 $C$($n , k$) < $O(2n)$ 。(註：$T$($n, k$) $< 20+21+22+ … +2n-1 = 2n$)
https://stackoverflow.com/questions/26228385/time-complexity-of-recursive-algorithm-for-calculating-binomial-coefficient
![](https://i.imgur.com/aGDepcB.png)

:::

---
### 3. 費氏 (Fibonacci) 數列被定義成： <br> &emsp; (1) $F_0 = 0, F_1 = 1;$ <br> &emsp; (2) $F_n= F_{n−1} + F_{n−2},$ 當 $n≥2$。 <br> 寫出遞迴和迴圈版本（非遞迴）的程序來計算費氏數列（輸入 $n$，求 $F_1,  F_2, … , F_n$）。

:::spoiler 遞迴版本:

```cpp=
# include <iostream>
using namespace std;

int F(int n)
{   int ans;
    if (n == 0) return 0;
    if (n == 1) return 1;
    return F(n - 1) + F(n - 2);
}
 
int main(void)
{   int n, i;
    while(cin >> n)
    {   
        for (i = 0; i <= n; i++) cout << F(i)<< " ";
        cout << endl;
    }
    return 0;
}
```
/* ---- 執行結果:

3
0 1 1 2
5
0 1 1 2 3 5
10
0 1 1 2 3 5 8 13 21 34 55
15
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
20
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

---- */

![](https://i.imgur.com/lZOxbmN.png)

:::

:::spoiler 迴圈版本:

```cpp=
int main()
{   int n, i;
    while (cin >> n)
    {   int F[n + 1] = {0};
        F[1] = 1;
        for (i = 2; i <= n; i++) F[i] = F[i - 1] + F[i - 2];
        for (i = 0; i <= n; i++) cout << F[i] << " ";
        cout << endl << endl;
    }	
}
```
/* ---- 執行結果:

3
0 1 1 2
5
0 1 1 2 3 5
10
0 1 1 2 3 5 8 13 21 34 55
20
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

---- */

![](https://i.imgur.com/3vQfE2A.png)

:::

---
### 4. Lucas 數列被定義成： <br> &emsp; (1) $L_0 = 2, L_1 = 1;$ <br> &emsp; (2) $L_n = L_n-1 + L_n−2,$ 當 $n≥2$。 <br> 寫出遞迴和非遞迴版本的程序來計算Lucas 數列。

:::spoiler 比較
>:::spoiler 遞迴版本：
>```cpp=
>int L(int n)
>{  int ans;
>    if (n == 0) return 2;
>    if (n == 1) return 1;
>    return L(n - 1) + L(n - 2);
>}
>int main(void)
>{  int n, i;
>    while (cin >> n)
>    {   for (i = 0; i <= n; i++)
>        {   cout << L(i) << " ";
>        } 
>        cout << endl; 
>    }	
>}
>```
>/* ---- 執行結果:
>2
>2 1 3
>5
>2 1 3 4 7 11
>10
>2 1 3 4 7 11 18 29 47 76 123
>20
>2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349 15127
>---- */
>![](https://i.imgur.com/qqvX6ws.png)
>:::
>:::spoiler 迴圈版本：
>```cpp=
>int main()
>{   int n, i;
>    while(cin >> n)
>    {   int L[n + 1] = {2};
>        L[1] = 1;
>        for (i = 2; i <= n; i++)
>        {   L[i] = L[i - 1] + L[i - 2];
>        }
>        for(i = 0 ;i <= n; i++)
>        {   cout << L[i] << " ";
>        }
>        cout << endl << endl; 
>    }
>}
>```
>/* ---- 執行結果:
>2
>2 1 3
>5
>2 1 3 4 7 11
>10
>2 1 3 4 7 11 18 29 47 76 123
>20
>2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349 15127
>---- */
>![](https://i.imgur.com/qqvX6ws.png)
>:::

:::

---
### 5. Ackerman’s 函式 A(m, n) 的定義如下： <br> $\qquad \quad A(m,n)=\begin{cases}\qquad \quad n+1 \qquad \qquad \quad \ \ \text{ if } \ \ m=0 \\\qquad A(m-1,1) \qquad \quad \ \ \ \text{ if } \ \ n=0 \\A(m-1,A(m,n-1)) \quad	 \text{ otherwise }\end{cases}$ <br> 這個函式在 $m$ 和 $n$ 的值還不是很大的時候，就已成長的非常快。寫一個遞迴程序序計算它。

:::spoiler 遞迴版本:

```cpp=
int Ackerman(int m, int n)
{   if (m == 0) return n + 1;
    else if (n == 0) Ackerman(m - 1, 1);
    else Ackerman(m-1, Ackerman(m, n - 1));
}
int main(void)
{   int m, n;
    while(cin >> m >> n)
    {   cout << "Answer = " << Ackerman(m, n);
        cout << endl << endl;
    } 
}
```
/* ---- 執行結果:

1 10
Answer = 12

3 10
Answer = 8189

2 15
Answer = 33

---- */

![](https://i.imgur.com/Y6ofI0k.png)

:::

::: spoiler 迴圈版本(僅供參考)：

```cpp=
# include <iostream>
# include <time.h>
using namespace std;
int ack_nonrecursive(int m, int n)
{   int value[500000];
    int Size = 0;
    for (;;)
    {   if (m == 0)
        {   n++;
            if (Size-- == 0) break;
            m = value[Size];
            continue;
        }
        if (n == 0)
        {   m--;
            n = 1;
            continue;
        }
        int index = Size++;
        value[index] = m - 1;
        n--;
    }
    return n;
}
int main()
{   int m, n;
    cin >> m >> n;
    double START,END;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
        {   cout << "mi=" << i << " nj=" << j << "Value=";
            START = clock();
            cout << ack_nonrecursive(i, j) << endl;
            END = clock();
            cout << "Execution Time: " << (END - START) / 
            CLOCKS_PER_SEC << "s" << endl << endl;
        }
}
```
/* ---- 執行結果:
![](https://i.imgur.com/na6KtK8.png) ![](https://i.imgur.com/k57YZJ8.png)
:::
:::spoiler 遞迴與迴圈執行時間比較 (僅供參考；CPU: RAM:  OS: Windows 10)：

| 遞迴版執行時間 | 迴圈版執行時間 | 
| -------- | -------- | 
| ![](https://i.imgur.com/VatBWLg.png) | ![](https://i.imgur.com/15FH7n1.png) |

:::

---
### 6. 給一個正整數 $n$，寫一個程式來判斷 $n$ 是不是其所有因數的總和。亦即是否$n$ 是所有小於 $n$ 的因數總和，其 $1 ≤ t < n$，且 $t$ 整除 $n$。
:::spoiler
```cpp=
void run(int n)
{   int i, sum = 1, map[n] = {0};
    for (i = 2; i < n; i++)
    {   if (n % i == 0)
        {   sum += i;
            map[i] = 1;
        }
    }
    if (sum == n)
    {   cout << "True" << endl;
        cout << n << " = 1"; 
        for (i = 0; i < n; i++)
        {    if (map[i] == 1) cout << " + " << i;
        }
        cout << endl;
        return;
    }
    else
    {   cout << "False" << endl;
        return;
    }
}
int main(void)
{   int n;
    while (cin >> n)
    {   run(n);
        cout << endl;
    }
}
```
/* ---- 執行結果:
10
False
28
True
28 = 1 + 2 + 4 + 7 + 14
100
Flase
496
True
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248*/
![](https://i.imgur.com/KOExPrU.png)
---- */
:::

---
### 7. 假如 $S$ 是一個含有 $n$ 個元素的集合，則 $S$ 的 power set 就是「所有 $S$ 可能的子集合的集合」，例如：假如 $S = \{ a, b, c \}$ ，則 powerset($S$) = $\{∅, \{ a \}, \{ b \}, \{ c \}, \{ a, b \}, \{ a, c \}, \{ b, c \}, \{ a, b, c \} \}$，寫一個遞迴程式來計算 powerset($S$)。

:::spoiler 請見下表：

&emsp;&emsp;&ensp;$S$ &emsp; &emsp; &emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp; powerset($S$)中元素

|{a, b, c}|{}|{c}|{b}|{b, c}|{a}|{a, c}|{a, b}|{a, b, c}|
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
|0/1 Bit|000|001|010|011|100|101|110|111|

由上表可知：求 $S = \{ a, b, c \}$ 的 power set 相當於求 000 \~ 111 的所有 bit patterns!
可設一 0/1 Bit 陣列 (\|BIT\| = \|$S$\|) 與 $S$ 的字元相互對應，recursively 求 Bit 的所有0/1 patterns: powerset(Bit[$k,n$]) = {Bit[$k$]=$0$ \|\| powerest(Bit[$k+1,n$])} ∪ {Bit[$k$]=$1$ \|\| powerest(Bit[$k+1,n$])} 其中 || 表示 0/1 patterns 的串接。呼叫 powerset(Bit[$n-1,n$]) 時即為 boundary condition 可依 Bit[$0:n-1$] 的0/1 pattern 印出對應的 subset of $S$.

```cpp=
# include <stdio.h>
# include <stdlib.h>

char a[10] = { "abcdefgh" };
char b[10];
int Bit[10];
int cnt = 0;
int solCnt;

void printSubset(int Bit [], int n)
{   int i, index = 0;
    for (i = 0; i < n; i++)
        if (Bit[i]) b[index++] = a[i];
    b[index] = '\0';
    printf("{%s}", b);
    if (++cnt < solCnt) printf(", ");
}

void powerSet(int k, int n)
{   if (k == n) printSubset(Bit, n);
    else
    {   Bit[k] = 0;
        powerSet(k + 1, n);
        Bit[k] = 1;
        powerSet(k + 1, n);
    }
}

int main()
{   int i, n;
    printf("Please input the size (n) of the set: n = ");
    while (scanf(" %d", &n), solCnt = pow(2, n),  n != 0)
    {   printf("{");
        powerSet(0, n);
        printf("}\nSize of Powerset = %d.\n\nContinue (0 for exit) n = ", cnt);
        cnt = 0;
    }
    return 1;
}
```
/* ---- 執行結果:

Please input the size (n) of the set: n = 3
{{}, {c}, {b}, {bc}, {a}, {ac}, {ab}, {abc}}
Size of Powerset = 8.

Continue (0 for exit) n = 4
{{}, {d}, {c}, {cd}, {b}, {bd}, {bc}, {bcd}, {a}, {ad}, {ac}, {acd}, {ab}, {abd}, {abc}, {abcd}}
Size of Powerset = 16.

Continue (0 for exit) n = 5
{{}, {e}, {d}, {de}, {c}, {ce}, {cd}, {cde}, {b}, {be}, {bd}, {bde}, {bc}, {bce}, {bcd}, {bcde}, {a}, {ae}, {ad}, {ade}, {ac}, {ace}, {acd}, {acde}, {ab}, {abe}, {abd}, {abde}, {abc}, {abce}, {abcd}, {abcde}}
Size of Powerset = 32.

Continue (0 for exit) n = 7
{{}, {g}, {f}, {fg}, {e}, {eg}, {ef}, {efg}, {d}, {dg}, {df}, {dfg}, {de}, {deg}, {def}, {defg}, {c}, {cg}, {cf}, {cfg}, {ce}, {ceg}, {cef}, {cefg}, {cd}, {cdg}, {cdf}, {cdfg}, {cde}, {cdeg}, {cdef}, {cdefg}, {b}, {bg}, {bf}, {bfg}, {be}, {beg}, {bef}, {befg}, {bd}, {bdg}, {bdf}, {bdfg}, {bde}, {bdeg}, {bdef}, {bdefg}, {bc}, {bcg}, {bcf}, {bcfg}, {bce}, {bceg}, {bcef}, {bcefg}, {bcd}, {bcdg}, {bcdf}, {bcdfg}, {bcde}, {bcdeg}, {bcdef}, {bcdefg}, {a}, {ag}, {af}, {afg}, {ae}, {aeg}, {aef}, {aefg}, {ad}, {adg}, {adf}, {adfg}, {ade}, {adeg}, {adef}, {adefg}, {ac}, {acg}, {acf}, {acfg}, {ace}, {aceg}, {acef}, {acefg}, {acd}, {acdg}, {acdf}, {acdfg}, {acde}, {acdeg}, {acdef}, {acdefg}, {ab}, {abg}, {abf}, {abfg}, {abe}, {abeg}, {abef}, {abefg}, {abd}, {abdg}, {abdf}, {abdfg}, {abde}, {abdeg}, {abdef}, {abdefg}, {abc}, {abcg}, {abcf}, {abcfg}, {abce}, {abceg}, {abcef}, {abcefg}, {abcd}, {abcdg}, {abcdf}, {abcdfg}, {abcde}, {abcdeg}, {abcdef}, {abcdefg}}
Size of Powerset = 128.

Continue (0 for exit) n = 0

Process returned 1 (0x1)   execution time : 51.907 s
Press any key to continue.

![](https://i.imgur.com/UVVyKcI.png)

---- */

:::

---
### 8. 請參考範例1-5、程式1-4，考慮輸入為 $n$ 個圓盤的河內塔搬運問題： <br> &emsp; (a) 實作出有三根支柱，搬運河內塔的遞迴程式； <br> &emsp; (b) 請想想倘若有四根支柱，$n$ 個圓盤該如何搬運？

三根支柱

程式詳解可見講義。以下程序以 C++ Builder 撰寫。
```cpp=
// 以下程序以 C++ Builder 撰寫
void Hanoi3(int disk, String source, String spare, String destination)    //盤數,來源,暫存,目標
{   if	(disk == 0) return;
    Hanoi3(disk - 1, source, destination, spare);
    Form1->Memo1->Lines->Add("Step " + IntToStr(++counter) + ": Move disk " + IntToStr(disk) + " from tower " + source + " to tower " + destination);   //列印盤子的移動
    Hanoi3(disk - 1, spare, source, destination);
}
void __fastcall TForm1::Button4Click(TObject *Sender)
{   n = Edit1->Text.ToInt();   //決定盤子數量
    counter = 0;
    Hanoi3(n, "A", "B", "C");  //呼叫Honoi function
    Memo1->Lines->Add("-- 3 Rods [1] -- " + IntToStr(counter) + " steps in total for " + IntToStr(n) + " disks -----");     
    // Memo2->Lines->Add("-- 3 Rods [1] -- "+IntToStr(counter)+" steps in total for "+IntToStr(n)+" disks -----");
}
// 另一種寫法
void Hanoi(int disk, String source, String spare, String destination, int cur_disk, int diskId)    //盤數,來源,暫存,目標
{   if (Form1->CheckBox1->Checked) PrintMoves(disk, source, destination, spare, cur_disk, diskId);
    if	(disk == 1)       // 移動最頂的盤子到目標
    {   counter++;        // 移動步驟計數+1
        Form1->Memo1->Lines->Add("Step " + IntToStr(counter) + ": Move the top disk from tower " + source + " to tower " + destination);   //列印盤子的移動
    }
    else      //遞迴呼叫Hanoi function執行
    {   Hanoi(disk - 1, source, destination, spare, disk - 1, disk - 1);
        Hanoi(1, source, spare, destination, disk - 1, disk);
        Hanoi(disk - 1, spare, source, destination, disk - 1, disk - 1);
    }
}
```
| $n$ =3, 4 | ![](https://i.imgur.com/7SobLML.png) |
|:------------------------------------:|:------------------------------------:|
| 更多細節 $n$ = 3 | ![](https://i.imgur.com/5Nktym9.png) |




![](https://i.imgur.com/MnO4TGU.png)

![](https://i.imgur.com/8c1SQY2.png)

:::
```cpp=
// 以下程序以 C++ Builder 撰寫
// 方法 1
void Hanoi4(int n, String source, String aux1, String aux2, String destination)
{   if (n == 0) return;
    if (n == 1)
    {	Form1->Memo1->Lines->Add("Step " + IntToStr(++counter) + ": Move disk " + IntToStr(n) + " from tower " + source + " to tower " + destination);   //列印盤子的移動
        return;
    }
    Hanoi4(n - 2, source, aux2, destination, aux1);
    Form1->Memo1->Lines->Add("Step "+IntToStr(++counter)+": Move disk "+IntToStr(n - 1) + " from tower " + source + " to tower " + aux2);   //列印盤子的移動
    Form1->Memo1->Lines->Add("Step " + IntToStr(++counter) + ": Move disk " + IntToStr(n) + " from tower " + source + " to tower " + destination);   //列印盤子的移動
    Form1->Memo1->Lines->Add("Step " + IntToStr(++counter) + ": Move disk " + IntToStr(n - 1) + " from tower " + aux2 + " to tower " + destination);   //列印盤子的移動
    Hanoi4(n - 2, aux1, source, aux2, destination);
}
// 方法 2
void Hanoi4_2(int n, String source, String aux1, String aux2, String destination)
{   if (n == 0)	return;
    if (n == 1)
    {   Form1->Memo1->Lines->Add("Step " + IntToStr(++counter) + ": Move the top disk from tower " + source + " to tower " + destination);   //列印盤子的移動
        return;
    }
    if (n == 2)
    {	Form1->Memo1->Lines->Add("Step " + IntToStr(++counter) + ": Move the top disk from tower " + source + " to tower " + aux2);   
        Form1->Memo1->Lines->Add("Step " + IntToStr(++counter) + ": Move the top disk from tower " + source + " to tower " + destination);   
        Form1->Memo1->Lines->Add("Step " + IntToStr(++counter) + ": Move the top disk from tower " + aux2 + " to tower "+destination);   //列印盤子的移動
        return;
    }
	Hanoi4_2(n / 2, source, aux2, destination, aux1);
	Hanoi4_2(n - 1 - n / 2, source, aux1, destination, aux2);
    Form1->Memo1->Lines->Add("Step " + IntToStr(++counter) + ": Move the top disk from tower " + source + " to tower " + destination);   
    Hanoi4_2(n - 1 - n / 2, aux2, aux1, source, destination);
    Hanoi4_2(n / 2, aux1, source, aux2, destination);
}
```
四根支柱
上列有兩種搬運方法！
|               $n$ = 5                | ![](https://i.imgur.com/e8QUgZT.png)                     |
|:------------------------------------:|:------------------------------------:|
| 次數比較 | ![](https://i.imgur.com/WkEU3Kr.png) |


:::

---
### 9. 比較 $n^3$ 和 $2^n$ 這兩個函式，計算出哪個 $n$ 值會使後者大於前者。

:::spoiler

當 $n = 10$ 時,  $n^3 =1000 < 2^n = 1024$; 當 $n > 10$ 時, $n^3 < 2^n$。

:::

---
### 10. 使用數學歸納法證明： <br> &emsp; (a) $\sum\limits_{1≤i≤n}{i}=\dfrac{n(n+1)}{2},n≥1;$ <br> &emsp; (b)$\sum\limits_{1≤i≤n}{i^2}=\dfrac{n(n+1)(2n+1)}{6},n≥1;$ <br> &emsp; (c\) $\sum\limits_{1≤i≤n}{x^i}=\dfrac{x^{n+1}-1}{x-1},x≠1,n≥0;$ <br>  &emsp; (d) $\sum\limits_{1≤i≤n}{2i-1}=n^2。$


>:::spoiler (a)
>
>&ensp; 當 $n$ = $1$ 時, $\sum\limits_{i=1}^{1}{i} = 1 = \tfrac{1(1+1)}{2}$ 成立;
>&ensp; 設 $n$ = $k$, $\sum\limits_{i=1}^{k}{i} = \tfrac{k(k+1)}{2}$ 成立;
>&ensp;則當 $n$ = $k+1$, $\sum\limits_{i=1}^{k+1}{i} = \sum\limits_{i=1}^{k}{i} + (k+1)$
>假設: 
>&emsp; $\begin{eqnarray}
>\sum\limits_{i=1}^{k+1}{i} &=& \tfrac{k(k+1)}{2} + (k+1) \nonumber \\
>~&=& \tfrac{k(k+1)}{2} k(k+1) + \tfrac{2(k+1)}{2} \nonumber \\
>~&=& (k+1) \tfrac{[(k+1)+1]}{2}
>\end{eqnarray}$
>&emsp;&ensp;當 $n$ = $k$ + $1$ 時原式亦成立，則根據數學歸納法，即可得證。
>
>:::
>
>:::spoiler (b)
>
>&ensp; 當 $n$ = $1$ 時, $\sum\limits_{i=1}^{1}{i^2} = 1 = \tfrac{1×2×3}{6}$ 成立;
>&ensp; 設 $n$ = $k$, $\sum\limits_{i=1}^{k}{i^2} = \tfrac{k(k+1)(2k+1)}{6}$ 成立;
>&ensp;則當 $n$ = $k+1$, $\sum\limits_{i=1}^{k+1}{i^2} = \sum\limits_{i=1}^{k}{i^2} + (k+1)^2$
>假設: 
>&emsp; $\begin{eqnarray}
>\sum\limits_{i=1}^{k+1}{i^2} &=& \tfrac{k(k+1)(2k+1)}{6} + (k+1)^2 \nonumber \\
>~&=& (k+1) \tfrac{[k(2k+1)+6(k+1)]}{6} \nonumber \\
>~&=& (k+1) \tfrac{2k^2+7k+6}{6} \nonumber \\
>~&=& \tfrac{k+1[(k+1)+1]+[2(k+1)+1]}{6}
>\end{eqnarray}$
>&emsp;&ensp;當 $n$ = $k$ + $1$ 時原式亦成立，則根據數學歸納法，即可得證。
>
>:::
>
>:::spoiler (c\) 
>
>&ensp; 當 $n$ = $0$ 時, $\sum\limits_{i=0}^{0}{x^i} = x^0 = 1 =\tfrac{x-1}{x-1}$ 成立;
>&ensp; 設 $n$ = $k$, $\sum\limits_{i=0}^{k}{x^i} = \tfrac{x^{k+1}-1}{x-1}$ 成立;
>&ensp;則當 $n$ = $k+1$, $\sum\limits_{i=0}^{k+1}{x^i} = \sum\limits_{i=0}^{k}{x^i} + x^{k+1}$
>假設: 
>&emsp; $\begin{eqnarray}
>\sum\limits_{i=0}^{k+1}{x^i} &=& \tfrac{x^{k+1}-1}{x-1} + x^{k+1} \nonumber \\
>~&=& \tfrac{x^{k+1}-1}{x-1}  + \tfrac{(x-1)x^{k+1}}{x-1} \nonumber \\
>~&=& \tfrac{x^{k+1}-1+x^{k+2}-x^{k+1}}{x-1} \nonumber \\
>~&=& \tfrac{x^{k+2}-1}{x-1} \nonumber \\
>~&=& \tfrac{x^{(k+1)+1}-1}{x-1} \nonumber \\
>\end{eqnarray}$
>&emsp;&ensp;當 $n$ = $k$ + $1$ 時原式亦成立，則根據數學歸納法，即可得證。
>
>:::
>
>:::spoiler (d) 
>
>&ensp; 當 $n$ = $1$ 時, $\sum\limits_{i=1}^{1}{(2i-1)} = 1 = 1^2$ 成立;
>&ensp; 設 $n$ = $k$, $\sum\limits_{i=1}^{k}{(2i-1)} = k^2$ 成立;
>&ensp;則當 $n$ = $k+1$, $\sum\limits_{i=1}^{k+1}{(2i-1)} = \sum\limits_{i=1}^{k}{(2i-1)} + 2(k+1)-1$
>假設: 
>&emsp; $\begin{eqnarray}
>\sum\limits_{i=1}^{k+1}{(2i-1)} &=& k^2+2(k+1)-1 \nonumber \\
>~&=& k^2+2k+1 \nonumber \\
>~&=& (k+1)^2 \nonumber \\
>\end{eqnarray}$
>&emsp;&ensp;當 $n$ = $k$ + $1$ 時原式亦成立，則根據數學歸納法，即可得證。
>
>:::

:::

---
### 11. 分析下列程式的時間複雜度—計算出 $x$ 的值（初始值皆為0），並以大*O*表示其時間複雜度：


(a)
```cpp=
for (i = 1; i <= n; i++) 
    for (j = 1; j <= i; j++) 
        for (k = 1; k <= j; k++) 
            x++; 
```
(a) 利用重複物件的組合來解迴圈執行次數：
$\displaystyle\quad {r+n-1 \choose r} \\ 
=\displaystyle{3+n-1 \choose 3} \\
=\dfrac{n(n+1)(n+2)}{6} \\   
= O(n^3)$
$x$ 會印出 $\frac{n(n+1)(n+2)}{6}$ 的值(視所輸入的 $n$ 而定)。
此題可想成：方程式 $x_1+x_2+...+x_n=3\ (r=3)$ 非負整解的個數！或：將3個一樣的球放入 $n$ 個不一樣的容器(編號: $1, 2, ... , n$)；若此3個球放入的容器編號分別為 $y_1, y_2, y_3$ (球可能放入同一容器)，而其排序結果為：$a\ge b\ge c$；吾人即將迴圈控制變數 $i, j, k$ 分別設定為 $a, b, c$，那麼 $i, j, k$ 有多少可能即由 $a, b, c$ 的個數決定----某一種球放入容器的放法，即對應某一組 $i, j, k$ 下 $x$++ 的執行！兩者有 one to one correspondence (1對1的對應關係)----而後者共有
$\quad {r+n-1 \choose r} \\ 
={3+n-1 \choose 3} \\
=\frac{n(n+1)(n+2)}{6}$ 種可能。
(b)
```cpp=
i = 1; 
while (i <= n) 
{   x++; 
    i++; 
}
```
(b) $n$ = *O*($n$)

(c\)
```cpp=
for (i = 1; i <= n; i++) 
    for (j = 1; j <= i; j *= 2) 
        x++; 
```
(c\) $O(nlogn)$ 
可列出註標 $i$, $j$ 的值，與當時$x$++的執行次數，之後加總之。

| $i$ | $1$ | $2$ | $3$ | $4$ | ... | $n$ |
|-  |---| - | --|  -|-----|-- |
|$j$  |$1$| $1, 2$ | $1, 2$| $1, 2, 4$|...|$1, 2, 4, ... n$ |
|#  |$1$| $2$ | $2$| $3$|...|$logn+1$ |
|#  |$log1+1$| $log2+1$ | $log3+1$| $log4+1$|...|$logn+1$ |

$log1+1+log2+1+...+logn+1$ 
$=\sum_{k=1}^{n}logn+n$
$= log(1\times 2\times ... \times n)+n$
$= log(n!)+n \\ \le log(n^n)+n = nlogn+n\\   =O(nlogn)$


(d)
```cpp=
for (i = 1; i <= n; i *= 2) 
    for (j = 1; j <= i; j++) 
        x++;
```


(d) $O(n)$

| $i$ | $1$ | $2$ | $4$ | $8$ | ... | $n$ |
|-  |---| - | --|  -|-----|-- |
|$j$  |$1$| $1,2$ | $1,2,3,4$| $1$~$8$|...| $1$~$n$ |
|#  |$1$| $2$ | $4$| $8$|...|$n$ |
|#  |$2^0$| $2^1$ | $2^2$| $2^3$|...|$2^{logn}$ |

$2^0+2^1+2^2+ ... + 2^{logn} \ (引用等比級數和的公式)\\ 
=\frac{2^0(2^{logn+1}-1)}{2-1} \\ =2^{logn+1}-1\\
=2^{logn}\times 2-1\\
=2n-1\\
=O(n)$

:::

---
### 12.證明下列等式是正確的： <br> &emsp; (a) $5n^2-6n = Θ(n^2)$ <br> &emsp; (b) $n! = Ο (n^n)$ <br> &emsp; (c\) $2n^22^n+nlogn = Θ(n^22^n)$ <br> &emsp; (d) $\sum\limits_{i=0}^{n}{i^2}=Θ(n^3)$ <br>  &emsp; (e) $\sum\limits_{i=0}^{n}{i^3}=Θ(n^4)$ <br> &emsp; (f) $n^{2^n}$+$6×2^n$ = $Θ$($n^{2^n})$ <br> &emsp; (g) $n^3+10^6n^2 = Θ(n^3)$ <br>  &emsp; (h) $6n^3/(logn+1) =Ο (n^3)$ <br>  &emsp; (i) $n^{1.001}+nlogn = Θ(n^{1.001}    )$ <br>  &emsp; (j) $n^k+ε+n^klogn = Θ(n^k+ε) \text{ for all k and }ε, k ≥ 0,\text{and } ε > 0$ <br>  &emsp; (k) $10n^3+15n^4+100n^22^n = Ο (100n^22^n)$ <br>  &emsp; (l) $33n^3+4n^2 = Ω (n^2)$ <br>  &emsp; (m) $33n^3+4n^2 = Ω (n^3)$

:::spoiler 以下請以 (a) 的詳解，推演其他題目的解答！

>:::spoiler (a)
>
>令 $f(x) = 5n^2-6n$ 和 $g(n) = n^2$。
>我們嘗試證明 $c_1g(n) ≤ f(n) ≤ c_2g(n)$。 意即, $c_1n^2 ≤ 5n^2-6n ≤ c_2n^2 => c_1n ≤ 5n-6 ≤ c_2n$。
>因為存在 $c_1 = 1, c_2 = 5, n_0 = 2$, 使得 $n ≥ 2$ 後，$n^2 ≤ 5n^2-6n ≤ 5n^2$。
>
>:::
>
>:::spoiler (b)
>
>$g(n) = n^n$
>$cn^n ≥ n! => cn^n ≥ n×(n-1)×(n-2)×...×1$
>因為存在 $c = 1, n_0 = 1$, 使得 $n ≥ 1$後，$n^n ≥ n!$。
>
>:::
>
>:::spoiler (c\)
>
>$g(n) = n^22^n$
>$c_1n^22^n ≤ 2n^22^n+nlogn ≤ c_2n^22^n => c_1n2^n ≤ 2n2^n+logn ≤ c_2n2^n$
>因為存在 $c_1 = 1 , c_2 = 6, n_0 = 1$, 使得 $n ≥ 1$後，$n2^n ≤ 2n2^n+logn ≤ 6n2^n$。
>
>:::
>
>:::spoiler (d)
>
>$g(n) = n^3$
>$c_1n^3 ≤ \frac{n(n+1)(2n+1)}{6} ≤ c_2n^3 => c_1n^2 ≤ \frac{(n+1)(2n+1)}{6} ≤ c_2n^2$
>因為存在 $c_1 = \frac{1}{3}, c_2 =1 , n_0 =1$，使得上式成立。
>
>:::
>
>:::spoiler (e)
>
>$g(n) = n^4$
>$c_1n^4 ≤ [\frac{n(n+1)}{2}]^2 ≤ c_2n^4 => c_1n^4 ≤ \frac{n^4+2n^3+n^2}{4} ≤ c_2n^4 => c_1n^2 ≤ \frac{n^2+2n+1}{4} ≤ c_2n^2$
>因為存在 $c_1 = \frac{1}{6}, n_0 =1$，使得上式成立。(請看下圖)
>![](https://i.imgur.com/iYVkGNg.png)
>
>:::
>
>:::spoiler (f)
>
>$g(n) = n^{2^n}$
>$c_1n^{2^n} ≤ n^{2^n}+6×2^n ≤ c_2n^{2^n}$ 
>令 $c_1 = 1, c_2 = 4, n_0 = 2$，當 $n ≥ 2$， $1×n^{2^n} ≤ n^{2^n}+6×2^n$  且 $n^{2^n}+6×2^n ≤ 4n^{2^n}$  
>(“$≤$” 必成立；後者請看：令 $n = n_0 = 2$， $n^{2^n}+6×2n  = 2^4+6×2 = 28 ≤ 4n^{2^n} = 4×2^4 = 64$)  
>亦即 $n^{2^n} ≤ n^{2^n}+6 ×2^n  ≤ 4n^{2^n}$ 成立，於是 $n^{2^n}+6×2^n = Θ(n^{2^n})$。
>
>:::
>
>:::spoiler (g)
>
>$g(n) = n^3$
>$c_1n^3 ≤ n^3+10^6n^2 ≤ c_2n^3 => c_1n ≤ n+10^6 ≤ c_2n$
>因為存在 $c_1 = 1, c_2 = 10, n_0 = 10^6$, 使得 $n ≥ 10^6$後，$n ≤ n+10^6 ≤ 10n$
>
>:::
>
>:::spoiler (h)
>
>$g(n) = n^3$
>$cn^3 ≥ \frac{6n^3}{logn+1} => c ≥ \frac{6}{logn+1}$
>因為存在 $c = 7, n_0 = 1$
>使得 $n ≥ 1$ 後，$7 ≥ \frac{6}{logn+1}$
>
>:::
>
>:::spoiler (i)
>
>先證明 $n^{0.001}+logn = Θ(n^{0.001})$！($log$ 以 $log_2$ 做運算)
>(1) 取 $c=500, n_0 = 2^{1000}$ 可得 $log(2^{1000}) = 1000  ≤  cn_0^{0.001} = 500×(2^{1000})^{0.001}=1000$
>此式對 $n ≥ n_0$ 皆成立，所以 $logn = O(n^{0.001})$
>(2) 由 $n^{0.001} ≤  n^{0.001}+logn ≤  2n^{0.001}$ 可知 $n^{0.001}+logn = Θ(n^{0.001})$。($n^{0.001}+logn$ 介於 $1n^{0.001}和 2n^{0.001}$ 之間)
>原題：$n^{1.001}+nlogn = n(n^{0.001}+logn) = nΘ(n^{0.001}) = Θ(n^{1.001})$。
>一般而言, 在 $a, b>0$ 下，$\displaystyle\lim_{n\to\infty}{\frac{(logn)^a}{n^b}}=0$。
>https://math.stackexchange.com/questions/2094165/is-n0-01-big-omega-or-big-o-of-logn
>
>:::
>
>:::spoiler (k)
>
>$g(n) = 100n^22^n$
>$c×100n^22^n ≥ 10n^3+15n^4+100n^22^n => c×100×2^n ≥ 10n+15n^2+100×2^n$
>因為存在 $c = 5, n_0 = 1$
>使得 $n ≥ 1後，500×2^n ≥ 10n+15n^2+100×2^n$
>
>:::
>
>:::spoiler (l)
>
>$g(n) = n^2$
>$cn^2 ≤ 33n^3+4n^2 => c ≤ 33n+4$
>因為存在 $c = 1, n_0 = 1$
>使得 $n ≥ 1$ 後，$1 ≤ 33n+4$
>
>:::
>
>:::spoiler (m)
>
>$g(n) = n3$
>$cn^3 ≤ 33n^3+4n^2 => cn ≤ 33n+4 => (c-33)n ≤ 4$
>因為存在 $c = 1, n_0 = 1$
>使得 $n ≥ 1$ 後，$-32n ≤ 4$
>
>:::
>
:::
---
### 13. 證明下列等式是錯誤的： <br> &emsp;  (a) $10n^2+9 = O(n)$ <br>  &emsp; (b) $n^2logn = Θ(n^2)$ <br>  &emsp; (c\) $\frac{n^2}{logn} = Θ(n^2)$ <br>  &emsp; (d) $n^32^n+6n^23^n = O(n^32^n)$

::: spoiler

(a)
$g(n) = n$
$cn ≥ 10n^2+9$
因為找不到合適的 $c, n_0$
使得 $n ≥ n_0$ 後，$cn ≥ 10n^2+9$

(b)
$n^2logn = Θ(n^2)$ 若為真，則存在常數 $c_1、c_2$ 和 $n_0$ (由定義可知 $n > n_0$)，可得
到 $c_1n^2 ≤ n^2logn ≤ c_2n^2$。$n^2logn  ≤ c_2n^2 => logn  ≤ c_2$ ，
選擇 $n > \max\{n_0, 2c_2\}$，會產生矛盾。

(c\)
$\frac{n^2}{logn} = Θ(n^2)$ 若為真，則存在常數 $c_1、c_2$ 和 $n_0$ (由定義可知 $n > n_0$)，可得到 
$c_1n^2 ≤ n^2/logn ≤ c_2n^2$。$c_1n^2 ≤ n^2/logn=> logn  ≤ 1/c_1$  會產生矛盾，因為左邊當 $n$ 遞增時會跟著遞增，但右邊則為常數。

(d)
$g(n) = n^32^n$
$cn^32^n ≥ n^32^n+6n^23^n => cn2^n ≥ n2^n+6×3^n$
因為找不到合適的 $c, n_0$
使得 $n ≥ n_0$ 後，$cn^32^n ≥ n^32^n+6n^23^n$

:::

---
## 第二章 陣列 習題解答
---
### 1. 有多少元素可以存在以下的陣列中（註標範圍 [$x$:$y$] 中 $x$ 表示下界，$y$ 表示上界）： <br>  &emsp; (a) A[$0:n$]； <br>  &emsp; (b) B[$-23:29$];  <br>  &emsp; (c\) C[$-1:n$][$1:m$]； <br>  &emsp; (d) D[$-n:0$][$1:3$]；

:::spoiler

(a) $n+1$
(b) $23+1+29 = 53$
(c\) $(1+1+n)×m = m(n+2)$
(d) $(n+1)×3 = 3(n+1)$
註：$C$ 的陣列宣告時只需要陣列型態、名稱和大小；其註標從 $0$ 開始，而且沒有下界、上界範圍的考量。這個題目旨在希望讀者對陣列內的個數／內容與註標定址有較廣泛的聯想。若希望用 "下界...上界" 來定位陣列元素，可以用指標來完成。請看下面的例子：

![](https://i.imgur.com/RLkNd1E.png)

其中前三行是程式的設定（第3行以 p 指向 A[5] 的住址）、後四行表列展示 A[$0$], A[$1$], ... , A[$9$] 和 $*(p-5), *(p-4), ... , *(p+4)$ 各自存放的內容；可以清楚看出 A[$0$] 與 $*(p-5)$ 、A[$1$] 與 $*(p-4)$、 ... 、A[$9$] 與 $*(p+4)$ 的值是一樣的；亦即：對 $p$ 而言，可用 $-5...9$ 中的註標來定址陣列 A。用指標的概念，可使陣列的註標定址關係有更大的彈性。

:::

---
### 2.導出陣列 $A[l_1…u_1][l_2…u_2]...[l_n…u_n]$ 的元素 $A[i_1][i_2]…[i_n]$ 的位址公式，$l_j ≤ i_j≤ u_j，1 ≤ j ≤ n$。假設每個元素佔 $l$ 個字元組，而$α$ 是 $A[l_1][l_2]...[l_n]$ 的位址，且：  <br>  &emsp; (a) 陣列 $A$ 是以列為優先存放；  <br>  &emsp; (b) 陣列 $A$ 是以行為優先存放。

:::spoiler
:::
&emsp;令 $b_i = u_i-l_i+1$，$d_j = i_j-l_j+1，s_j = b_jb_{j+1}...b_n$，$t_k = b_1b_2...b_k$ 其中 $1 ≤ i$, $j ≤ k ≤ n$ 且 $s_{n+1} = 1 = t_0$；則 $A[i_1][i_2]…[i_n]$ 的位址：
(a)
$α+l×\sum_{i=1}^{n}d_is_{i+1}$
(b)
$α+l×\sum_{i=1}^{n}d_it_{i-1}$

:::

---
### 3. 寫一個程序來估算每個不同的字元在字串中出現的次數，用適當的資料來測試你的函式。

:::spoiler 以下程式以英文小寫字元 'a', 'b', ... , 'z' 為例。

```cpp=
# include <stdio.h>
void charFrequency(char s[], int len)
{   int freq[26], i;
    char base = 'a';
    for (i = 0; i  <  26; i++) freq[i] = 0;
    for (i  =  0; i  <  len; i++) freq[s[i]  -  base]++;
    for (i  =  0; i  <  26; i++)
        if (freq[i] != 0) printf("%c : %d\n", base  +  i, freq[i]);
}
int main()
{   char s [256];
    int len;
    while (scanf("%s", s)!=EOF)
    {   printf("s = %s\n", s);
        for (len  =  0; s[len] != '\0'; len++);
        printf("len = %d\n", len);
        charFrequency(s, len);
    }
    return 1;
}
```
/* ---- 執行結果:
asgfagsfgafsgafsgfagsfagfsg
s = asgfagsfgafsgafsgfagsfagfsg
len = 27
a : 6
f : 7
g : 8
s : 6
trwretwretrwtertwretuqywuyuywueyuwyueywuyeuyw
s = trwretwretrwtertwretuqywuyuywueyuwyueywuyeuyw
len = 45
e : 7
q : 1
r : 6
t : 6
u : 8
w : 9
y : 8
nvjfnjvfnjvnfjnvjfnvjnfjnjfvfnfjnvjfnjvnjfnvjf
s = nvjfnjvfnjvnfjnvjfnvjnfjnjfvfnfjnvjfnjvnjfnvjf
len = 46
f : 11
j : 13
n : 13
v : 9
---- */

![](https://i.imgur.com/BCWc1Gq.png)

:::

---
### 4. 寫一個程序，輸入為一個字串 $text$ 和一個常數 $k$，列出在 $text$ 中出現次數前 $k$ 高的字元及其出現次數。

:::spoiler

```cpp=
char Char[26];
int Count[26];
char text[n];
int Order[k], Max, MaxIndex;
void TextOrder( char text[], int k)
{   for ( int g = 0;g < 26;g++)
    {   for ( int s = g + 1;s < 26;s++)
        {   Max = Count[g]; 
            MaxIndex = g;
            if ( Count[s] > Max)
            {   Max = Count[s]; 
                MaxIndex = s;
            }
            Order[k] = MaxIndex; 
        }
    } 
    for ( int i 0;i < k;i++) 
        cout << Char[Order[i]] << ” ” << Count[Order[i]] << endl; 
}
```

:::

---
### 5. 寫一個函式，它會接受一個字串 text 和兩個整數 start 和 length，這個函式會從字串 text 的第 start 個字元起刪除 length 個字元，而傳回產生新的字串。

:::spoiler

```cpp=
char[] deleteText(char text[], int start, int length)
{   int k; 
    int groot[256];
    // int n=text.length();
    for (i = 0, k = 0; i < length; i++)
    {   if (i < start || i >= (start + length) )
            groot[k++] = text[i];      
    }
    // if ( text[i] == “\0”) return text;
    groot[k] = '\0';
    return groot; 
}
// 胡乃文、楊駘、史孟仟 提供 1036

```

:::

---
### 6. 使用最少的記憶空間，寫一個程序：給一個陣列 A[$n$]，請產生 Z[$n$]，使得Z[$0$] = A[$n−1$], Z[$1$] = A[$n−2$], …, Z[$n−2$] = A[$1$], Z[$n−1$] = A[$0$]。

:::spoiler

```cpp=
void copy_reverse(int A[], int Z[])
{   int i;
    for (i = 0; i < n; i++) Z[i] = A[n - i - 1];
}
```

:::

---
### 7. 假設有 $n$ 個串列，$n > 1$，它們用一維陣列 space[$m$] 來表示。令 front[$i$] 是指到第 $i$ 個串列第一個元素的前一個位置，rear[$i$] 是指到第 $i$ 個串列最後一個元素的位置，假設 rear[$i$] ≤ front[$i+1$]，$0 ≤ i < n$，且 front[$n$] = $m−1$，這些串列所能做的運算就是插入和刪除。 <br> &emsp; (a) 找出 front[$i$] 和 rear[$i$] 的適當的起始和終止條件。 <br> &emsp; (b) 寫一個程序 Insert(int i, int j, int item)，使其能在串列 $i$ 的第 ($j-1$) 個元素後面插入 item，這個程序在 space 已經有了 $m$ 個元素的情況下，不允許插入的動作。

:::spoiler

(a)
起始條件：front[$i$] = rear[$i$] = $i * ⎣\frac{m}{n}⎦ -1$， $0 ≦ i＜n$ 且 front[$n$] = $m-1$。 
刪除終止條件：只有當 front[$i$] = rear[$i$]成立時，第 $i$ 條字串會為空。
新增終止條件：只有當 rear[$i$] = front[$i+1$]成立時，第 $i$ 條字串已滿。

(b)
```cpp=
int Insert(int i, int j, int item) 
{   if ( rear[i] - front[i] < j - 1) return 0; 
    if (rear[i] == front[i + 1]) //判斷第 i 條字串是否已滿 
        ListFull( );
    if (rear[i] < front[i + 1]) //space found 
    {    for (int k = rear[i]; k >= j; k--)
             space[k + 1] = space[k]; 
         space[j] = item; 
         return 1; 
    } 
    else return 0; 
}
```

:::

---
### 8. 承上題，寫一個程序 int Delete(int i, int j) 來刪除第 $i$ 個串列的第 $j$ 個元素，並傳回它的值。

:::spoiler

```cpp=
int Delete(int i, int j) 
{   if (rear[i] - front[i] < j - 1) return 0; 
    if (rear[i] == front[i]) ListEmpty( );
    if (front[i + j - 1] != NULL) 
    {    int data = space[i + j - 1];
         space[i + j - 2]->next = space[i + j - 1]->next;
         free(space[i + j - 1]);
         return data; 
    } 
} 
```

:::

---
### 9. 當一個陣列的所有元素都排在其主對角線及其下方或上方，這個矩陣就叫做「三角矩陣」(triangular matrix)。圖 2-20 表示出「下三角」(lower triangular) 和「上三角」(upper triangular) 矩陣，其中非 0 元素標示為 X。 <br>  &emsp;  &emsp; ![](https://hackmd.io/_uploads/SkCJ-5apn.png) <br><br> 將 $n×n$ 的下（上）三角矩陣存放在記憶體中，$0$ 的值不存，請為陣列元素[$i$][$j$] 求出其位址公式，$0 ≤ i, j ≤ n−1$（每個元素佔 $l$ 個字元組，而 $α$ 為陣列第一個非 $0$ 元素（位於[$0$][$0$]）在記憶體中的位址）。

::: spoiler (a) 下三角
以列為主： A[$i$][$j$]（$i ≥ j$） = $α + l[\frac{i(i+1)}{2} + j]$
以行為主： A[$i$][$j$]（$i ≥ j$） = $α + l[\frac{(2n-j+1)j}{2} + (i − j)]$
:::
::: spoiler (b) 上三角
以列為主：A[$i$][$j$]（$i ≤ j$） = $α + l[\frac{(2n-i+1)i}{2} + (j − i)]$
以行為主：A[$i$][$j$]（$i ≤ j$） = $α + l[\frac{j(j+1)}{2} + i]$
:::

---
### 10. 假設 A 和 B 是兩個 $n×n$ 的下三角矩陣，則它們的元素個數總和為 $n(n+1)$。設計出一種方法把這兩個矩陣同時儲存在一個陣列 C[$n$][$n+1$] 裡（提示：把 A 以 C 的下三角方式儲存，B 的轉置矩陣則存在 C 的上三角矩陣）。再設計一個演算法，從陣列 C 中找出 A[$i$][$j$] 和 B[$i$][$j$] 的值，$0 ≤ i, j ≤ n−1$。
:::spoiler
:::
>:::spoiler (a) 將陣列 A、B 存入陣列 C 中
>:::
>```cpp=
>for (i = 0; i < n; i++) 
>{   for (j = 0; j <= i; j++) 
>         C[i][j] = A[i][j]; 
>     for (j = i+1; j <= n; j++) 
>         C[i][j] = B[j-1][i]; 
>}
>// or simply
>for (i = 0; i < n; i++) 
>     for (j = 0; j <= n; j++)
>          C[i][j] = (i>=j) ? A[i][j] : B[j-1][i]; 
>```
>:::spoiler (b) 從陣列 C 找出陣列 A、B
>:::
>```cpp=
>for (i = 0; i < n; i++)
>{   for (j = 0; j <= n; j++)
>     {   if (i >= j) A [i][j] = C[i][j]; 
>         else B[j-1][i] = C[i][j]; 
>     }
>}
>>// or simply
>for (i = 0; i < n; i++) 
>     for (j = 0; j <= i; j++)
>     {    A[i][j] = C[i][j];
>          B[i][j] = C[j][i+1];
>     }
>```
:::
---
### 11. 一個「三對角線矩陣」(tri-diagonal matrix) 為一個方陣，其中在主對角線及其相鄰的兩個對角線以外的元素均為 $0$ (如圖 2-21)。令 $A$ 為一 $n×n$ 的三對角線矩陣，將 $A$ 中三個對角線所形成帶狀區域上的元素，以列為優先，儲存在一個一維陣列 $M$ 中（$A[0][0]$ 存放在 $M[0]$ 中）。設計一個演算法，輸入 $A[i][j]$ 時，可求得 $k$；即 $A[i][j]\ 存在\  M[k]$ 中，$0 ≤ i, j ≤ n−1$。
&emsp;  &emsp;  &emsp;  &emsp;  &emsp;  &emsp;  &emsp;  &emsp; ![](https://hackmd.io/_uploads/S17u-cT62.png_center =330x)


::: spoiler *k* = 2*i*+*j* 
讀者可與以下表格比對，其中 $|i-j|\le 1$。
|   |$0$  |$1$  |$2$  |$3$  |$4$  |...|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|$0$  |$0$  |$1$  |   |   |   |   |
|$1$  |$2$  |$3$  |$4$  |   |   |   |
|$2$  |   |$5$  |$6$  |$7$  |   |   |
|$3$  |   |   |$8$  |$9$  |$10$ |   |
|...|   |   |   |   |   |   |

亦可以對角線的觀點來想！
令主對角線為 $D$。自上矩陣可知 $D$ 中元素的編號恰為 $3i$，$D$ 下方對角線的元素編號為 $3i-1$；$D$ 上方對角線的元素編號為 $3i+1$。而三者可用 $3i+(j-i)=2i+j$ 統一表示！亦即：
$k=2i+j$。

:::
---
### 12. 一個「方形帶狀矩陣」(square band matrix) $D_{n,a}$ 是一個 $n×n$ 的矩陣，其中所有可能的非零元素，均集中在以主對角線為中心的帶狀區域上（此帶狀區域外的元素皆為 $0$）；此帶狀區域包括了主對角線與其上和其下各 $a−1$ 條對角線（如圖 2-22 (a) 和 (b)，圖 2-22 (b) 是一 $D_{5,2}$ 的例子）。請回答： <br> &emsp; (a) 在此帶狀 $D_{n,a}$ 中有多少個元素？ <br> &emsp; (b) 對於帶狀 $D_{n,a}$ 中的元素 $d_{ij}$ 而言，$i$ 與 $j$ 之間的關係為何？ <br> &emsp; (c\) 假設帶狀 $D_{n,a}$ 以對角線為主，並從最低的對角線開始，循序儲存在陣列 *A* 中。例如，圖 2-22 (b) 中的帶狀矩陣 $D_{5,2}$ 的表示法如下： <br> ![](https://i.imgur.com/R1IPfO6.png) <br> 找出在 $D_{n,a}$ 的下帶狀區域中的任一元素 $d_{ij}$ 的定址公式，即輸入 $i$ 和 $j$，求出 $k$，$d_{ij}$ = $A[k]$。 <br> &emsp;  &emsp;  &emsp;  &emsp;  &emsp;  &emsp;  ![](https://i.imgur.com/cIZcJgX.png_center =360x) <br> &emsp;  &emsp;  &emsp;  &emsp;  &emsp;  &emsp;  &emsp;  &emsp;  &emsp;![](https://hackmd.io/_uploads/HkVaQcpp2.png_center =220x)


::: spoiler
(a) 主對角線有 $n$ 個元素，以其為基準，上方的 $1, 2, ... , a-1$ 條對角線分別有 $n-1,\ n-2,\ ...\ ,\ n-a+1$ 個元素，如下圖左；
| ![](https://i.imgur.com/wkNsnYS.png) | ![](https://i.imgur.com/1EyicUD.png)  |
|----|----|


於其下方的 $a-1$ 條對角線亦然。加總所有元素可得：
$\begin{split}
\quad &n+2\sum\limits_{t=1}^{n-a+1}{n-t}\\ 
&=n+2[(n-1)+(n-2)+...+(n-a+1)] \\
&=n+2\frac{(2n-a)(a-1)}{2} \\
&=n+(2n-a)(a-1) \\
&=n+(2na-a^2-2n+a) \\
&=2na-a^2-n+a 
\end{split}$

上式亦可列為：

$\begin{eqnarray}
n+2\sum\limits_{t=n-a+1}^{n-1}{t} &=& n+2[(n-a+1)+(n-a+2)+...+(n-1)] \nonumber \\
~&=& n+2\frac{(2n-a)(a-1)}{2} \nonumber \\
~&=& n+(2n-a)(a-1)
\end{eqnarray}$

(b) 請參考上圖右，令主對角線為 $D$：
(b.1) 若 $i=j$，$A[i][j]$ 恰在 $D$ 上；
(b.2) 若 $i<j\ 且\ j-i = t，A[i][j]$ 在 $D$ 上方的第 $t$ 條對角線，$1 \leq t\leq a-1$；
(b.3) 若 $i>j\ 且\ i-j = t，A[i][j]$ 在 $D$ 下方的第 $t$ 條對角線，$1 \leq t\leq a-1$。
總結以上討論：$|i - j| < a$。

(c\) 令 $k$ 為由最低對角線開始存放一維陣列中 $A[i][j]$ 的對應註標。如 (b) 所列：
(c.1) 若 $i=j$，$A[i][j]$ 恰在 $D$ 上； 所有下帶狀元素先存，所以有 
$n+2[(n-1)+(n-2)+...+(n-a+1) = \frac{(2n-a)(a-1)}{2}$ 個
存在 $D$ 元素之前；而且在 $A[i][j]=A[i][i]$ 之前，還有 $i$ 個 $D$ 中元素，所以 $k = i+\frac{(2n-a)(a-1)}{2}$。

(c.2) 先考慮 (b.3) 的情況：若 $i>j\ 且\ i-j = t$，$A[i][j]$ 在 $D$ 下方的第 $t$ 條對角線，$1 \leq t\leq a-1$。
此 $D$ 下方的第 $t$ 條對角線，元素有 $n-t$ 個且其起點的列註標即為 $t$，再往下共有註標為 $t+1,\ t+2,\ ...\,\ a-1$ 的$a-t-1$條對角線，元素分別為 $n-t-1,\ n-t-2,\ ...\,\ n-a+1$，所有下帶狀元素先存，所以元素有

$\quad (n-t-1)+(n-t-2)+\ ...\ +(n-a+1) \\
=\frac{(n-a+1+(n-t-1))(a-t-1)}{2}
=\frac{(2n-a-t)(a-t-1)}{2}$

在 $D$ 下第 $t$ 條對角線的 $A[i][j]$ 之前的元素，其列註標起點分別位於 $t,\ t+1,\ ...\,\ i-1$，計有 $(i-1)-t+1 = i-t = i-(i-j) = j$ 個(或直接想：不管那條下帶狀的對角線，行 $j$ 之前必有 $j$ 個元素)。於是 $A[i][j]$ 之前的元素總個數為：
$\quad k = j+\frac{(2n-a-t)(a-t-1)}{2}$。

(c.3) 若 $i<j\ 且\ j-i = t$，$A[i][j]$ 在 $D$ 上方的第 $k$ 條對角線，$1 \leq k\leq a-1$。
$D$ 中元素共有 $n$ 個；所有下帶狀的元素個數為：
$\quad (n-1)+(n-2)+\ ...\ +(n-a+1) \\
=\frac{(n-1+(n-a+1))(a-1)}{2}
=\frac{(2n-a)(a-1)}{2}。$
在 $D$ 上第 $1,\ 2, \ ...\,\ t-1$ 條對角線的元素共有：
$\quad (n-1)+(n-2)+\ ...\ +(n-t+1) \\
=\frac{(n-1+(n-t+1))(t-1)}{2}
=\frac{(2n-t)(t-1)}{2}。$
在 $D$ 中第 $k$ 條對角線上 $A[i][j]$ 之前的元素有 $(j-1)-(t-1)=j-t=j-(j-i)=i$ 個 (或直接想：不管那條上帶狀的對角線，列 $i$ 之前必有 $i$ 個元素)。此外，我們還需要再加上主對角線的$n$個元素。由以上可得：
$k=i+\frac{(2n-t)(t-1)}{2}+\frac{(2n-a)(a-1)}{2} + n 。$

總結 (c.1)-(c.3) 可得

$k=\begin{cases}
i+\frac{(2n-a)(a-1)}{2}, \ \text{if}\ (i-j)=0; \\
j+\frac{(2n-a-t)(a-t-1)}{2}, \ \text{if}\  (i-j)=t\ \text{where}\ 1\le t \le a-1; \\
i+\frac{(2n-a)(a-1)}{2}+\frac{(2n-t)(t-1)}{2}+ n, \ \text{if}\ (j-i)=t\ \text{where}\  1\le t \le a-1
\end{cases}$
:::

---
### 13. 一個「一般帶狀矩陣」(generalized band matrix) $D_{n,a,b}$ 是一個 $n×n$ 的矩陣，其中所有可能的非零元素，皆集中在由主對角線以下的 $a−1$ 個對角線，主對角線和主對角線以上的 $b−1$ 個對角線，所形成的帶狀區域上（如圖 2-23）。 <br> &emsp; (a) 在此帶狀 $D_{n,a,b}$ 中有多少個元素？ <br> &emsp; (b) 對於帶狀 $D_{n,a,b}$ 中的元素 $d_{ij}$ 而言，$i$ 與 $j$ 之間的關係為何？ <br> &emsp; (c\) 找出此帶狀 $D_{n,a,b}$ 在一維陣列 $B$ 中的循序表示法。對此表示法，設計一個函數 $address(n, a, b, i, j, B)$，根據傳入的參數 $n, a, b, i, j, B$，來決定在陣列 B 中，矩陣 $D_{n,a,b}$ 中的 $d_{ij}$ 值。 <br>  &emsp;  &emsp;  &emsp;  &emsp;  &emsp;  &emsp;  &emsp; ![](https://hackmd.io/_uploads/H1JeSqpph.png_center =320x)





(a) (by S. J.)
$\sum\limits_{i=0}^{a-1}{(b+i)}+\sum\limits_{i=a}^{n-b-1}{(a+b-1)}+\sum\limits_{i=n-b}^{n-1}{[(a+b-1)-(n-b-i)]}$
$=ab+ \frac{a(a-1)}{2}+(n-a-b)(a+b-1)+ab+\frac{b(b-1)}{2}$
$(=n(a+b-1)-\frac{a(a-1)+b(b-1)}{2})$
![](https://i.imgur.com/O1fXEHK.jpg)
例子：$a=3,\ b=2,\ n=8$
代入上式可得元素個數共 28 個 (見下圖右下)
![](https://i.imgur.com/TxABLQo.png)

亦可用對角線優先的觀點來想：
主對角線 $D$ 共 $n$ 個元素；其下帶狀 $a-1$ 條對角線分別有 $n-1,\ n-2,\ ...\ ,\ n-a+1$ 個元素；其上帶狀共 $b-1$ 條對角線分別有 $n-1,\ n-2,\ ...\ ,\ n-b+1$ 個元素；總共有

$\begin{aligned}
\quad &n+\sum\limits_{k=n-a+1}^{n-1}{k}+\sum\limits_{k=n-b+1}^{n-1}{k} \\ 
&= n+[(n-a+1)+(n-a+2)+...+(n-1)]+[(n-b+1)+(n-b+2)+...+(n-1)] \\
&= n+\frac{(a-1)(2n-a)}{2}+\frac{(b-1)(2n-b)}{2} \\ 
&=\frac {2n+2na-2n-a^2+a+2nb-2n-b^2+b}{2} \\
&=n(a+b-1)-\frac{a(a-1)+b(b-1)}{2}
\end{aligned}$

(b) 若 $d_{ij}$ 
(b.1) 在主對角線 $D$ 上，$i=j$；
(b.2) 在下帶狀區域內，則 $(i-j)\le a-1$； 
(b.3) 在上帶狀區域內，則 $(j-i)\le b-1$；$|i - j| < \text{max}(a, b)$
不在 (b.1)-(b.3) 範圍內的 $i, j$ 其 $d_{ij}$ = 0。

($\text{c}$) 若以最低對角線開始存放元素(如題12)，則 $address(n, a, b, i, j, B)$ 可以下式設計，回傳位址：$\&B[k]\ (=B+k (= \alpha+k\times l))$，其中
$k=\begin{cases}
i+\frac{(a-1)(2n-a)}{2}, \ \text{if} \quad i-j=0 \\
j-a+\frac{(a-1-s)(2n-a-s)}{2-1}, \ \text{if} \quad i-j =s, \text{and} \quad s<a \\
i-a+n+\frac{(a-1)(2n-a)}{2}+\frac{(s-1)(2n-s)}{2-1}, \ \text{if} \quad j-i =s,\text{and} \quad s<b
\end{cases}$

若要以列為優先，則請依上述邏輯自行推導。讀者可由題12和13得知：用「對角線優先」(diagonal-major) 可以是二維陣列儲存在一維記憶體空間中，有效率地的對應關係。
:::

---
### 14. 請撰寫程式實作經驗法則 2-7 解決騎士巡迴的問題。
//:::spoiler 請參照經驗法則 2-7
![image](https://hackmd.io/_uploads/SyULTfHtp.png)
![image](https://hackmd.io/_uploads/S1jYpGHt6.png)

程式實作如下：
```cpp=
# define SIZE 20
# define DIR 8
# include <stdio.h>
# include <iostream>
using namespace std;
int K[SIZE][SIZE];// K[n][n] is a global array
int move_x[SIZE], move_y[SIZE];
void init()
{   int i, j;
    move_x[0] = -2;  move_y[0] = 1;
    move_x[1] = -1;  move_y[1] = 2;
    move_x[2] =  1;  move_y[2] = 2;
    move_x[3] =  2;  move_y[3] = 1;
    move_x[4] =  2;  move_y[4] = -1;
    move_x[5] =  1;  move_y[5] = -2;
    move_x[6] = -1;  move_y[6] = -2;
    move_x[7] = -2;  move_y[7] = -1;
}
void kinghtTour(int n, int x, int y)
{   int next_x[DIR], next_y[DIR], next_moves[DIR];
    int i, j, k, step, nSquare, tx, ty, sx, sy, cnt, min;
    for (i = 0; i < n; i++) //*(Kp+i) = 0;
        for (j = 0; j < n; j++)
   	        K[i][j] = 0;
    K[x][y] = 1;
    for (nSquare = n * n, sx = x, sy = y, step = 2; step <= nSquare; step++)
    {   for (cnt = 0, k = 0; k < DIR; k++)
        {   tx = sx + move_x[k];	ty = sy + move_y[k];
            if ((tx >= 0 && tx < n) && (ty >= 0 && ty < n) && !K[tx][ty])
            {   next_x[cnt] = tx; next_y[cnt++] = ty;
            }
        }
        if (cnt == 0) break;
        for (i = 0; i < cnt; i++)
        {   sx = next_x[i];	sy = next_y[i];	next_moves[i] = 0;
            for (k = 0; k < DIR; k++)
            {   tx = sx + move_x[k];	ty = sy + move_y[k];
                if ((tx >= 0 && tx < n) && (ty >= 0 && ty < n) && !K[tx][ty])
                    next_moves[i]++;
            }
        }
        for (min = 0, i = 1; i < cnt; i++)
            if (next_moves[i] < next_moves[min])
                min = i;
        sx = next_x[min];    sy = next_y[min];
        K[sx][sy] = step;
    }
    if (step > nSquare)
    {   for (i = 0; i < n; i++)
        {   for (j = 0; j < n; j++)
                printf("%7d", K[i][j]);
            cout << endl;
        }
    }
    else cout << "No knight's tour from (" << x << ", " << y << ")!" << endl;
}
 
int main()
{   int n, x, y;
    init();
    while (cout << "n = ", (cin >> n), n != 0)
    {   cout << "x y =";
        cin >> x >> y;
        kinghtTour(n, x, y);
    }
}
```
/* -----
Please input board size n, and starting position $(x, y).
n = 6
x y = 1 1
| 25| 32| 11|  2| 19| 34|
|-|-|-|-|-|-|
| 10|  1| 26| 33| 12|  3|
| 31| 24|  9| 18| 35| 20|
|  8| 17| 36| 27|  4| 13|
| 23| 30| 15|  6| 21| 28|
| 16|  7| 22| 29| 14|  5|

n = 7
x y = 3 4
No knight's tour from (3, 4)!
n = 8
x y = 3 4
|52 | 21| 64| 47| 50| 23| 40|  3|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|63 | 46| 51| 22| 55|  2| 49| 24|
|20 | 53| 62| 59| 48| 41|  4| 39|
|61 | 58| 45| 54|  1| 56| 25| 30|
|44 | 19| 60| 57| 42| 29| 38|  5|
|13 | 16| 43| 34| 37|  8| 31| 26|
|18 | 35| 14| 11| 28| 33|  6|  9|
|15 | 12| 17| 36|  7| 10| 27| 32|

n = 10
x y = 2 6
|21 | 42| 59| 46| 23| 44| 61|  2| 25| 28|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|58 | 47| 22| 43| 60| 73| 24| 27| 62|  3|
|41 | 20| 75| 78| 45| 70|  1| 72| 29| 26|
|76 | 57| 48| 69| 74| 79| 94| 67|  4| 63|
|19 | 40| 77| 92| 99| 68| 71| 64| 83| 30|
|56 | 91| 38| 49| 80| 93| 88| 95| 66|  5|
|39 | 18| 55|100| 89| 98| 65| 82| 31| 84|
|54 | 15| 90| 37| 50| 81| 96| 87|  6|  9|
|17 | 36| 13| 52| 97| 34| 11|  8| 85| 32|
|14 | 53| 16| 35| 12| 51| 86| 33| 10|  7|

---- */
![](https://i.imgur.com/ejDZxr0.png)
:::

---
---
## 第三章 堆疊和佇列 習題解答
---
### 1. 圖 3-31 描繪了一個鐵路調度軌道，每一節車廂都編號 $1, 2, 3$, ..., $n$，並按順序從左到右停放在軌道上，車廂可以從任何一條橫向軌道一次一台的移進垂直軌道，而移進垂直軌道的車廂也可以一次一台的移到任何一條橫向軌道，則垂直軌道就像一個堆疊，新移進車廂都在最上層，能移出的車廂也是最上層的那一個。假設 $n$ = $3$ 時，我們可以先移車廂 $1$ 進垂直軌道，再來是車廂 $2$，最後是車廂 $3$，然後我們就得到一個新的順序 $3, 2, 1$；當 $n$ = $3$ 和 $4$ 時，可以得到哪幾種有可能的車廂排列？有哪幾種排列是不可能的？ <br>  &emsp;  &emsp;  &emsp;  &emsp;  &emsp;  &emsp; ![image](https://hackmd.io/_uploads/S1BOLRmtp.png)


:::spoiler  數量可藉由離散數學中介紹的 Catalan 數列求一般解

當 $n = 3$ 時
&ensp; 可能的排列有 $5$ 種：$123, 132, 213, 231, 321$
&ensp; 不可能的排列有 $1$ 種：$312$

當 $n = 4$ 時
&ensp; 可能的排列有 $14$ 種 ： $1234, 1243, 1324, 1342, 1432, 2134, 2143, 2314, 2341, 2431, 3421, 3241, 3214, 4321$
&ensp; 不可能的排列有 $10$ 種：$1423, 2413, 3124, 3142, 3412, 4123, 4132, 4213, 4231, 4312$

註：Catalan Number $C_n = {2n\choose {n}}-{2n\choose {n+1}}$, or $C_n =\frac {1}{n+1}{2n \choose {n}}$

:::

---
### 2. 對一堆疊依序加入 (push) $1, 2, 3, 4, 5$，其間可輸出 (pop) 元素，請列出所有可能的輸出？亦請列出所有不可能的輸出。
:::spoiler
有可能的輸出：$42$ 種（請自行列舉）
※公式： 
$C_n = {2n\choose {n}}-{2n\choose {n+1}}$, $C_n =\frac {1}{n+1}{2n \choose {n}}$ 或
$C_n = \frac{2n!}{(n+1)!n!}$   
此為第 $n$ 項 Catalan number (https://en.wikipedia.org/wiki/Catalan_number 或可見散離數學書中的相關証明)
不可能的輸出：$78$ 種（請自行列舉）
:::

---
### 3. 一個「雙端佇列」（double-ended queue，也稱 deque）是一個線性串列，它可以在佇列任一端加入或刪除元素。設計一個表示法，使用一維陣列來表示雙端佇列，再寫出從任一端加入或刪除雙向佇列的演算法。

:::spoiler

```cpp=
# include <stdio.h>
# include <iostream>
#define MAXSIZE 10
using namespace std;
int queue[MAXSIZE];
int head = -1, tail = -1;
void Insert(int v)
{   if (tail == MAXSIZE) cout << "overflow" << endl;
    else
    {   if (head == -1 && tail == -1)
        {   head = 0;
            tail = 0;
        }
        else tail++;
        queue[tail] = v;
    }
}
void f_Insert(int v)
{   if (tail == MAXSIZE) cout << "overflow" << endl;
    else
    {   if (head == -1 && tail == -1)
        {   head = 0;
            tail = 0;
        }
        else tail++;
        for (int i = tail; i > 0; i--)
        {   queue[i] = queue[i-1];
        }
    	queue[head] = v;
	}
}
int Pop()
{   if(head == -1 || head > tail)
	{   cout << "No element" << endl;
        return -1;
	}
	else
	{   int v = queue[head];
    	head++;
    	if (head > tail)
        {   head = -1;
            tail = -1;
        }
    	return v;
	}
}
int b_Pop()
{   if (head == -1 || head > tail)
    {   cout << "No element" << endl;
        return -1;
    }
    else
    {   int v = queue[tail];
    	tail--;
    	if (head > tail)
        {   head = -1;
            tail = -1;
        }
    	return v;
    }
}
void Display()
{   for(int i = head; i <= tail; i++)
    {   cout << queue[i] << " ";
    }
    cout << endl;
}
int main()
{   string s;
    int v;
    while (cout << "前加入(j)/後加入(i)/前刪除(p)/後刪除(q) :", cin >> s)
    {   if(s == "p") Pop();
        if(s == "q") b_Pop();
    	if(s == "i")
    	{   cout << "n :";
            cin >> v;
            Insert(v);
    	}
    	if (s == "j")
    	{   cout << "n :";
            cin >> v;
            f_Insert(v);
    	}
    	if (head != -1) Display();
    }
}
```
:::

---
### 4. 用陣列實作一個線性串列，使用兩個變數 front 和 rear，使其變成「環狀」。 <br> &emsp; (a) 使用 front, rear 和 $n$，設計一個公式來求出串列中元素的個數。 <br> &emsp; (b) 寫一個演算法來刪除串列中第 $k$ 個元素。 <br> &emsp; (c\) 寫一個演算法來立即插入元素 $y$ 在第 $k$ 個元素後面。 <br> 你設計的演算法 (b) 和 (c\)，其時間複雜度為多少?


:::spoiler
(a) 令 $k$ 表示串列中元素的個數，
$\quad k=\begin{cases} rear - front \qquad \qquad \quad \text{, if} \ \ rear < front \\ (n - front)+rear \qquad \ \ \text{, if} \ \ n=0 \\0 \qquad \qquad \qquad \qquad \qquad \ \text{, otherwise }\end{cases}$
(b)
```cpp=
Delete(k) 
{   if (front == rear) ListEmpty(); 
    else 
    {   p = ListSize(list) //求串列元素個數
        for (int i = k; i < p; i++)
            list[(front + i) % n] = list[(front + i + 1) % n]; 
        rear = (rear + n - 1) % n 
    } 
} 
```
$O(p-k)$
(c\)
```cpp=
Add(y, k) 
{   if (front == rear + 1) 
    ListFull();
    else 
    {   p = ListSize(list) //求串列元素個數
        for (int i = p; i >= k; i--) 
            list[(front + i + 1) % n] = list[(front + i) % n]; 
        list[(front + k) % n] = y; 
        rear = (rear + 1) % n; 
    } 
} 
```
$O(p-k)$

:::

---
### 5. 一個 $m×p$ 的迷宮，全部有可能的路徑中，最長的長度為多少？

:::spoiler

路徑最長的長度(即為最差的情況)：$\text{max}( \frac{m}{2}×(p+1),\ + \frac{p}{2}×(m+1))$

:::

---
### 6. 判斷以下的數學形式為何種形式（即中序、前序或後序），然後再轉換成另外兩種： <br> &emsp; (a) 1+2-3×4/5×6/7-8/9 <br> &emsp; (b) +×-×123×45/×678

:::spoiler

(a)
前序：− − + 12 / × / × 34567 / 89
後序：12 + 34 × 5 / 6 × 7 / − 89 /−
(b)
中序：[ ( 1 × 2 ) − 3 ] × 4 × 5 + 6 × 7 / 8
後序：12 × 3 − 45 × × 67 × 8 / +

:::

---
### 7. 寫出下列式子的後置式： <br> &emsp; (a) A×B×C <br> &emsp; (b) -A+B-C+D <br> &emsp; (c\) A×-B+C <br> &emsp; (d) (A+B)×D+E/(F+A×D)+C <br> &emsp; (e) A&&B\||C\||!(E>F) <br> &emsp; (f) !(A&&!((B<C)\||(C>D)))\||(C<E) <br> &emsp; (g) A and B or C or not (E>F) <br> &emsp; (h) (A+B)\*C^(D+E\*F-G\*(H+J))

:::spoiler

(a) AB × C ×
(b) A − B + C − D +
(c\) AB − × C +
(d) AB + D × EFAD × + /+ C +
(e) AB && C \|| EF > !\||
(f) ABC < CD >\|| ! && ! CE < ||
(g) AB and C or EF > not or
(h) AB + CDEF * + GHJ + * - ^ *

:::

---
### 8. 使用表 3-1 和 3-2 各運算子和其優先次序，再加上 "("、")" 和 "#"，來回答下面的問題： <br> &emsp; (a) 在演算法 3-3 中，假如一個運算式 e 內含有 $n$ 個運算子和標點符號，則堆疊中最多會放進多少個元素？ <br> &emsp; (b) 假如運算式e有n 個運算子，且括號最深有6層（如：(..(..)..) + (..(..(..)..)..) 此式括號最深就是 3 層），則 (a) 的答案會是多少？
:::spoiler
(a)
&ensp; 當所有運算皆以由左到右的順序計算時 (如：運算子皆為 + ) 且没有 “(“, “)”時，所有運算子皆得放入 stack 中，於是 stack 最多會放入 $n$ 個元素。
(b)
&ensp; 所有右括號皆不會被 push 至 stack 中，於是 stack 最多會放入 $n$-6  個元素。
8-1 請寫出輸入中置式/中序式，輸出後置式/後序式的 (a) 演算法、(b) 程式。
(a)
```cpp=
Input: Infix e
Output: Postfix of e
n = parsing(e, token);
push(“#”); 
for (i = 0; i < n; i++)
{   s = token[i];
    if (s is an Operand) postfix += s;   // output(s);
    else if (s == ”)”) //將堆疊中第一個 ( 之前的運算子皆pop出並印出
        while ((x=pop()) != “(”) output(x);
    else
    {   while ( p(s) <= q(Stack[top]) )
        {   x = pop();
            postfix += s ;  // output(x);
        }
    }
    push(s);
}
while ((x = pop()) != “#”) postfix += s;  // output(x);
return postfix;
```
(b)
```cpp=
# include <stdio.h>
# include <string.h>
# define SIZE 256
char infix[SIZE], prefix[SIZE];
char Stack[SIZE];
int top = -1;
void push(char x)
{   if (top < SIZE) Stack[++top] = x;
    else printf("Stack Full!");
}
char pop()
{   if (top > -1) return Stack[top--];
    else return '0';
}
int p(char op)
{   if ((op == '+') || (op == '-') ) return 3 ;
    if ((op == '*') || (op == '/') ) return 4 ;
    if ((op == '^') || (op == '&') || (op == '|') ) return 5 ;
    if ((op == '(') ) return 8 ;
    if ((op == '@') ) return 9 ;
    if (op == '#') return 0 ;
}
int q(char op)
{   if ((op == '+') || (op == '-') ) return 3 ;
    if ((op == '*') || (op == '/') ) return 4 ;
    if ((op == '^') || (op == '&') || (op == '|') ) return 5 ;
    if ((op == '(')) return 1 ;
    if ((op == '@') ) return 9 ;
    if (op == '#') return 0 ;
}
int IsOperand(char s)
{   if ((s != '+') && (s != '-') && (s != '*') && (s != '/') && (s != '(') && (s != ')')  && (s != '&') && (s != '|') && (s != '^') && (s != '#')) return true;
    return false;
}
void InfixToPostfix(char infix[])
{   int len = strlen(infix), i;
    char s, x;
    push('#');
    for (i = 0; i < len; i++)
    {   s = infix[i];
        if (IsOperand(s)) strncat(prefix, &s, 1);
        else
        {   if (s == ')') while ((x=pop()) != '(') strncat(prefix, &x, 1); //將堆疊中第一個（之前的運算子皆pop出並印出之） 
	    else
	    {   for ( ; p(s) <= q(Stack[top]); x = pop(), strncat(prefix, &x, 1));
                push(s);
	    }
	    printf("Opt: infix[%d]=%c, prefix=%s, len=%d\n", i, s, prefix, strlen(prefix));
        }
    }
    while ((x = pop()) != '#') strncat(prefix, &x, 1);
}
int main()
{   int i;
    while (printf("input an infix (or a string with prefix 0* to stop): "), scanf("%s", infix), infix[0] != '0')
    {   // cout << "x = " << x;
        printf("==>  infix = %s\n", infix);
        strcpy(prefix, "");
        InfixToPostfix(infix);
        printf("==> prefix = %s, length : %d\n", prefix, strlen(prefix));
    }
}
```
/* ---
input an infix (or a string with prefix 0* to stop): ((A+B*C)/(D+E)+F)*(G-H^I/J+K)+L*M
==>  infix = ((A+B*C)/(D+E)+F)*(G-H^I/J+K)+L*M
Opt: infix[0]=(, prefix=, len=0
Opt: infix[1]=(, prefix=, len=0
Opt: infix[3]=+, prefix=A, len=1
Opt: infix[5]=*, prefix=AB, len=2
Opt: infix[7]=), prefix=ABC*+, len=5
Opt: infix[8]=/, prefix=ABC*+, len=5
Opt: infix[9]=(, prefix=ABC*+, len=5
Opt: infix[11]=+, prefix=ABC*+D, len=6
Opt: infix[13]=), prefix=ABC*+DE+, len=8
Opt: infix[14]=+, prefix=ABC*+DE+/, len=9
Opt: infix[16]=), prefix=ABC*+DE+/F+, len=11
Opt: infix[17]=*, prefix=ABC*+DE+/F+, len=11
Opt: infix[18]=(, prefix=ABC*+DE+/F+, len=11
Opt: infix[20]=-, prefix=ABC*+DE+/F+G, len=12
Opt: infix[22]=^, prefix=ABC*+DE+/F+GH, len=13
Opt: infix[24]=/, prefix=ABC*+DE+/F+GHI^, len=15
Opt: infix[26]=+, prefix=ABC*+DE+/F+GHI^J/-, len=18
Opt: infix[28]=), prefix=ABC*+DE+/F+GHI^J/-K+, len=20
Opt: infix[29]=+, prefix=ABC*+DE+/F+GHI^J/-K+*, len=21
Opt: infix[31]=*, prefix=ABC*+DE+/F+GHI^J/-K+*L, len=22
==> prefix = ABC*+DE+/F+GHI^J/-K+*LM*+, length : 25
input an infix (or a string with prefix 0* to stop): A+B*C^(D*E-F/G+(H-I))/(J+K)+L*M
==>  infix = A+B*C^(D*E-F/G+(H-I))/(J+K)+L*M
Opt: infix[1]=+, prefix=A, len=1
Opt: infix[3]=*, prefix=AB, len=2
Opt: infix[5]=^, prefix=ABC, len=3
Opt: infix[6]=(, prefix=ABC, len=3
Opt: infix[8]=*, prefix=ABCD, len=4
Opt: infix[10]=-, prefix=ABCDE*, len=6
Opt: infix[12]=/, prefix=ABCDE*F, len=7
Opt: infix[14]=+, prefix=ABCDE*FG/-, len=10
Opt: infix[15]=(, prefix=ABCDE*FG/-, len=10
Opt: infix[17]=-, prefix=ABCDE*FG/-H, len=11
Opt: infix[19]=), prefix=ABCDE*FG/-HI-, len=13
Opt: infix[20]=), prefix=ABCDE*FG/-HI-+, len=14
Opt: infix[21]=/, prefix=ABCDE*FG/-HI-+^*, len=16
Opt: infix[22]=(, prefix=ABCDE*FG/-HI-+^*, len=16
Opt: infix[24]=+, prefix=ABCDE*FG/-HI-+^*J, len=17
Opt: infix[26]=), prefix=ABCDE*FG/-HI-+^*JK+, len=19
Opt: infix[27]=+, prefix=ABCDE*FG/-HI-+^*JK+/+, len=21
Opt: infix[29]=*, prefix=ABCDE*FG/-HI-+^*JK+/+L, len=22
==> prefix = ABCDE*FG/-HI-+^*JK+/+LM*+, length : 25
input an infix (or a string with prefix 0* to stop): (((A+B)/(C-D*E)-F/G)-H)*I^J
==>  infix = (((A+B)/(C-D*E)-F/G)-H)*I^J
Opt: infix[0]=(, prefix=, len=0
Opt: infix[1]=(, prefix=, len=0
Opt: infix[2]=(, prefix=, len=0
Opt: infix[4]=+, prefix=A, len=1
Opt: infix[6]=), prefix=AB+, len=3
Opt: infix[7]=/, prefix=AB+, len=3
Opt: infix[8]=(, prefix=AB+, len=3
Opt: infix[10]=-, prefix=AB+C, len=4
Opt: infix[12]=*, prefix=AB+CD, len=5
Opt: infix[14]=), prefix=AB+CDE*-, len=8
Opt: infix[15]=-, prefix=AB+CDE*-/, len=9
Opt: infix[17]=/, prefix=AB+CDE*-/F, len=10
Opt: infix[19]=), prefix=AB+CDE*-/FG/-, len=13
Opt: infix[20]=-, prefix=AB+CDE*-/FG/-, len=13
Opt: infix[22]=), prefix=AB+CDE*-/FG/-H-, len=15
Opt: infix[23]=*, prefix=AB+CDE*-/FG/-H-, len=15
Opt: infix[25]=^, prefix=AB+CDE*-/FG/-H-I, len=16
==> prefix = AB+CDE*-/FG/-H-IJ^*, length : 19
input an infix (or a string with prefix 0* to stop): 0

Process returned 0 (0x0)   execution time : 256.204 s
Press any key to continue.
--- */
:::

---
### 9. 另外一種容易計算且不必加括號式子的表示法就是前序表示式，這種表示法就是將運算子放在運算元的前面，請見範例 3-13： <br> &emsp; (a) 將習題 6 表示成對應的前序表示。 <br> &emsp; (b) 寫一個演算法來計算前序表示法 e。 <br> &emsp; (c\) 寫一個演算法把中序式 e 轉成相等的前序式，假設每個 e 都以符號 "#"做開頭，且其前序式的也要以 "#" 做開頭。 <br> 你的演算法 (b) 和 (c\) 的複雜度為多少？每個演算法需要多少空間？

:::spoiler

(a) − − +12 /× /× 34567 / 89

(b)
```cpp=
# include <iostream>
# include <string>
# include <algorithm>
using namespace std;
int top = 0;
int opndstk[100000];
int opndstk_pop()
{   if (top == -1) cout << "empty stack." << endl;
    else return opndstk[--top];
}
int calculate(int o1, int o2, char opr)
{   if (opr == '+') return o1 + o2;
    if (opr == '-') return o1 - o2;
    if (opr == '*') return o1 * o2;
    else return o1 / o2;
}
int main()
{   int i =- 1;
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    int ans = 0;
    int opnd1, opnd2;
    while (++i < s.size())
    {   if (isdigit(s[i])) opndstk[top++] = s[i] - '0';
        else
        {   opnd1 = opndstk_pop();
            opnd2 = opndstk_pop();
            opndstk[top++] = calculate(opnd1, opnd2, s[i]);
            cout << opnd1 << " " << s[i] << " " << opnd2 << " = " << calculate(opnd1, opnd2, s[i]) << endl;
        }
    }
    cout << "Ans = " << opndstk[top] << endl;
}
```
(c\)
```cpp=
輸入：中序運算式e
輸出：對應輸入之前序運算法
n = parsing(e, token);
push(“#”);
for (i = 0; i < n; i++)
{   s = token(i);
    if (s是一運算元) push_opn(s);
    else if (s == ”)”) //將堆疊中第一個(之前的運算子皆pop並印出
    {   while((x = pop()) != ”(”)
            push_opn(get_prefix(x));
    }
    else
    {   while ( p(s) <= q(Stack[top]) )
        {   x = pop();
            push_opn(get_prefix(x));
        }
    push(s);
    }
}
while (Stack[top] != ”#”)
{   x = pop();
    push_opn(get_prefix(x)
}
x = pop();  // pop out “#”
return pop_opn();
//—------------------
String get_prefix(x)
{   String a = pop_opn();
    return x + pop_opn() + a;
}
```
:::

---
### 10. 寫一個演算法將前序式轉成後序式，詳細描述任何有關輸入式子的假設。你的演算法需要多少時間和空間？
:::spoiler
```cpp=
Input: Prefix e
Output: Postfix of e
n = parsing(e, token);
for (i = 0; i < n; i++)
    {   s = token[i];
        if (s is an Operand)
        {   while (stack[top] is an Operand) //這是關鍵
            {   y = pop(); // pop 出前一個 operand
                x = pop(); // pop 出對應的 operator
                s = y + s + x; // operator x 所對應的 postfix
            } // 若 stack[top] 又是 operand, s 須再與之結合
        push(s); // push 所得的 operand (in postfix form)
        }
        else push(s); // push operator s
    }
return pop(); // final result 
```
:::

---
### 11. 有兩個堆疊用這節討論的方法儲存在陣列 M[$m$]，寫一個演算法 Add 和Delete 在堆疊 i 中，0 ≤ $i$ ≤ 1，做加入和刪除的動作，你的演算法必須保證只要兩個堆疊的元素總和小於 $m$ 就能加入元素，而且執行時間必須在 $O(1)$ 內。

:::spoiler

對 Stack0 做 
&emsp; push : Stack0[++top] = element;
&emsp; pop  : return Stack[top--];

|       |        Stack0        | Stack1 |
|:----- |:-------------------- |:------ |
| Init. | $top0 = -1$            | $top1 = m$ |
| push  | Stack0[$++top$] = $data$ | Stack1[$--top$] = $data$ |
| pop   | return Stack0[$--top$] | Stack1[$top++$] |
| Full  | $if (top1==top0)$      | $if (top0 == top1)$ |
| Empty | $if (top == -1)$       | $if (top == m)$ |

![](https://i.imgur.com/5VYZ6Pw.png)

:::

---
### 12. 設計一個資料表示法，將 $n$ 個佇列循序對應到陣列 M[$m$]；在 M 中每個佇列就像是環形佇列，為此表示法寫出函式 Add、Delete 和 QueueFull。

:::spoiler

```cpp=
# define SIZE 5
# include <iostream>
using namespace std;
int Cqueue[SIZE];
int front = -1,rear = -1;
bool QueueFull() 
{   if (front == 0 && rear == SIZE - 1) return true;
    if (front == rear + 1) return true;
    return false;
}
bool isEmpty() 
{   if (front == -1)return true;
    else return false;
}
void Add(int element) 
{   //增加元素
    if (QueueFull())cout << "Queue is full" << endl;
    else
    {   if (front == -1) front = 0;
        rear = (rear + 1) % SIZE;
        Cqueue[rear] = element;
        cout << "Inserted :" << element << endl;
    }
}
int Delete() 
{   //刪除元素
    int element;
    if (isEmpty())
    {   cout << "Queue is empty" << endl;
        return -1;
    }
    else
    {   element = Cqueue[front];
        if (front == rear)
        {   front = -1;
            rear = -1;
        }
        else front = (front + 1) % SIZE;
        return (element);
    }
}
void display() 
{   int i;
    if (isEmpty()) cout << endl << "Empty Queue" << endl;
    else
    {   cout << "Front -> " << front;
    	cout << endl << "Items -> ";
    	for (i = front; i != rear; i = (i + 1) % SIZE)cout << Cqueue[i];
    	cout << Cqueue[i];
    	cout << endl << "Rear -> " << rear <<endl;
    }
}
int main(void)
{   int select;
    int loop = 1;
    int temp;
    while ( loop )
    {   printf("[1]Add [2]Delete ==>\n");
        scanf("%d",&select);// 讀入選項
        switch ( select )
        {   case 1: printf("input value(%d,%d) ==> ",front,rear);
                    scanf("%d",&temp);
                    Add(temp);
                    display();
                    break;
            case 2: if (isEmpty());
                    else
                    {   temp = Delete();
                        printf("Pop: %d\n",temp);
                    }
                    break;
            /* 跳出迴圈 */
            case 3: loop = 0;
                    break;
        }
    }
    system("PAUSE");
    return 0;
}
```

![](https://i.imgur.com/grG8DkB.png)

:::

---
### 13. 設計一個資料結構，將 $n$ 個資料物件連續對應到陣列 M[$m$]，其中 $n_1$ 個物件為堆疊，剩下的 $n_2$ = $n−n_1$ 為佇列。寫出加入和刪除的演算法，只要陣列中還有空間沒使用到，此演算法就要提供空間給第 $i$ 個資料物件。注意：一個有 $r$ 個空間的環形佇列只能儲存 $r−1$ 個元素。

:::spoiler

```cpp=
#define SIZE 6
#include <iostream>
using namespace std;
int Cqueue[SIZE];
int front = -1,rear = -1;
bool QueueFull() 
{   if (front == 0 && rear == SIZE - 1)return true;
    if (front == rear + 1)return true;
    return false;
}
bool isEmpty() 
{   if (front == -1)return true;
    else return false;
}
void Add(int element) 
{   //增加元素
    if (QueueFull())cout << "Queue is full" << endl;
    else
    {   if (front == -1) front = 0;
        rear = (rear + 1) % SIZE;
        Cqueue[rear] = element;
        cout << "Inserted :" << element << endl;
    }
}
int Delete() 
{   //刪除元素
    int element;
    if (isEmpty())
    {   cout << "Queue is empty" << endl;
        return -1;
    }
    else
    {   element = Cqueue[front];
        if (front == rear)
        {   front = -1;
            rear = -1;
        }
        else front = (front + 1) % SIZE;
        return (element);
    }
}
int Spop()
{   int element;
    if (isEmpty())
    {   cout << "Queue is empty" << endl;
        return -1;
    }
    else
    {   element = Cqueue[rear];
        if (rear == front)
        {   front = -1;
            rear = -1;
    	}
        else rear = (rear - 1) % SIZE;
        return (element);
    }
}
void display() 
{   int i;
    if (isEmpty()) cout << endl << "Empty Queue" << endl;
    else
    {   cout << "Front -> " << front;
    	cout << endl << "Items -> ";
    	for (i = front; i != rear; i = (i + 1) % SIZE)cout << Cqueue[i];
    	cout << Cqueue[i];
    	cout << endl << "Rear -> " << rear <<endl;
    }
}
int main(void)
{   int select ,temp;
    int loop = 1;
    while ( loop )//主迴路開始
    {   printf("[1]Add [2]Queue Pop [3]Stack Pop ==>\n");
        cin >> select;//讀入選項
    	switch ( select )
    	{   case 1: printf("input value(%d,%d) ==> ",front,rear);
                    cin >> temp;
                    Add(temp);
                    display();
                    break;
            case 2: if (isEmpty()) cout << "No Data" << endl ;
                    else
                    {   temp = Delete();
                    	cout << "Queue Pop :" << temp << endl;
                    }
                    cout << "front -> " << front << endl;
                    cout << "Rear -> " << rear << endl;
                    break;
            case 3: if (isEmpty()) cout << "No Data" << endl ;
                    else
                    {   temp = Spop();
                    	cout << "Stack Pop :" << temp << endl;
                    }
                    cout << "front -> " << front << endl;
                    cout << "Rear -> " << rear << endl;
                    break;
            case 4: loop = 0;
                    break;
    	}
   }
   system("PAUSE");
   return 0;
}
```
![](https://i.imgur.com/geczlSX.png)

:::

---
### 14. 下列是 Hanoi 塔 (Hanoi tower) 的遞迴演算法： 
```cpp=
演算法 3-5 Hanoi 塔:
輸入：整數 N：大小不一（1~N 由小至大排列）的盤子數，A:起點、B： 終點、C：輔助點
輸出：將 N 個盤子從 A 藉助 C，搬到 B；在 A、B 和 C 任一點上，大盤子皆得在小盤子之下
Tower(N, A, B, C) 
{   if (N > 0)
    {   Tower(N - 1, A, C, B);
        搬第 N 個盤子，從 A 搬到 B;
        Tower(N - 1, C, B, A);
    }
} 
```
&emsp;請將上述遞迴演算法改用非遞迴方式。
:::spoiler
```cpp=
for (i = 1;i <= n;++i)
{   A[i][0] = 'A'; 
    for (j = 1;j <= (int)pow(2, n - 1);++j)
    {   switch (j % 3)
        {   case 1: if (n % 2 == 0) 
                    {   if (i % 2 == 0) A[i][j] = 'C'; 
                        else A[i][j] = 'B'; 
                    } 
                    else 
                    {   if (i % 2 == 0) A[i][j] = 'B'; 
                        else A[i][j] = 'C'; 
                    } 
                    break; 
            case 2: if (n % 2 == 0) 
                    {   if (i % 2 == 0) A[i][j] = 'B'; 
                        else A[i][j] = 'C'; 
                    }
                    else 
                    {   if (i % 2 == 0) A[i][j] = 'C'; 
                        else A[i][j] = 'B'; 
                    } 
                    break; 
            case 0: A[i][j] = 'A'; break; 
        }
    }
}
```
```cpp=
struct package
{   int size, id;
    String source, temp, dest;
};
struct package Stack[30];
int top = -1;

void push(struct package p)
{	Stack[++top] = p;
}
struct package pop()
{	return Stack[top--];
}
struct package pack(int size, int id, String  source, String temp, String dest)
{	struct package p;
	p.size = size;
	p.id   = id;
	p.source = source;
	p.temp = temp;
	p.dest = dest;
	return p;
}
//---------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{	int n = Edit1->Text.ToInt();
	int count = 0;
	struct package p, q;
	q = pack(n, n, "A", "B", "C");
	push(q);
	Memo1->Lines->Add("---- NUmber of Disks: " + IntToStr(n) + " ----");
	while (top != -1)
	{  p = pop();
	   if (p.size == 1)
		Memo1->Lines->Add("Move disk  " + ntToStr(p.id) + "  from  " + p.source + "  to  " + p.dest + "  [" + (++count) + "]");
	   else  // 原是三次遞迴呼叫；改為三次pack必要參數後push，但注意順序
	   {  q = pack(p.size - 1, p.size - 1, p.temp, p.source, p.dest);
		 push(q);
		 q = pack(1, p.size, p.source, p.temp, p.dest);
		 push(q);
		 q = pack(p.size - 1, p.size - 1, p.source, p.dest, p.temp);
		 push(q);
	   }
	}
}
```
/* ---
---- NUmber of Disks: 3 ----
Move disk  1  from  A  to  C  [1]
Move disk  2  from  A  to  B  [2]
Move disk  1  from  C  to  B  [3]
Move disk  3  from  A  to  C  [4]
Move disk  1  from  B  to  A  [5]
Move disk  2  from  B  to  C  [6]
Move disk  1  from  A  to  C  [7]
---- NUmber of Disks: 4 ----
Move disk  1  from  A  to  B  [1]
Move disk  2  from  A  to  C  [2]
Move disk  1  from  B  to  C  [3]
Move disk  3  from  A  to  B  [4]
Move disk  1  from  C  to  A  [5]
Move disk  2  from  C  to  B  [6]
Move disk  1  from  A  to  B  [7]
Move disk  4  from  A  to  C  [8]
Move disk  1  from  B  to  C  [9]
Move disk  2  from  B  to  A  [10]
Move disk  1  from  C  to  A  [11]
Move disk  3  from  B  to  C  [12]
Move disk  1  from  A  to  B  [13]
Move disk  2  from  A  to  C  [14]
Move disk  1  from  B  to  C  [15]
---- NUmber of Disks: 5 ----
Move disk  1  from  A  to  C  [1]
Move disk  2  from  A  to  B  [2]
Move disk  1  from  C  to  B  [3]
Move disk  3  from  A  to  C  [4]
Move disk  1  from  B  to  A  [5]
Move disk  2  from  B  to  C  [6]
Move disk  1  from  A  to  C  [7]
Move disk  4  from  A  to  B  [8]
Move disk  1  from  C  to  B  [9]
Move disk  2  from  C  to  A  [10]
Move disk  1  from  B  to  A  [11]
Move disk  3  from  C  to  B  [12]
Move disk  1  from  A  to  C  [13]
Move disk  2  from  A  to  B  [14]
Move disk  1  from  C  to  B  [15]
Move disk  5  from  A  to  C  [16]
Move disk  1  from  B  to  A  [17]
Move disk  2  from  B  to  C  [18]
Move disk  1  from  A  to  C  [19]
Move disk  3  from  B  to  A  [20]
Move disk  1  from  C  to  B  [21]
Move disk  2  from  C  to  A  [22]
Move disk  1  from  B  to  A  [23]
Move disk  4  from  B  to  C  [24]
Move disk  1  from  A  to  C  [25]
Move disk  2  from  A  to  B  [26]
Move disk  1  from  C  to  B  [27]
Move disk  3  from  A  to  C  [28]
Move disk  1  from  B  to  A  [29]
Move disk  2  from  B  to  C  [30]
Move disk  1  from  A  to  C  [31]
--- */
:::

---
---
## 第四章 鏈結串列
---
### 1. 設計一個演算法來計算一個由 first 指標指向開頭節點的單向鏈結串列所含的節點總數目，串列中最後一個節點的 link 欄為 NULL。計算此演算法的時間複雜度。

:::spoiler

```cpp=
while (first != null)
{   first = first->next;
    counter++;
}
```
```cpp=
int CountNodes(struct node * first)
{   int cnt;
    for (cnt = 0, p = first; p; cnt++, p = p->next);
    return cnt;
}
```
時間複雜度：$O(n)$，其中 $n$ 為串列節點個數。

:::

---
### 2. 用遞迴的概念，重做習題 1。

:::spoiler

```cpp=
Count(first)
{   if (first != null) return Count(first->next);
    else return 0;
}
```
```cpp=
int Count(struct node *p)
{   if (p) return Count(p->next);
    else return 0;
}
```

:::

---
### 3. 設計三個演算法分分別來計算： <br> &emsp; (a) 由 first 指標指向開頭節點的雙向鏈結串； <br> &emsp; (b) 由 first 指標指向開頭空節點的雙向鏈結串； <br> &emsp; ($\text{c}$) 由 $p$ 指標指向其中一節點的雙向鏈結串；所含的非空節點總數目，串列中最後一個節點的 link 欄為 NULL。分析此三個演算法的時間複雜度。

:::spoiler

(a)
```cpp=
count = 0;
while (first != NULL)
{   first = first->next;
    count++;
}
for (cnt = 0, p = first; p; cnt++, p = p->link);
```
$O(n)$
(b)
```cpp=
count = 0;
while (first != NULL)
{   first = first->next;
    count++;
}
count--;
int CountNodesHead(struct node *first)
{   int cnt;
    for (cnt = 0, p = first->link; p; cnt++, p = p->link);
    return cnt;
}
```
$O(n)$
(c\)
```cpp=
count = 0;
if(p != NULL)
{    q = p->pre;
    while (p != NULL)
    {   p = p->next;
        count++;
    }
    while (q != NULL)
    {   q = q->pre;
        count++;
    }
}
for (cnt = 1, a = p->link; a; cnt++, a = a->link);
for (b = p->prev; b; cnt++, b = b->prev);
```
時間複雜度：$O(n)$

:::

---
### 4. 寫出三個程序，分別刪除由 first 指標指向開頭節點的 <br> &emsp; (a) 單向鏈結串列（含或不含開頭空節點）； <br> &emsp; (b) 單向環狀鏈結串列； <br> &emsp; ($\text{c}$) 雙向環狀鏈結串列； <br> 的所有節點。並計算此三程序的時間複雜度。

:::spoiler

(a)
```cpp=
//不含開頭空節點
while (first != NULL)
{   q = first;
    cout << q->data << endl;
    first = first->next;
}
for (q = p = first; p; q = p = p->next) free(q);
```
$O(n)$
```cpp=
//含開頭空節點
while (first->next != NULL)
{   p = first->next;
    first->next = p->next;
    cout<<p->data<<endl;
    first->next = p->next;
}
for (q = p = first->next; p; q = p = p->next) free(q);
```
$O(n)$
(b)
```cpp=
//不含開頭空節點
for (q = p= first; p != first; q = p = p->next) free(q);
// 含開頭空節點
for (q = p = first->next; p != first; q = p = p->next) free(q);
```
$O(n)$
(c\)
```cpp=
//不含開頭空節點
for (q = p = first; p != first; q = p = p->next) free(q);
// for (q=p=first; p!=first; q=p=p->prev) free(q);
// 含開頭空節點
for (q = p = first->next; p != first; q = p = p->next) free(q);
//for (q=p=first->prev; p!=first; q=p=p->prev) free(q);
```
時間複雜度：$O(n)$
:::

---
### 5. 令兩個鏈結串列分別為：$x = (x_1, x_2, ..., x_n)$ 與 $y = (y_1, y_2, ..., y_m)$，其穿插合併串列 $z$ 定義成：若 $m ≤ n$ 則 $z = (x_1, y_1, x_2, y_2, ..., x_m, y_m, x_{m+1}, x_{m+2}, ..., x_n)$ ，若 $m > n$ 則 $z = (x_1, y_1, x_2, y_2, ..., x_n, y_n, y_{n+1}, y_{n+2}, ..., y_m)$；而合併後，$x$ 與 $y$ 其原先每一節點現在都存於 $z$ 中，所以 $x$ 與 $y$ 將變為空串列。請設計演算法求得 $x$ 與 $y$ 的穿插合併串列 $z$；且合併過程中不能使用其他節點。請分別考慮： <br> &emsp; (a) 單向鏈結串列（含或不含開頭空節點）； <br> &emsp; (b) 單向環狀鏈結串列； <br> &emsp; ($\text{c}$) 雙向環狀鏈結串列；並計算演算法的時間複雜度。

:::spoiler

令節點結構如下：
```cpp=
struct node
{   int data;
    struct node *next;
};
```
或
```cpp=
struct Dnode
{   struct Dnode *prev;
    int data;
    struct Dnode *next;
};
struct node *first_x, *first_y, *first_z; 
// 前兩者分別指向串列 X, Y，而後者為空指標/開頭空白節點；或
struct Dnode *first_x, *first_y, *first_z;
```
(a) Singly linked list
```cpp=
//不含開頭空節點
struct node *MergeList(struct node *first_x, struct node *first_y)
{   struct node *a, *b, *first_z, *last;
    // cnt_x = CountNodes(first_x);    // CountNodes() 請參考習題 1
    // cnt_y = CountNodes(first_y);
    if (!first_x) return first_z = first_y;
    if (!first_y) return first_z = first_x;
    first_z = first_x;
    a = first_z->next;
    first_z->next = first_y;
    b = first_y->next;
    first_z->next = b;
    for (last = first_z->next; a && b; )
    {    last->next = a;
         a = a->next;
         last->next->next = b;
         b = b->next;
         last = b;
    }
    last->next = (a) ? a : b;
    first_x = first_y = NULL;
    return first_z;
}
```
```cpp=
// 含開頭空節點
struct node *MergeListHead(struct node *first_x, struct node *first_y, struct node *first_z) 
// Note: *first_z has been created in main()
{   struct node *a, *b, *last;
    if (!first_x->next) return first_z = first_y;
    if (!first_y->next) return first_z = first_x;
    for (a = first_x->next, b = first_y->next, last = first_z; a && b; )
    {   last->next = a;
        a = a->next;
        last->next->next = b;
        b = b->next;
        last = b;
    }
    last->next = (a) ? a : b;
    first_x->next = first_y = NULL;
    return first_z;
}
```
時間複雜度：$O(m+n)$
(b) Singly cyclic linked list
```cpp=
//不含開頭空節點
struct node *MergeList(struct node *first_x, struct node *first_y)
{   struct node *a, *b, *p, *first_z, *last;
    if (!first_x) return first_z = first_y;  // if X is empty
    if (!first_y) return first_z = first_x;  // if Y is empty 
    first_z = first_x;
    a = first_x->next;
    first_z->next = first_y;
    b = first_y->next;
    for (last = first_z->next; a != first_x && b != first_y; )
    {    last->next = a;
         a = a->next;
         last->next->next = b;
         b = b->next;
         last = b;
    }
    last->next = (a) ? a : b;
    for (p = last->next; p->next != first_x && p->next != first_y; p = p->next);
    p->next = first_z;
    first_x = first_y = NULL;
    return first_z;
}
```
```cpp=
// 含開頭空節點
struct node *MergeListHead(struct node *first_x, struct node *first_y, struct node *first_z) 
// Note: *first_z has been created in main()
{   struct node *a, *b, *first_z, *last;
    if (first_x->next == first_x) return first_z = first_y;
    if (first_y->next == first_y) return first_z = first_x;
    for (a=first_x->next, b=first_y->next, last=first_z; a && b; )
    {   last->next = a;
        a = a->next;
        last->next->next = b;
        b = b->next;
        last = b;
    }
    last->next = (a) ? a : b;
    for (p = last->next; !p->next != first_x && p->next != first_y; p = p->next);
    p->next = first_z
    first_x->next = first_x;
    first_y->next = first_y;
    return first_z;
}
```
時間複雜度：$O(m+n)$
($\text{c}$) Doubly cyclic linked list
```cpp=
//不含開頭空節點
struct Dnode *MergeList(struct Dnode *first_x, struct Dnode *first_y)
{   struct Dnode *a, *b, *p, *first_z, *last;
    if (!first_x) return first_z = first_y;  // if X is empty
    if (!first_y) return first_z = first_x;  // if Y is empty 
    first_z = first_x;
    a = first_x->next;
    first_z->next = first_y;
    b = first_y->next;
    first_z->next->prev = first_z;    
    for (last = first_z->next; a != first_x && b!=first_y; )
    {    last->next = a;
         a->prev = last;  //last->next->prev = last;
         a->next = b;
         b->prev = a;     //last->next->prev = last->next;
         a = a->next;
         b = b->next;
         last = b;
    }
    last->next = (a) ? a : b;
    for (p = last->next; p->next != first_x && p->next != first_y; p = p->next);
    p->next = first_z;
    first_z->prev = p;
    first_x = first_y = NULL;
    return first_z;
}
```
```cpp=
// 含開頭空節點
struct Dnode *MergeListHead(struct Dnode *first_x, struct Dnode *first_y, struct Dnode *first_z) 
// Note: *first_z has been created in main()
{   struct Dnode *a, *b, *first_z, *last;
    if (first_x->next == first_x) return first_z = first_y;
    if (first_y->next == first_y) return first_z = first_x;
    for (a = first_x->next, b = first_y->next, last = first_z; a && b; )
    {   last->next = a;
        a->prev = last;
        a->next = b;
        b->prev = a;
        a = a->next;
        b = b->next;
        last = b;
    }
    last->next = (a) ? a : b;
    for (p = last->next; !p->next != first_x && p->next != first_y; p = p->next);
    p->next = first_z;
    first_z->prev = p;
    first_x->prev = first_x->next = first_x;
    first_y->prev = first_y->next = first_y
    return first_z;
}
```
時間複雜度：$O(m+n)$

:::

---
### **6. 令兩個非遞減鏈結串列分別為：$x = (x_1, x_2, ..., x_n)$ 與 $y = (y_1, y_2, ..., y_m)$，每個鏈結串列中的節點是以資料欄值的非遞減順序排列。撰寫程序使能合併兩串列 $x$ 與 $y$，使成非遞減鏈結串列 $z$。合併過程中不能使用其他節點。並計算此演算法的時間複雜度。請分別考慮： <br> &emsp; (a) 單向鏈結串列（含或不含開頭空節點）； <br> &emsp; (b) 單向環狀鏈結串列； <br> &emsp; ($\text{c}$) 雙向環狀鏈結串列。

:::spoiler

令節點結構如下：
```cpp=
struct node
{   int data;
    struct node *next;
};
struct node *head_x, *head_y, *head_z;//前兩者分別指向串列 X, Y，而後者為空指標/開頭空白節點。
```
(b) Singly cyclic linked list
```cpp=
// 含開頭空節點
struct node *MergeListsNonDec(struct node *head_x, struct node *head_y)
{  struct node *a, *b, *p, *q, *sp, *sq, *last;
   if (head_x->next == head_x)
   {	head_z->next = head_y->next;
	last = last_y;  // last_y is global
	last->next = head_z;
   }
   else if (head_y->next == head_y)
   {	head_z->next = head_x->next;
	last = last_x;  // last_y is global
	last->next = head_z;
   }
   else
   {  head_z->next = (head_x->next->data <= head_y->next->data) ? head_x->next : head_y->next;
      for (p = sp = head_x, q = sq = head_y, a = sp->next, b = sq->next; (a != head_x && b != head_y); )
      {  for ( ; (a->data <= b->data) && (a!=head_x); p = a, a = a->next);
	    if (sp != p)
         {	  p->next = (b != head_y) ? b : head_z; 	sp = p;	}
         for ( ; (b->data <= a->data) && (b!=head_y); q = b, b = b->next);
         if (sq != q)
         {	  q->next = (a != head_x) ? a : head_z; 	sq = q;	}
	 }
       if (a != head_x)
       {  for ( ; p->next != head_x; p = p->next);
          p->next = head_z;
       }
       else if (b != head_y)
       {	for ( ; q->next != head_y; q = q->next);
		q->next = head_z;
	  }
   }
   Memo3->Lines->Add("Z: " + printSCL(head_z) + "<");
   head_x->next = head_x;
   head_y->next = head_y;
}
```
時間複雜度：$O(m+n)$

![](https://i.imgur.com/RgM4Xqb.png)
![](https://i.imgur.com/uDG01r1.png)

:::

---
### 7. 令 p 為指向環形鏈結串列的一指標，如何將此串列當作一佇列使用？（亦即寫出其新增與刪除元素的程序）。

:::spoiler

```cpp=
struct node
{   int data;
    struct node *next;
};//使 p 指向環狀串列任一個當開頭，令 q 指向 p 的前一個當環狀串列的結尾
struct node * p,*q;
q = p->next;
while (q->next != p) q = q->next;
int delete()//delete：將p 指到下一個即可刪除原本 p 所指的元素
{   r = p;
    p = p->next;
    return r->data;
}
void add( v ) //add：加到 q 後面
{   struct node *s;
    s->data = v;
    s->next = NULL;
    q->next = s;
    q = q->next;
}
```

:::

---
### 8. 多項式 (polynomial) 的數學表示為： $\begin{eqnarray}A(x) &=& \sum\limits_{i=0}^{n}{c_ix^i} \nonumber \\~&=& c_nx^n+c_{n-1}x^{n-1}+...+c_1x^1+c_0 \nonumber \\\\\end{eqnarray}$ 此為降冪排列，因 $x$ 的次數由大至小排列（若 $x$ 的次數由小至大排列，則為升冪排列）；此多項式的冪次為 $n$ 。請用鏈結串列來表示冪次為 $n$ 的降冪多項式。

 :::spoiler

```cpp=
#include <stdio.h>
#include <stdlib.h>
#define swap(a, b) { int t = a; a = b, b = t; }
typedef struct NodeOfPolynomial 
{   int coef, pow;     //Coefficient and Power
    struct NodeOfPolynomial *next; //Next term
} *Term;
// ----------------
/* ---上述4行宣告與下面5行同義，請留意！這宣告方式在後面頻繁使用
struct NodeOfPolynomial
{   int coef, pow;     //Coefficient and Power
     struct NodeOfPolynomial *next; //Next term
}; 
typedef struct NodeOfPolynomial *Term;
// Term 是個自定型態，即為 struct NodeOfPolynomial * 
下行的 Term NewTerm(int ceof, int pow) 
實則為 struct NodeOfPolynomial * NewTerm(int ceof, int pow)
--- */
Term NewTerm(int ceof, int pow) 
{   Term term = (Term)malloc(sizeof(struct NodeOfPolynomial));
    term->coef = ceof;
    term->pow = pow;
    term->next = NULL;
    return term;
}
void Sort(int *cbegin, int *cend, int *pbegin, int *pend) 
{   //Quick Sort
    if (pbegin < pend-1) 
    {   int split = *pbegin, *i = pbegin, *ci = cbegin;
        for (int *j = pbegin + 1, *cj = cbegin + 1; j != pend; ++j, ++cj) 
        {   if (*j > split) 
            {   ++i; ++ci;
                swap(*i, *j);
                swap(*ci, *cj);
            }
        }
        swap(*i, *pbegin);
        swap(*ci, *cbegin);
        sort(cbegin, ci, pbegin, i);
        sort(ci + 1, cend, i + 1, pend);
    }
}
void Output(Term polynomial) 
{   int i = 0;
    for (Term term = polynomial->next; term; term = term->next, ++i)    
        if (term->coef > 0) 
             printf(" + %dx^%d" + (!i<<1), term->coef, term->pow);
        else printf(" - %dx^%d", -term->coef, term->pow);
}
int main() 
{   int coefs[100], pows[100], size = 0;
    //Input coefficients and powers
    for (int *coef = coefs, *pow = pows; 
         scanf("%d %d", coef, pow) != EOF; ++coef, ++pow, ++size);
    //Sorting to achieve descending power polynomials
    Sort(coefs, coefs + size, pows, pows + size);

    Term polynomial = NewTerm(-1, -1), term = polynomial;

    for (int i = 0; i < size; ++i, term = term->next) 
         term->next = NewTerm(coefs[i], pows[i]);
    Output(polynomial);
    return 0;
}
```
![](https://i.imgur.com/OUlqQam.png)

:::

---
### 9. 令 $A$ 和 $B$ 皆為多項式， <br> &emsp; $A(x) = \sum\limits_{i=0}^{n}{a_ix^i}, B(x) = \sum\limits_{i=0}^{n}{b_ix^i}$ <br> 多項式相加的定義為： <br> &emsp; $A(x) + B(x) = \sum\limits_{i=0}^{n}{(a_i+b_i)x^i}$ <br> 請參考 3.6.1 節用鏈結串列表示多項式，設計出輸入多項式的程序，並與程式 4-17（多項式相加的程序）搭配，實作兩輸入多項式的相加，並輸出其結果。請分析並驗証使用演算法的時間與空間複雜度。 <br> 提示：可將節點設計成可儲存：非 $0$ 係數 $c_i$、其對應冪次 $i$ 與下一非 $0$ 項指標的節點。注意在多項式的 $n$ 很大而非 $0$ 項數很少時，鏈結串列的表示可節省空間。
:::spoiler
繼第8題
```cpp=
//Polynomial addition
Term Add(Term a, Term b)       //a and b are descending polynomial
{   Term result = NewTerm(-1, -1), term = result;
    a = a->next;
    b = b->next;  //Skip blank nodes
    while (a && b)     //If a and b are not empty, enter the loop
    {   if (a->pow > b->pow)
        {   term->next = NewTerm(a->coef, a->pow);
            a = a->next;
            term = term->next;
        }
        else if (a->pow < b->pow)
        {   term->next = NewTerm(b->coef, b->pow);
            b = b->next;
            term = term->next;
        }
        else
        {   if (a->coef - b->coef)
                term = term->next =
                           NewTerm(a->coef + b->coef, a->pow);
            a = a->next;
            b = b->next;
        }
    }
    for (a = a ? a : b; a; a = a->next, term = term->next)
        term->next = NewTerm(a->coef, a->pow);
    return result;
}
```
/* --- 執行結果
5 5   6 1   7 3
3 5   6 3
Ans : 8x^5 + 13x^3 + 6x^1

1 2   3 7   6 6
5 2   5 3
Ans : 3x^7 + 6x^6 + 5x^3 + 6x^2

57 6   7 3   32 5   -12 1
33 5   -12 3   -8 0
Ans : 57x^6 + 65x^5 - 5x^3 - 12x^1 - 8
--- */
![](https://i.imgur.com/03PVoNp.png)
時間複雜度：*O*($n+m$)，其中 $n$ 是多項式 A 中的項數，$m$ 是多項式 B 中的項數。

:::

---
### 10. 令 $A$ 和 $B$ 皆為多項式， <br> &emsp; $A(x) = \sum\limits_{i=0}^{n}{a_ix^i}, B(x) = \sum\limits_{i=0}^{n}{b_ix^i}$ <br> 多項式相加的定義為： <br> &emsp; $A(x) + B(x) = \sum\limits_{i=0}^{n}{(a_i+b_i)x^i}$ <br> 請用前題的鏈結串列表示並輸入兩多項式，並與程式 4-19（多項式相乘的程序）搭配，實作兩輸入多項式的相乘，並輸出其結果。請分析並驗証使用演算法的時間與空間複雜度。

:::spoiler

繼第8題
```cpp=
//Polynomial multiplication
Term Mul(Term a, Term b)       // a and b are descending polynomial
{   Term result = NewTerm(-1, -1), r, next;
    result->next = result;
    for (a = a->next; a; a = a->next)
    {   for (Term term = b->next; term; term = term->next)
        {   int coef = a->coef * term->coef,
                    pow  = a->pow + term->pow;
            for (r = result->next; pow < r->next->pow; r = r->next);
            if (pow > r->next->pow)
            {   next = r->next;
                r->next = NewTerm(coef, pow);
                r->next->next = next;
            }
            else r->next->coef += coef;
        }
    }
    r->next->next = NULL;
    return result;
}
```
/* --- 執行結果

5 5   6 1   7 3
3 5   6 3
Ans : 15x^10 + 51x^8 + 60x^6 + 36x^4

1 2   3 7   6 6
5 2   5 3
Ans : 15x^10 + 45x^9 + 30x^8 + 5x^5 + 5x^4

57 6   7 3   32 5   -12 1
33 5   -12 3   -8 0
Ans : 1881x^11 + 1056x^10 - 684x^9 - 153x^8 - 936x^6 - 256x^5 + 144x^4 - 56x^3 + 96x^1

--- */
![](https://i.imgur.com/tLFcu4a.png)
時間複雜度：*O*($nm$)，其中 $n$ 是多項式 A 中的項數，$m$ 是多項式 B 中的項數。

:::

---
### 11. 仿照 8、9 和 10 的題意，設計出多項式相減和相除的演算法。請分析所用演算法的時間與空間複雜度。

:::spoiler

```cpp=
//Polynomial subtraction
Term Sub(Term a, Term b)       //a and b are descending polynomial
{   Term result = NewTerm(-1, -1), term = result;
    a = a->next;
    b = b->next;  //Skip blank nodes
    while (a && b)     //If a and b are not empty, enter the loop
    {   if (a->pow > b->pow)
        {   term->next = NewTerm(a->coef, a->pow);
            a = a->next;
            term = term->next;
        }
        else if (a->pow < b->pow)
        {   term->next = NewTerm(-b->coef, b->pow);
            b = b->next;
            term = term->next;
        }
        else
        {   if (a->coef - b->coef)
                term = term->next =
                           NewTerm(a->coef - b->coef, a->pow);
            a = a->next;
            b = b->next;
        }
    }
    int pn = a ? 1 : -1;
    for (a = a ? a : b; a; a = a->next, term = term->next)
        term->next = NewTerm(a->coef * pn, a->pow);
    return result;
}
```
/* --- 執行結果

5 5   6 1   7 3
3 5   6 3
Ans : 2x^5 + 1x^3 + 6x^1

1 2   3 7   6 6
5 2   5 3
Ans : 3x^7 + 6x^6 - 5x^3 - 4x^2

57 6   7 3   32 5   -12 1
33 5   -12 3   -8 0
Ans : 57x^6 - 1x^5 + 19x^3 - 12x^1 + 8

--- */
![](https://i.imgur.com/G3vXPNQ.png)
時間複雜度：*O*($n+m$)，其中 $n$ 是多項式 A 中的項數，$m$ 是多項式 B 中的項數。
```cpp=
//Polynomial division
#include <stdio.h>
//#include <stdlib.h>     //CodeBlock會跟內建函式衝到
#define swap(type, a, b) { type t = a; a = b, b = t; }
typedef struct Fraction     //Fraction
{   int num, den;   //Numerator and Denominator
} Frac;
typedef struct NodeOfPolynomial
{   struct Fraction coef;          //Coefficient
    int pow;                       //Power
    struct NodeOfPolynomial *next; //Next term
} *Term;
// Functions of Fraction
inline Frac Red(struct Fraction frac)    //Reduction of fraction
{   int a = abs(frac.num), b = abs(frac.den), c;
    while (b) c = b, b = a % b, a = c;     //GCD
    return (Frac){frac.num / a, frac.den / a};
}
inline struct Fraction add(Frac a, Frac b)     //Addition
{   return Red((Frac){a.num * b.den + b.num * a.den, a.den * b.den});
}
inline struct Fraction sub(Frac a, Frac b)     //Subtraction
{   return Red((Frac){a.num * b.den - b.num * a.den, a.den * b.den});
}
inline struct Fraction mul(Frac a, Frac b)     //Multiplication
{   return Red((struct Fraction){a.num * b.num, a.den * b.den});
}
inline struct Fraction div(Frac a, Frac b)     //Division
{   return Red((struct Fraction){a.num * b.den, b.num * a.den});
}
inline void output(struct Fraction frac)
{   if (frac.den == 1) printf("%d", abs(frac.num));
    else printf("(%d/%d)", abs(frac.num), frac.den);
}
// Functions of Polynomial
Term NewTerm(struct Fraction ceof, int pow)
{   Term term = (Term)malloc(sizeof(struct NodeOfPolynomial));
    term->coef = ceof;
    term->pow = pow;
    term->next = NULL;
    return term;
}
void Sub(Term A, Term B)       //Polynomial subtraction
{   Term pre = A, a = A->next, b = B->next, next;
    free(B);
    while (a && b)     //If a and b are not empty, enter the loop
    {   if (a->pow > b->pow)
        {   pre = a;
            a = a->next;
        }
        else if (a->pow < b->pow)
        {   b->coef.num = -b->coef.num;
            pre->next = b;
            pre = b;
            next = b->next;
            b->next = a;
            b = next;
        }
        else
        {   a->coef = sub(a->coef, b->coef);
            if (a->coef.num)
                pre = a = a->next;
            else
                pre->next = a->next, free(a), a = pre->next;
            next = b->next;
            free(b);
            b = next;
        }
    }
    if (b) pre->next = b;
}
Term *Div(Term a, Term b)    //Polynomial division
{   Term result = NewTerm((struct Fraction){-1, 1}, -1), t,
    term = result, tmp = NewTerm((Frac){-1, 1}, -1);
    for (a = a->next, t = tmp; a; a = a->next, t = t->next)
        t->next = NewTerm(a->coef, a->pow);
    a = tmp;
    while (a->next->pow >= b->next->pow)
    {   Term mcl = NewTerm((Frac){-1, 1}, -1), m = mcl;
        term = term->next = NewTerm(div(a->next->coef, 
            b->next->coef), a->next->pow - b->next->pow);
        for (Term bi = b->next; bi; bi = bi->next, m = m->next)
            m->next = NewTerm(mul(bi->coef, term->coef), 
                bi->pow+term->pow);
        Sub(a, mcl);
    }
    Term * ans = (Term *)malloc(sizeof(Term) * 2);
    ans[0] = result;         //Quotient
    ans[1] = a;              //Remainder
    return ans;
}

inline void Clear(Term pol)
{   for (Term next; pol; next = pol->next, free(pol), pol = next);
}
void Output(Term polynomial)
{   int i = 0;
    for (Term term = polynomial->next; term; term = term->next, ++i)
    {   printf(term->coef.num > 0 ? " + " + (!i<<1) : " - ");
        output(term->coef);
        if (term->pow)
            printf("x^%d", term->pow);
    }
    puts("");
}
void Sort(int *cbegin, int *cend, int *pbegin, int *pend)   //Quick Sort
{   if (pbegin < pend - 1)
    {   int split = *pbegin, *i = pbegin, *ci = cbegin;
        for (int *j = pbegin + 1, *cj = cbegin + 1; j != pend; ++j, ++cj)
        {   if (*j > split)
            {   ++i;
                ++ci;
                swap(int, *i, *j);
                swap(int, *ci, *cj);
            }
        }
        swap(int, *i, *pbegin);
        swap(int, *ci, *cbegin);
        Sort(cbegin, ci, pbegin, i);
        Sort(ci + 1, cend, i + 1, pend);
    }
}
int main()
{   int coefs1[100], pows1[100], size1 = 1;
    int coefs2[100], pows2[100], size2 = 1;
    //Input coefficients and powers
    for (int *coef = coefs1, *pow = pows1; scanf("%d %d", coef, pow)
            != EOF && getchar() != '\n'; ++coef, ++pow, ++size1);
    for (int *coef = coefs2, *pow = pows2; scanf("%d %d", coef, pow)
            != EOF && getchar() != '\n'; ++coef, ++pow, ++size2);
    //Sorting to achieve descending power polynomials
    Sort(coefs1, coefs1 + size1, pows1, pows1 + size1);
    Sort(coefs2, coefs2 + size2, pows2, pows2 + size2);
    Term polynomial1 = NewTerm((struct Fraction){-1, 1}, -1),
         term1 = polynomial1,
         polynomial2 = NewTerm((struct Fraction){-1, 1}, -1),
         term2 = polynomial2;
    for (int i = 0; i < size1; ++i, term1 = term1->next)
        term1->next = NewTerm((Frac){coefs1[i], 1}, pows1[i]);
    for (int i = 0; i < size2; ++i, term2 = term2->next)
        term2->next = NewTerm((Frac){coefs2[i], 1}, pows2[i]);
    Term *polynomial3 = Div(polynomial1, polynomial2);
    printf("Quotient :");
    Output(polynomial3[0]);
    printf("Remainder:");
    Output(polynomial3[1]);
    Clear(polynomial3[0]);
    Clear(polynomial3[1]);
    free(polynomial3);
    return 0;
}
```
/* --- 執行結果

2 2   3 1   1 0
1 1   3 0
Quotient : 2x^1 - 3
Remainder: 10
3 2   2 1   1 0
2 1   3 0
Quotient : (3/2)x^1 - (5/4)
Remainder: (19/4)
2 5   1 4  -2 1   1 0
5 2   4 1
Quotient : (2/5)x^3 - (3/25)x^2 + (12/125)x^1 - (48/625)
Remainder: - (1058/625)x^1 + 1

--- */
![](https://i.imgur.com/3ICfAVp.png)

時間複雜度：$O(max(nm, n(em-en)))$，其中 $m$ 是多項式 $A$ 中的項數，$n$ 是多項式 $B$ 中的項數，$em$ 是多項式 $A$ 的最大冪，$en$ 是多項式 $B$ 的最大冪。
:::

---
### 12. 請將習題7~10與第二章陣列的使用做比較，討論陣列與鏈結串列在表示多項式時的優劣。

:::spoiler

&emsp; 陣列在表示多項式時，可以由陣列中的位置得知多項式的次方，運算時可以直接使用；鏈結串列則須多紀錄一個次方數，在運算時才比較方便。然而，當次方很大而非 $0$ 項數很少時，陣列亦會紀錄次方數為 $0$ 的項數，而浪費了空間；鏈結串列卻可跳過次方數為 $0$ 的項數，達到節省空間的優勢。

:::

---
### 13. 利用環形串列重做習題 7~10。請比較兩做法的時間複雜度。

:::spoiler

&emsp; 一般而言，線性串列、環狀串列、含開頭空白節點的環狀串列、或雙向串列在搜尋、新增(至某節點後)、刪除... 皆有相同的時間複雜度(即令處理的細節互有所異)；唯在邊界條件 (first?=NULL、head?=NULL、...)判定時，含開頭空白節點的環狀串列可省下檢測是否為空串列的考量。

:::

---
### 14. 設計一種串列表示法可以在串列兩頭做刪除與插入的動作，這種結構稱為「雙向佇列」 (deque) ，寫一個自兩端做插入動作的程序。請分別考慮： <br> &emsp; (a) 單向鏈結串列（含或不含開頭空節點）； <br> &emsp; (b) 單向環狀鏈結串列； <br> &emsp; (c\) 雙向環狀鏈結串列。

:::spoiler

(a)
```cpp=
typedef struct SingleNode
{   int data;
    struct SingleNode *next;
} *SNode;
SNode front = NULL, rear = NULL;
SNode NewNode(int data)
{   SNode node = (SNode)malloc(sizeof(struct SingleNode));
    node->data = data;
    node->next = NULL;
    return node;
}
void InsertFront(SNode x)
{   if (!front) front = rear = x;
    else
    {   x->next = front;
        front = x;
    }
}
void InserRear(SNode x)
{   if (!rear) front = rear = x;
    else
    {   rear->next = x;
        rear = x;
    }
}
```
(b)
```cpp=
typedef struct SingleCNode
{   int data;
    struct SingleCNode *next;
} *SCNode;
SCNode front = NULL, rear = NULL;
SCNode NewNode(int data)
{   SCNode node = (SCNode)malloc(sizeof(struct SingleCNode));
    node->data = data;
    node->next = NULL;
    return node;
}
void InsertFront(SCNode x)
{   if (!front) front = rear = x->next = x;
    else
    {   rear->next = x;
        x->next = front;
        front = x;
    }
}
void InserRear(SCNode x)
{   if (!rear) front = rear = x->next = x;
    else
    {   x->next = rear->next;
        rear->next = x;
        rear = x;
    }
}
```
(c\)
```cpp=
typedef struct DoubleCNode
{   int data;
    struct DoubleCNode *prev, *next;
} *DCNode;

DCNode front = NULL, rear = NULL;

DCNode NewNode(int data)
{   DCNode node = (DCNode)malloc(sizeof(struct DoubleCNode));
    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    return node;
}
void InsertFront(DCNode x)
{   if (!front)
        front = rear = x->prev = x->next = x;
    else
    {   x->prev = front->prev;
        x->next = front;
        front->prev = x;
        rear->next = x;
        front = x;
    }
}
void InsertRear(DCNode x)
{   if (!rear)
        front = rear = x->prev = x->next = x;
    else
    {   x->next = rear->next;
        x->prev = rear;
        rear->next = x;
        front->prev = x;
        rear = x;
    }
}
```

:::

---
### 15. 如節 4.7 所介紹：當矩陣的非 $0$ 元素很多時，稱此矩陣為稀疏矩陣 (sparse matrix)。請設計儲存非 $0$ 元素的節點結構。若所設計的結構與圖 4-31 不同，請比較並討論其優劣。

 :::spoiler
節點結構圖示如下：(在此設計的節點與圖4-31相似，僅有變數名稱不同！)
| 圖 4-31 | 本題 |
| :------: | :------: |
| ![image](https://hackmd.io/_uploads/rJhwAKfKp.png =90%x)  | ![image](https://hackmd.io/_uploads/BJhg0tGKp.png  =90%x)  | 

宣告如下：
```cpp=
typedef struct Matrix_Node
{   int data;
    struct Pos
    {   int i, j;
    } pos;
    struct Matrix_Node *next_r, *next_c;
} *Node;
```

:::

---
### 16. 請設計演算法並實作：將所輸入的資料，存成稀疏矩陣。

 :::spoiler
請對照圖4-32！下列解法並沒有用到圖4-32最左欄(最上列)的開頭空白列(空白欄)節點：而各列、各欄皆為環狀串列
```cpp=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Matrix_Node
{   int data;
    struct Pos
    {   int i, j;
    } pos;
    struct Matrix_Node *next_r, *next_c;
} *Node;

typedef struct Sparse_Matrix
{   Node *row_f, *row_l,
    *col_f, *col_l;
} Sparse_Matrix;
// Sparse_Matrix 定義了由4個指標*row_f, *row_l, *col_f, *col_l，型態皆為 struct Matrix_Node * 
// *row_f[i] (*row_l[i]) 會指向第i列的第一(最後)節點；在Initialization動態產生
// *col_f[j] (*col_l[j]) 會指向第j欄的第一(最後)節點；在Initialization動態產生
void Initialization(Sparse_Matrix *matrix, int m, int p)
{   matrix->row_f = (Node *)malloc(sizeof(Node) * m);
    matrix->row_l = (Node *)malloc(sizeof(Node) * m);
    matrix->col_f = (Node *)malloc(sizeof(Node) * p);
    matrix->col_l = (Node *)malloc(sizeof(Node) * p);
    memset(matrix->row_f, 0, sizeof(Node) * m);
    memset(matrix->row_l, 0, sizeof(Node) * m);
    memset(matrix->col_f, 0, sizeof(Node) * p);
    memset(matrix->col_f, 0, sizeof(Node) * p);
} // 初始值皆為 NULL (0)：各行各列皆為空串列

Node NewNode(const int data, int i, int j)
{   Node node = (Node)malloc(sizeof(struct Matrix_Node));
    node->data = data;
    node->pos.i = i;
    node->pos.j = j;
    node->next_r = NULL;
    node->next_c = NULL;
    return node;
}

void InsertLastR(Node *first, Node *last, Node x)
{   if (!*first) *first = *last = x;
    else
    {   (*last)->next_r = x;
        *last = x;
    }
}  // 新增在 row i 串列之後

void InsertLastC(Node *first, Node *last, Node x)
{   if (!*first) *first = *last = x;
    else
    {   (*last)->next_c = x;
        *last = x;
    }
}  // 新增在 col j 串列之後

Sparse_Matrix a, b, result;

void Scan(Sparse_Matrix sm, int m, int p)
{   int n;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < p; j++)
        {   scanf("%d", &n);
            if (n)
            {   Node x = NewNode(n, i, j);
                InsertLastR(&sm.row_f[i], &sm.row_l[i], x);
                InsertLastC(&sm.col_f[j], &sm.col_l[j], x);
            }
        }
}

void Build(int m, int p)
{   Initialization(&a, m, p);
    Initialization(&b, m, p);
    Scan(a, m, p);
    Scan(b, m, p);
}   // 新建並讀入大小為 m*p 的矩陣：a, b；輸入時將所有 m*p 的值(含諸多0)皆讀入！為0的值不會存入
// 測試結果請見習題17
```

:::

---
### 17. 請設計演算法，解決兩稀疏矩陣的相加。請分析演算法的複雜度。
:::spoiler
```cpp=
void Add(Sparse_Matrix a, Sparse_Matrix b, int m, int p)
{   Initialization(&result, m, p);
    for (int i = 0, j; i < m; i++)
    {   Node aj = a.row_f[i], bj = b.row_f[i], x;
        while (aj && bj)
        {   if (aj->pos.j < bj->pos.j)
            {   x = NewNode(aj->data, i, aj->pos.j);
                j = aj->pos.j;
                aj = aj->next_r;
            }
            else if (aj->pos.j > bj->pos.j)
            {   x = NewNode(bj->data, i, bj->pos.j);
                j = bj->pos.j;
                bj = bj->next_r;
            }
            else
            {   x = NewNode(aj->data + bj->data, i, aj->pos.j);
                j = aj->pos.j;
                aj = aj->next_r;
                bj = bj->next_r;
            }
            InsertLastR(&result.row_f[i], &result.row_l[i], x);
            InsertLastC(&result.col_f[j], &result.col_l[j], x);
        }
        while (aj)
        {   x = NewNode(aj->data, i, aj->pos.j);
            j = aj->pos.j;
            aj = aj->next_r;
            InsertLastR(&result.row_f[i], &result.row_l[i], x);
            InsertLastC(&result.col_f[j], &result.col_l[j], x);
        }
        while (bj)
        {   x = NewNode(bj->data, i, bj->pos.j);
            j = bj->pos.j;
            bj = bj->next_r;
            InsertLastR(&result.row_f[i], &result.row_l[i], x);
            InsertLastC(&result.col_f[j], &result.col_l[j], x);
        }
    }
}

void PrintZ(int left, int right)
{   while (left++ < right)
        printf("%d ", 0);
}

void Output(Sparse_Matrix ms, int m, int p)
{   puts("");
    for (int i = 0; i < m; i++)
    {   Node x = ms.row_f[i];
        for (int j = 0; j < p; x = x->next_r)
        {   if (!x)
            {   PrintZ(j, p);
                break;
            }
            PrintZ(j, x->pos.j);
            printf("%d ", x->data);
            j = x->pos.j + 1;
        }
        puts("");
    }
}

int main()
{   int m, p;
    scanf("%d %d", &m, &p);
    Build(m, p);
    Add(a, b, m, p);
    printf(“\nResult:”);
    Output(result, m, p);
}
```
/* --- 執行結果

5 5
0 0 3 0 6
0 7 0 0 0
5 3 0 0 0
0 0 0 5 0
0 7 0 0 0

0 0 5 0 0
0 2 0 0 8
3 0 0 0 2
0 0 0 2 1
0 0 3 0 0

Result:
0 0 8 0 6
0 9 0 0 8
8 3 0 0 2
0 0 0 7 1
0 7 3 0 0

--- */


![](https://i.imgur.com/CmrIQLD.png)
時間複雜度：$O(n+m)$，其中 $n$ 是稀疏矩陣 $A$ 中非零元素的數量，$m$ 是稀疏矩陣 $B$ 中非零元素的數量。

:::
---
### **18. 請設計演算法，解決兩稀疏矩陣的相乘。請分析演算法的複雜度。
:::spoiler

```cpp=
void Mul(Sparse_Matrix a, Sparse_Matrix b, int m, int p, int q)
{   Initialization(&result, m, q);
    for (int i = 0; i < m; i++)
    {   for (int j = 0, n; j < q; j++)
        {   Node ap = a.row_f[i], bp = b.col_f[j], x;
            n = 0;
            while (ap && bp)
            {   if (ap->pos.j < bp->pos.i)
                    ap = ap->next_r;
                else if (ap->pos.j > bp->pos.i)
                    bp = bp->next_c;
                else
                {   n += ap->data * bp->data;
                    ap = ap->next_r;
                    bp = bp->next_c;
                }
            }
            if (n)
            {   x = NewNode(n, i, j);
                InsertLastR(&result.row_f[i], &result.row_l[i], x);
                InsertLastC(&result.col_f[j], &result.col_l[j], x);
            }
        }
    }
}

int main()
{   int m, p, q;
    scanf("%d %d %d", &m, &p, &q);
    Build(m, p, q);
    Mul(a, b, m, p, q);
    printf("\nResult:");
    Output(result, m, q);
}
```
/* --- 執行結果
5 5 5
0 0 3 0 6
0 7 0 0 0
5 3 0 0 0
0 0 0 5 0
0 7 0 0 0

0 0 5 0 0
0 2 0 0 8
3 0 0 0 2
0 0 0 2 1
0 0 3 0 0

Result:
9 0 18 0 6
0 14 0 0 56
0 6 25 0 24
0 0 0 10 5
0 14 0 0 56

--- */

![](https://i.imgur.com/3HCZJFi.png)
時間複雜度：$O(nm + pq)$，其中 $n$ 是稀疏矩陣 $A$ 中非零元素的數量，$m$ 是稀疏矩陣 $B$ 中非零元素的數量，$p$ 是稀疏矩陣 $A$ 中的行數，$q$ 是稀疏矩陣 $B$ 中的列數 。

:::
---
