# 資料結構與演算法 習題解答 第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
---- */
:::
---
### 2. 二項式係數 (binomial coefficient) 的定義如下： <br>   $\dbinom{n}{m} = \dfrac{n!}{m!(n-m)!};$ <br> 請用迴圈撰寫程式，計算二項式係數（輸入 $n$，求 <br>   $\dbinom{n}{m}$，$m=0, 1, 2, …, n$）。 <br> 而該式可用下面的遞迴式表示： <br>   $\dbinom{n}{m} = \dbinom{n-1}{m} + \dbinom{n-1}{m-1}$ <br> 請用遞迴的技巧撰寫程式，計算二項式係數。試比較兩者的優劣。
$\displaystyle\sum_{k=1}^{n}x(t_k)$
:::spoiler 遞迴版本:
 請將二項式係數 $\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
---- */
利用迴圈可在 $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
:::
---
### 3. 費氏 (Fibonacci) 數列被定義成： <br>   (1) $F_0 = 0, F_1 = 1;$ <br>   (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
---- */
:::
:::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
---- */
:::
---
### 4. Lucas 數列被定義成： <br>   (1) $L_0 = 2, L_1 = 1;$ <br>   (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
>---- */
>
>:::
>:::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
>---- */
>
>:::
:::
---
### 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
---- */
:::
::: 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;
}
}
```
/* ---- 執行結果:
 
:::
:::spoiler 遞迴與迴圈執行時間比較 (僅供參考；CPU: RAM: OS: Windows 10)：
| 遞迴版執行時間 | 迴圈版執行時間 |
| -------- | -------- |
|  |  |
:::
---
### 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*/
---- */
:::
---
### 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 請見下表：
   $S$               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.
---- */
:::
---
### 8. 請參考範例1-5、程式1-4，考慮輸入為 $n$ 個圓盤的河內塔搬運問題： <br>   (a) 實作出有三根支柱，搬運河內塔的遞迴程式； <br>   (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 |  |
|:------------------------------------:|:------------------------------------:|
| 更多細節 $n$ = 3 |  |
:::
```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 |  |
|:------------------------------------:|:------------------------------------:|
| 次數比較 |  |
:::
---
### 9. 比較 $n^3$ 和 $2^n$ 這兩個函式，計算出哪個 $n$ 值會使後者大於前者。
:::spoiler
當 $n = 10$ 時, $n^3 =1000 < 2^n = 1024$; 當 $n > 10$ 時, $n^3 < 2^n$。
:::
---
### 10. 使用數學歸納法證明： <br>   (a) $\sum\limits_{1≤i≤n}{i}=\dfrac{n(n+1)}{2},n≥1;$ <br>   (b)$\sum\limits_{1≤i≤n}{i^2}=\dfrac{n(n+1)(2n+1)}{6},n≥1;$ <br>   (c\) $\sum\limits_{1≤i≤n}{x^i}=\dfrac{x^{n+1}-1}{x-1},x≠1,n≥0;$ <br>   (d) $\sum\limits_{1≤i≤n}{2i-1}=n^2。$
>:::spoiler (a)
>
>  當 $n$ = $1$ 時, $\sum\limits_{i=1}^{1}{i} = 1 = \tfrac{1(1+1)}{2}$ 成立;
>  設 $n$ = $k$, $\sum\limits_{i=1}^{k}{i} = \tfrac{k(k+1)}{2}$ 成立;
> 則當 $n$ = $k+1$, $\sum\limits_{i=1}^{k+1}{i} = \sum\limits_{i=1}^{k}{i} + (k+1)$
>假設:
>  $\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}$
>  當 $n$ = $k$ + $1$ 時原式亦成立，則根據數學歸納法，即可得證。
>
>:::
>
>:::spoiler (b)
>
>  當 $n$ = $1$ 時, $\sum\limits_{i=1}^{1}{i^2} = 1 = \tfrac{1×2×3}{6}$ 成立;
>  設 $n$ = $k$, $\sum\limits_{i=1}^{k}{i^2} = \tfrac{k(k+1)(2k+1)}{6}$ 成立;
> 則當 $n$ = $k+1$, $\sum\limits_{i=1}^{k+1}{i^2} = \sum\limits_{i=1}^{k}{i^2} + (k+1)^2$
>假設:
>  $\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}$
>  當 $n$ = $k$ + $1$ 時原式亦成立，則根據數學歸納法，即可得證。
>
>:::
>
>:::spoiler (c\)
>
>  當 $n$ = $0$ 時, $\sum\limits_{i=0}^{0}{x^i} = x^0 = 1 =\tfrac{x-1}{x-1}$ 成立;
>  設 $n$ = $k$, $\sum\limits_{i=0}^{k}{x^i} = \tfrac{x^{k+1}-1}{x-1}$ 成立;
> 則當 $n$ = $k+1$, $\sum\limits_{i=0}^{k+1}{x^i} = \sum\limits_{i=0}^{k}{x^i} + x^{k+1}$
>假設:
>  $\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}$
>  當 $n$ = $k$ + $1$ 時原式亦成立，則根據數學歸納法，即可得證。
>
>:::
>
>:::spoiler (d)
>
>  當 $n$ = $1$ 時, $\sum\limits_{i=1}^{1}{(2i-1)} = 1 = 1^2$ 成立;
>  設 $n$ = $k$, $\sum\limits_{i=1}^{k}{(2i-1)} = k^2$ 成立;
> 則當 $n$ = $k+1$, $\sum\limits_{i=1}^{k+1}{(2i-1)} = \sum\limits_{i=1}^{k}{(2i-1)} + 2(k+1)-1$
>假設:
>  $\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}$
>  當 $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>   (a) $5n^2-6n = Θ(n^2)$ <br>   (b) $n! = Ο (n^n)$ <br>   (c\) $2n^22^n+nlogn = Θ(n^22^n)$ <br>   (d) $\sum\limits_{i=0}^{n}{i^2}=Θ(n^3)$ <br>   (e) $\sum\limits_{i=0}^{n}{i^3}=Θ(n^4)$ <br>   (f) $n^{2^n}$+$6×2^n$ = $Θ$($n^{2^n})$ <br>   (g) $n^3+10^6n^2 = Θ(n^3)$ <br>   (h) $6n^3/(logn+1) =Ο (n^3)$ <br>   (i) $n^{1.001}+nlogn = Θ(n^{1.001} )$ <br>   (j) $n^k+ε+n^klogn = Θ(n^k+ε) \text{ for all k and }ε, k ≥ 0,\text{and } ε > 0$ <br>   (k) $10n^3+15n^4+100n^22^n = Ο (100n^22^n)$ <br>   (l) $33n^3+4n^2 = Ω (n^2)$ <br>   (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$，使得上式成立。(請看下圖)
>
>
>:::
>
>:::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>   (a) $10n^2+9 = O(n)$ <br>   (b) $n^2logn = Θ(n^2)$ <br>   (c\) $\frac{n^2}{logn} = Θ(n^2)$ <br>   (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>   (a) A[$0:n$]； <br>   (b) B[$-23:29$]; <br>   (c\) C[$-1:n$][$1:m$]； <br>   (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$ 開始，而且沒有下界、上界範圍的考量。這個題目旨在希望讀者對陣列內的個數／內容與註標定址有較廣泛的聯想。若希望用 "下界...上界" 來定位陣列元素，可以用指標來完成。請看下面的例子：
其中前三行是程式的設定（第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>   (a) 陣列 $A$ 是以列為優先存放； <br>   (b) 陣列 $A$ 是以行為優先存放。
:::spoiler
:::
 令 $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
---- */
:::
---
### 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>   (a) 找出 front[$i$] 和 rear[$i$] 的適當的起始和終止條件。 <br>   (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>      <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$。
                
::: 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>   (a) 在此帶狀 $D_{n,a}$ 中有多少個元素？ <br>   (b) 對於帶狀 $D_{n,a}$ 中的元素 $d_{ij}$ 而言，$i$ 與 $j$ 之間的關係為何？ <br>   (c\) 假設帶狀 $D_{n,a}$ 以對角線為主，並從最低的對角線開始，循序儲存在陣列 *A* 中。例如，圖 2-22 (b) 中的帶狀矩陣 $D_{5,2}$ 的表示法如下： <br>  <br> 找出在 $D_{n,a}$ 的下帶狀區域中的任一元素 $d_{ij}$ 的定址公式，即輸入 $i$ 和 $j$，求出 $k$，$d_{ij}$ = $A[k]$。 <br>              <br>                  
::: spoiler
(a) 主對角線有 $n$ 個元素，以其為基準，上方的 $1, 2, ... , a-1$ 條對角線分別有 $n-1,\ n-2,\ ...\ ,\ n-a+1$ 個元素，如下圖左；
|  |  |
|----|----|
於其下方的 $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>   (a) 在此帶狀 $D_{n,a,b}$ 中有多少個元素？ <br>   (b) 對於帶狀 $D_{n,a,b}$ 中的元素 $d_{ij}$ 而言，$i$ 與 $j$ 之間的關係為何？ <br>   (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>               
(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})$
例子：$a=3,\ b=2,\ n=8$
代入上式可得元素個數共 28 個 (見下圖右下)
亦可用對角線優先的觀點來想：
主對角線 $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
程式實作如下：
```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|
---- */
:::
---
---
## 第三章 堆疊和佇列 習題解答
---
### 1. 圖 3-31 描繪了一個鐵路調度軌道，每一節車廂都編號 $1, 2, 3$, ..., $n$，並按順序從左到右停放在軌道上，車廂可以從任何一條橫向軌道一次一台的移進垂直軌道，而移進垂直軌道的車廂也可以一次一台的移到任何一條橫向軌道，則垂直軌道就像一個堆疊，新移進車廂都在最上層，能移出的車廂也是最上層的那一個。假設 $n$ = $3$ 時，我們可以先移車廂 $1$ 進垂直軌道，再來是車廂 $2$，最後是車廂 $3$，然後我們就得到一個新的順序 $3, 2, 1$；當 $n$ = $3$ 和 $4$ 時，可以得到哪幾種有可能的車廂排列？有哪幾種排列是不可能的？ <br>             
:::spoiler 數量可藉由離散數學中介紹的 Catalan 數列求一般解
當 $n = 3$ 時
  可能的排列有 $5$ 種：$123, 132, 213, 231, 321$
  不可能的排列有 $1$ 種：$312$
當 $n = 4$ 時
  可能的排列有 $14$ 種 ： $1234, 1243, 1324, 1342, 1432, 2134, 2143, 2314, 2341, 2431, 3421, 3241, 3214, 4321$
  不可能的排列有 $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>   (a) 使用 front, rear 和 $n$，設計一個公式來求出串列中元素的個數。 <br>   (b) 寫一個演算法來刪除串列中第 $k$ 個元素。 <br>   (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>   (a) 1+2-3×4/5×6/7-8/9 <br>   (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>   (a) A×B×C <br>   (b) -A+B-C+D <br>   (c\) A×-B+C <br>   (d) (A+B)×D+E/(F+A×D)+C <br>   (e) A&&B\||C\||!(E>F) <br>   (f) !(A&&!((B<C)\||(C>D)))\||(C<E) <br>   (g) A and B or C or not (E>F) <br>   (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>   (a) 在演算法 3-3 中，假如一個運算式 e 內含有 $n$ 個運算子和標點符號，則堆疊中最多會放進多少個元素？ <br>   (b) 假如運算式e有n 個運算子，且括號最深有6層（如：(..(..)..) + (..(..(..)..)..) 此式括號最深就是 3 層），則 (a) 的答案會是多少？
:::spoiler
(a)
  當所有運算皆以由左到右的順序計算時 (如：運算子皆為 + ) 且没有 “(“, “)”時，所有運算子皆得放入 stack 中，於是 stack 最多會放入 $n$ 個元素。
(b)
  所有右括號皆不會被 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>   (a) 將習題 6 表示成對應的前序表示。 <br>   (b) 寫一個演算法來計算前序表示法 e。 <br>   (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 做
  push : Stack0[++top] = element;
  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)$ |
:::
---
### 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;
}
```
:::
---
### 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;
}
```
:::
---
### 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);
}
}
```
 請將上述遞迴演算法改用非遞迴方式。
:::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>   (a) 由 first 指標指向開頭節點的雙向鏈結串； <br>   (b) 由 first 指標指向開頭空節點的雙向鏈結串； <br>   ($\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>   (a) 單向鏈結串列（含或不含開頭空節點）； <br>   (b) 單向環狀鏈結串列； <br>   ($\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>   (a) 單向鏈結串列（含或不含開頭空節點）； <br>   (b) 單向環狀鏈結串列； <br>   ($\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>   (a) 單向鏈結串列（含或不含開頭空節點）； <br>   (b) 單向環狀鏈結串列； <br>   ($\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)$
:::
---
### 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;
}
```
:::
---
### 9. 令 $A$ 和 $B$ 皆為多項式， <br>   $A(x) = \sum\limits_{i=0}^{n}{a_ix^i}, B(x) = \sum\limits_{i=0}^{n}{b_ix^i}$ <br> 多項式相加的定義為： <br>   $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
--- */
時間複雜度：*O*($n+m$)，其中 $n$ 是多項式 A 中的項數，$m$ 是多項式 B 中的項數。
:::
---
### 10. 令 $A$ 和 $B$ 皆為多項式， <br>   $A(x) = \sum\limits_{i=0}^{n}{a_ix^i}, B(x) = \sum\limits_{i=0}^{n}{b_ix^i}$ <br> 多項式相加的定義為： <br>   $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
--- */
時間複雜度：*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
--- */
時間複雜度：*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
--- */
時間複雜度：$O(max(nm, n(em-en)))$，其中 $m$ 是多項式 $A$ 中的項數，$n$ 是多項式 $B$ 中的項數，$em$ 是多項式 $A$ 的最大冪，$en$ 是多項式 $B$ 的最大冪。
:::
---
### 12. 請將習題7~10與第二章陣列的使用做比較，討論陣列與鏈結串列在表示多項式時的優劣。
:::spoiler
  陣列在表示多項式時，可以由陣列中的位置得知多項式的次方，運算時可以直接使用；鏈結串列則須多紀錄一個次方數，在運算時才比較方便。然而，當次方很大而非 $0$ 項數很少時，陣列亦會紀錄次方數為 $0$ 的項數，而浪費了空間；鏈結串列卻可跳過次方數為 $0$ 的項數，達到節省空間的優勢。
:::
---
### 13. 利用環形串列重做習題 7~10。請比較兩做法的時間複雜度。
:::spoiler
  一般而言，線性串列、環狀串列、含開頭空白節點的環狀串列、或雙向串列在搜尋、新增(至某節點後)、刪除... 皆有相同的時間複雜度(即令處理的細節互有所異)；唯在邊界條件 (first?=NULL、head?=NULL、...)判定時，含開頭空白節點的環狀串列可省下檢測是否為空串列的考量。
:::
---
### 14. 設計一種串列表示法可以在串列兩頭做刪除與插入的動作，這種結構稱為「雙向佇列」 (deque) ，寫一個自兩端做插入動作的程序。請分別考慮： <br>   (a) 單向鏈結串列（含或不含開頭空節點）； <br>   (b) 單向環狀鏈結串列； <br>   (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 | 本題 |
| :------: | :------: |
|  |  |
宣告如下：
```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
--- */
時間複雜度：$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
--- */
時間複雜度：$O(nm + pq)$，其中 $n$ 是稀疏矩陣 $A$ 中非零元素的數量，$m$ 是稀疏矩陣 $B$ 中非零元素的數量，$p$ 是稀疏矩陣 $A$ 中的行數，$q$ 是稀疏矩陣 $B$ 中的列數 。
:::
---
Sign in with Wallet
Connect another wallet