高等演算法第 1 次作業

1

Recall the recursive program (discussed in the class) that computes the n-th Fibonacci number. Compute the exact number of additions used by the program.

令

$T(n)$ 為計算第 n 個費氏數所需的加法次數，則根據遞迴公式可得

$T(n)=T(n-1)+T(n-2)+1,T(1)=0,T(2)=0,T(3)=1$

$T(n)=T(n-1)+T(n-2)+1\le 2T(n-1)+1$

$$\begin{array}{rl}T(n)& \le 2T(n-1)+1\\ & =2[2T(n-2)+1]+1\\ & =2^{2}T(n-2)+2+1\\ & =2^2[2T(n-3)+1]+2+1\\ & =2^{3}T(n-3)+2^2+2+1=...\\ & =2^{k}T(n-k)+2^{k-1}+2^{k-2}+...+2^2+2+1=2^{k}T(n-k)+{\displaystyle \frac{1-2^k}{1-2}}\\ & =2^{k}T(n-k)+2^k-1(letn-k=1)\\ & =2^{n-1}T(1)+2^{n-1}-1=2^{n-1}-1=O(2^n)\end{array}$$
故

$T(n)\in O(2^n)$

2

Given a tree T and k subtrees of T such that each pair of subtrees has at least one vertex in common, prove that there is at least one vertex in common to all the subtrees.

Helly property : A family

$\{A_i:i\in I\}$ of subsets of a set A is said to satisfiy the Helly property if

$J\subseteq I$, and

$A_i\cap A_j\ne \varnothing$, for every

$i,j\in J$, then

$\bigcap _{j\in J}{A}_j\ne \varnothing$.
Theorem : A family of subtrees of a tree satisfies the Helly property 一棵樹的所有子樹皆滿足 Helly property

Proof:
令 A 收集的是樹 T 的所有子樹，

$A=\{T_i:i\in I=\{1,2,...,n\}\}$。假設對所有的

$i,j\in J=\{1,2,...,k\}\subseteq I,T_i\cap T_j\ne \varnothing$，我們需要證明出

$\bigcap _{j\in J}{T}_j\ne \varnothing$。
若有一棵子樹

$T_i\in A,i\in J$ 只有一個點

$v$，則明顯可證出

$\bigcap _{j\in J}{T}_j=\{v\}$。所以假設每個子樹

$T_i\in A,i\in J$ 至少有兩個節點。

我們對子樹的節點數進行歸納法。假設樹 T 有 n 個節點，每個子樹最多有 n 個節點，且滿足 Helly property。
當 T 為 n + 1 個節點的樹時，
令

$v_0$ 為 T 的樹葉節點且其唯一的鄰點為

$u$。
令

$T_i^{\prime }=T_i-v_0，i\in J$ 且

$T^{\prime }=T-v_0$ 為 n 個節點的樹。
(

$T_i^{\prime }$ 為 T 的子樹去除

$v_0$，所以最多有 n 個節點)

根據歸納假設，

$T^{\prime }$ 滿足 Helly Property。

1. 若
   $T_i\mathrm{和}{T}_j$ 有一共同點
   $x(\ne v_0)$，則
   $T_i^{\prime }\mathrm{和}{T}_j^{\prime }$ 一定也有一共同點
   $x$。
2. 若
   $T_i\mathrm{和}{T}_j$ 有一共同點
   $v_0$，則
   $T_i\mathrm{和}{T}_j$ 一定還有一共同點
   $u_0$，因為前面有假設子樹最少兩個節點，所以如果
   $v_0$ 在裡面，
   $u_0$ 勢必也一定會在裡面，不然其中一個子樹只有一個節點
   $v_0$ 會矛盾。
   
   $\Rightarrow$
   $T_i^{\prime }\mathrm{和}{T}_j^{\prime }$ 有一個共同點
   $u_0$

由 (1)(2) 根據歸納假設，因為

$T_i^{\prime }\cap T_j^{\prime }\ne \varnothing ,$，則

$\bigcap _{j\in J}{T}_j^{\prime }\ne \varnothing$，也因此每個

$T_j^{\prime }$ 再加入

$v_0$ 得到

$\bigcap _{j\in J}{T}_j\ne \varnothing$。所以當 T 的節點數為 n + 1時命題亦成立，故由數學歸納法可得證。

3

The lattice points in the plane are the points with integer coordinate. Consider a polygon that all of its vertices are lattice points. Let p be the number of lattice points that are on the boundary of the polygon, and let q be the number of lattice points that are inside the polygon. Prove that the area of the polygon is p/2+q-1.

定義小三角形為內部沒有任何 Lattice Points 的三角形。
欲計算任意簡單多邊形面積，可先將一多邊形分割成許多個小三角形，每個小三角形的面積為

$\frac{1}{2}$。找出一個多邊形可以分割成多少個的小三角形，最後再乘上

$\frac{1}{2}$ 就是多邊形面積了。

令 r 為平面圖上的區域數，則多邊形內部有 r - 1 個區域，會減去 1 是代表扣掉多邊形外面的區域。
又

$2e=3(r-1)+e_b$，其中

$e_b$ 為多邊形外圍 (Boundary) 的邊數。

$\Rightarrow r=2(e-r)-e_b+3$，又根據尤拉公式 v - e + r = 2

$\Rightarrow e-r=v-2$

$\Rightarrow r=2(v-2)-e_b+3=2v-e_b-1$ 又

$v=p+q$ 且

$e_b=p$ ( 想一下邊界邊數與多邊形外圍的點數即可知)

$\Rightarrow r=2(p+q)-p-1=p+2q-1$

$\Rightarrow \mathrm{多}\mathrm{邊}\mathrm{形}\mathrm{面}\mathrm{積}=\mathrm{內}\mathrm{部}\mathrm{小}\mathrm{三}\mathrm{角}\mathrm{形}\mathrm{數}\times \frac{1}{2}=\frac{r-1}{2}=\frac{p+2q-2}{2}=\frac{p}{2}+q-1$，得證。

4

Given a positive integer n, find a way to partition n into one or more positive integers j1, j2, … , jk (i.e. j1 + j2 + … + jk = n) such that the product of these integers is maximized. Prove the correctness of your formula.

如果一個數拆成兩個數字相加，要使這兩個數字的乘積最大，則這兩個數字一定相等。同理，將數字 n 要拆成多個等份的 x 相加，即 x + x + … + x = n，則乘積最大值為

$x^{\frac{x}{n}}$。

令

$f=x^{\frac{x}{n}}$，利用微分求出極值，得出當 x = e 時 f 會有最大值。因為 2 < e < 3，所以將一個數字拆成 2 和 3 的線性組合時，這些

$j_i$ 的乘積會最大。

另外，6 = 3 + 3 = 2 + 2 + 2，但 3 * 3 > 2 + 2 + 2，所以每拆出三個 2 可以用二個 3 去替換。因此在分割 n 時，

$j_i$ 會以 3 為主。

首先，將 n mod 3 找出餘數是多少 :
若餘數為 0，則最大值為

$3^{\frac{n}{3}}$。
若餘數為 1，將 1 和最後一個 3 組合成 4，並把 4 拆成 2, 2，因為

$3\ast 1<2\ast 2$，得到最大值為

$3^{\lfloor \frac{n}{3}\rfloor -1}\ast 2\ast 2$
若餘數為 2，則最大值為

$3^{\lfloor \frac{n}{3}\rfloor }\ast 2$

5

Let a1, a2, … , an be positive real numbers such that a1 x a2 x … x an = 1. Prove, without using the arithmetic versus geometric inequality, that
(1+a1)(1+a2) x … x (1+an) ≥ 2^n.

當 n = 1，

$a_1=1，\mathrm{則}1+a_1\ge 2$ 成立。
假設 n = k 時命題成立 : 若

$a_1\cdot a_2\cdot \cdot \cdot a_k=1$，則

$(1+a_1)(1+a_2)\cdot \cdot \cdot (1+a_k)\ge 2^k$
當 n = k + 1 時，若

$a_1\cdot a_2\cdot a_3\cdot \cdot \cdot a_{k+1}=1$，則

$(1+a_1)(1+a_2)\cdot \cdot \cdot (1+a_k)(1+a_{k+1})\ge 2^k(1+a_{k+1})=2^k+2^k{a}_{k+1}$ 又根據歸納假設

$a_{k+1}=\frac{1}{a_1\cdot a_2\cdot \cdot \cdot a_k}=\frac{1}{1}=1$，故

$(1+a_1)(1+a_2)\cdot \cdot \cdot (1+a_k)(1+a_{k+1})\ge 2^{k+1}$ 命題亦成立。
因此由數學歸納法可得證。

6

Given n ≥ 1 numbers x1, x2, …, xn, show that the function f(x) = Σ |x - xi| for i = 1 to n takes its minimum value at the median of these n number.

解法一 :
想像

$x_1,x_2,...,x_n$ 座落在 x 軸上，且

$x_1\le x_2\le ...\le x_n$，而你站在 x 點，位於所有

$x_i$ 的最左邊，即

$x<x_1$。

假設 n = 7，你現在要開始往右邊旅行，去拜訪每個

$x_i$。每次前進你會往右 d 單位距離，此時你會距離每個

$x_i$ 更靠近 d 距離，所以距離總和 f(x) 會減少 7d。直到你抵達

$x_1$ 時，和

$x_1$ 之間的距離為 0，與

$x_2\sim x_7$ 之間的距離總和會減少 6d。再往右走 d 距離，你和

$x_1$ 的距離會增加 d，而與

$x_2\sim x_7$ 之間的距離總和會減少 6d，總共減少 5d。

你繼續往右走抵達

$x_2$ 時，你與

$x_1$ 的距離會增加 d，與

$x_2$ 的距離會為 0，與

$x_3\sim x_7$ 之間的距離總和會減少 5d，總距離和會再減少 4d。
同理，抵達

$x_3$ 時，你與

$x_1\sim x_2$ 的距離會增加 2d，與

$x_3$ 的距離會為 0，與

$x_4\sim x_7$ 之間的距離總和會減少 4d，總距離和會再減少 2d。
抵達

$x_4$ 時，你與

$x_1\sim x_3$ 的距離會增加 3d，與

$x_4$ 的距離會為 0，與

$x_5\sim x_7$ 之間的距離總和會減少 3d，總距離沒有減少也沒有增加。
抵達

$x_5$ 時，你與

$x_1\sim x_4$ 的距離會增加 4d，與

$x_5$ 的距離會為 0，與

$x_6\sim x_7$ 之間的距離總和會減少 2d，總距離會增加 2d。
抵達

$x_6$ 時，你與

$x_1\sim x_5$ 的距離總和會增加 5d，與

$x_6$ 的距離會為 0，與

$x_7$ 之間的距離總和會減少 d，總距離會增加 4d。
抵達

$x_7$ 時，你與

$x_1\sim x_6$ 的距離會增加 6d，與

$x_7$ 的距離會為 0，總距離會增加 2d。
抵達

$x>x_7$ 時，你與

$x_1\sim x_7$ 的距離會增加 7d，總距離會增加 7d。

由上述可觀察出，當你從最左端往右前進，距離總和 f(x) 會一直遞減，直到遇到中位數

$x_4$ 時 f(x) 達到最小值。當從中位數繼續往右走，距離總和又會開始慢慢遞增。因此當 x 為中位數時，f(x) 會有最小值。

解法二 :
令

$M$ 為

$x_i$ 的中位數，並將

$x_i$ 作排序，

$x_1\le x_2\le \cdots \le x_s\le A\le x_{s+1}\le \cdots \le x_t\le M\le x_{t+1}\le \cdots \le x_n$

考慮

$n$ 為偶數，

$n=2t,t\in N$，且

$A\le M$，則

$$\begin{array}{rl}f(A)& =\sum _{i=1}^s(A-x_i)+\sum _{i=s+1}^n(x_i-A)\\ & =[\sum _{i=1}^t(A-M+M-x_i)-\sum _{i=s+1}^t(A-x_i)]+[\sum _{i=s+1}^t(x_i-A)+\sum _{i=t+1}^n(x_i-M+M-A)]\\ & =\sum _{i=1}^t(M-x_i)+t(A-M)+\sum _{i=s+1}^t(x_i-A)+\sum _{i=s+1}^t(x_i-A)+\sum _{i=t+1}^n(x_i-M)+(n-t)(M-A)\\ & =\sum _{i=1}^t(M-x_i)+\sum _{i=t+1}^n(x_i-M)+2\sum _{i=s+1}^t(x_i-A)+(n-2t)(M-A)\end{array}$$

可看出前兩項都會大於等於零，且最後一項等於零 (因為

$n=2t$)，故當

$A=M$ 時，

$2\sum _{i=s+1}^t(x_i-A)<0$，

$f(A)$ 會有最小值。

考慮

$n$ 為奇數，且

$A\le M=x_t$，

$n=2t-1,t\in N$，

$x_1\le x_2\le \cdots \le x_s\le A\le x_{s+1}\le \cdots \le x_t=M\le x_{t+1}\le \cdots \le x_n$，則

$$\begin{array}{rl}f(A)& =\sum _{i=1}^s(A-x_i)+\sum _{i=s+1}^n(x_i-A)\\ & =[\sum _{i=1}^t(A-M+M-x_i)-\sum _{i=s+1}^t(A-x_i)]+[\sum _{i=s+1}^t(x_i-A)+\sum _{i=t+1}^n(x_i-M+M-A)]\\ & =\sum _{i=1}^t(M-x_i)+t(A-M)+\sum _{i=t+1}^n(x_i-M)+(n-t)(M-A)+2\sum _{i=s+1}^t(x_i-A)\\ & =\sum _{i=1}^t(M-x_i)+\sum _{i=t+1}^n(x_i-M)+2\sum _{i=s+1}^t(x_i-A)+(n-2t)(M-A)\\ & =\sum _{i=1}^t(M-x_i)+\sum _{i=t+1}^n(x_i-M)+2\sum _{i=s+1}^{t-1}(x_i-A)+2(x_t-A)-(M-A)\\ & =\sum _{i=1}^t(M-x_i)+\sum _{i=t+1}^n(x_i-M)+2\sum _{i=s+1}^{t-1}(x_i-A)+(M-A)\end{array}$$
可看出前兩項都會大於等於零，故當

$A=M$ 時，

$2\sum _{i=s+1}^{t-1}(x_i-A)+(M-A)<0$，

$f(A)$ 會有最小值。

同理，當

$A\ge M$ 亦成立。故取中位數代入 f(x) 為最小值。

7

Given a set of n +1 numbers out of the first 2n natural numbers 1, 2, …, 2n, prove by mathematic induction that here are two numbers in the set, one of which divides the other.

當 n = 1 時，取 1 和 2，1 | 2，命題成立
假設當

$n=k\ge 1$ 命題成立，即從 1, 2, …, 2k 中選 k + 1 個數字，必存在兩個數為倍數關係。
當

$n=k+1$ 時，要從 1, 2, …, 2k + 2 中選 k + 2 個數字，有以下三種情況。

1. 這 k + 2 個數皆小於等於 2k，代表從前 2k 個數字中選出 k + 2 個數字，根據歸納假設，從前 2k 個數中選出 k + 1 個數，必存在兩個數，其中一數可以整除另外一數。因此，這 k + 2 個數中也存在兩數為倍數關係。
2. 在這 k + 2 個數中，選了一數大於 2k，而剩下 k + 1 個數字小於等於 2k。根據歸納假設，這 k + 1 個數是從前 2k 個數字中選出來的，必存在兩數，其中一數可以整除另一數。因此，這 k + 2 個數中也存在兩數為倍數關係。
3. 在這 k + 2 個數中，選了二數大於 2k，即選了 2k + 1 和 2k + 2，而剩下 k 個數字小於等於 2k。
   a. 若這 k 個數當中有選 k + 1，則 (k + 1) | (2k + 2)，命題成立。
   b. 若這 k 個數當中沒有選 k + 1 :
   令解集合 A 收集的是選了 2k + 1 和 2k + 2 但沒有選 k + 1 的解。
   現在考慮一個新的解集合 B，我們暫時地不選 2k + 2，選了 2k + 1 和 k + 1，則可以套用 Case 2，因為 2k + 1 大於 2k，且能從 1 ~ 2k 中選 k + 1 個數字，所以存在兩數 a, b 使得 a | b。如果 a 和 b 皆不等於 k + 1，則此解一定也會在 A 中，故命題成立。如果 a 或 b 等於 k + 1，假設 b = k + 1，則 a | (k + 1)，在解集合 A 中，a 一定會整除 2k + 2，因為 (k + 1) | (2k + 2)，所以 a | (2k + 2)，故命題亦成立。

因此由數學歸納法可得證。

8

Let d1, d2, …, dn, n ≥ 2, be positive integers. Prove that if d1 + d2 + … + dn= 2n - 2, then there exists a tree with n vertices of degrees exactly d1, d2, …, dn. Based on your proof, design an efficient algorithm to construct such a tree.

當 n = 2 時，若

$d_1+d_2=2\ast 2-2=2$，則存在一棵樹的度數序列為

$d_1=d_2=1$，即兩點連成一線，故命題成立。
假設

$n=k\ge 2$ 時命題成立，則當

$n=k+1$ 時，若

$d_1+d_2+...+d_{k+1}=2(k+1)-2=2k$，且將這個 k+1 個數字由大到小使得

$d_1\ge d_2\ge ...\ge d_{k+1}$，其中須滿足

1. $d_1\ge 2$，因為若
   $d_1=1$ 則
   $d_1=d_2=...=d_{k+1}=1$，
   $d_1+d_2+...+d_{k+1}=k+1\ne 2k$，矛盾。所以
   $d_1$ 必須大於 1。
2. 所有
   $d_i$ 不可能全都大於等於 2，因為若
   $d_i\ge 2fori=1\sim k+1$，則
   $d_1+d_2+...+d_{k+1}\ge 2(k+1)\ne 2k$，矛盾。故至少兩個數字為 1，假設取
   $d_k=d_{k+1}=1$，這樣才不會和前提矛盾。

現在考慮此序列

$(d_1-1),d_2,d_3,...,d_k$，由歸納假設可知若

$(d_1-1)+d_2+d_3+...+d_k=2k-2$，則存在一樹 T 的度數序列為

$(d_1-1),d_2,d_3,...,d_k$。

$\Rightarrow deg(v_1)=d_1-1,deg(v_i)=d_{i}fori=2\sim k$
考慮加入一點

$v_{k+1}$，和

$v_1$ 連接，形成一棵有 k + 1 個節點的樹 T'，則

$deg(v_1)=(d_1-1)+1=d_1,deg(v_i)=d_{i}fori=2\sim k,deg(v_{k+1})=1=d_{k+1}$，因此存在一樹 T' 的度數序列為

$d_1,d_2,d_3,...,d_{k+1}$，命題成立。
由數學歸納法可得證。

Algo
定義 adj[n][n] 為儲存樹的 n * n Adjacency matrix。

Input : d1, d2, ..., dn
Output : construct a tree if there exists a tree with the given degree sequence

if d1 + d2 + … + dn = 2n - 2
    for i = 1 to n
        for j = i + 1 to n
            if(di == 0) break // 邊數已經建完後面節點就不用管了
            if(dj == 0) continue // 點 j 不能再加入邊了
            adj[i][j] = adj[j][i] = 1
            di = di - 1
            dj = dj - 1     
    return adj[][]
else return "There is no such a tree"

Time :

$O(n^2)$

9

Let G=(V, E) be a directed graph (not necessarily acyclic). Design an efficient algorithm to label the vertices of the graph with distinct labels from 1 to |V| such that the label of each vertex v is greater than the label of at least one of v’s predecessors, or determine that no such labeling is possible. (A predecessor of v is a vertex w such that wv in E.)

想法 : 找到 indegree = 0 的點，並從該點當作起點，利用 DFS 走訪整張圖，每拜訪一個點就為該點設編號。拜訪第一個點設 1 號，拜訪第二個點設 2 號，依此類推。當發現此圖有迴圈時，則不存在此種編號方式。DFS 走訪完後，檢查每個點是否都有拜訪過，如果有點沒被拜訪過代表此圖不連通，亦不存在此種編號方式。

時間 :

$O(V+E)$，DFS 走訪整張圖的時間。

10

Give a linear-time algorithm that takes as input a tree and determines whether it has a perfect matching: a set of edges that touches each node exactly once.

想法 : 給定一樹 T，從樹葉節點 L 開始配對，因為樹葉節點的分支度為 1，所以若要配對一定得和其父節點 P 組成一對。組好一對 (L, P) 後，將樹葉節點 L 和其父節點 P 從樹中刪除。接著再繼續找下一個樹葉節點進行上述動作，直到樹 T 為空，代表此樹有 Perfect Matching。如果過程中發現樹 T 有度數為 0 的節點代表該點已經孤立了，則此樹就不會有 Perfect Matching。

演算法 :

定義一邊集合 M = ∅，收集每組配對 (i, j) 的邊
while |T|≠ ∅
    若 T 有一節點 L 的度數為 0，回傳 "No matching"
    否則，找一樹葉節點 L
         令 p 為 L 的鄰點
         將邊 (p, L) 加入邊集合 M
         從樹 T 中刪除節點 p 和 L (兩點的鄰邊也一同刪除)
回傳 M

時間分析 : 一個一個刪掉樹葉節點和其鄰點，基本上就是遍歷一整棵樹，所以時間為線性時間。

11

Consider a variation of the towers of Hanoi. We no longer assume that all the disks are initially on one peg. They may be arbitrarily distributed among the three pegs, as long as they are ordered in decreasing sizes on each peg. The purpose remains to move all disks to one specified peg, under the same constraints as the original problem, with as few moves as possible. Design an algorithm to compute the minimal number of moves. How about the reverse of the problem?

想法 : 從最大的盤子開始思考要怎麼移動到目標柱。

令三個柱子分別為 A, B, C，總共有 n 個盤子。假設第 n 個盤子位於柱子 X，目標柱為 C。

定義 f(n, target) 為變化版河內塔，將 n 個散落於三個柱子的盤子全部移動到目標柱 target 上。
定義 g(n, P, target) 為原始版河內塔，將 n 個盤子全部移動到目標柱 target 上，過程中透過柱子 P 輔助。

1. 若第 n 個盤子位於柱子 C，則不需移動，所以現在問題縮小，只需考慮移動前 n - 1 個盤子，即解 f(n-1, C)。
2. 若第 n 個盤子不在柱子 C，則要將前 n - 1 個盤子移動到不是目標柱 C 也不是柱子 X 的柱子 Y 上，此時問題縮小成將 n - 1 個盤子移到柱子 Y 上，即 f(n-1, Y)。移動完之後再將第 n 個盤子搬到柱子 C，然後剩下 n - 1 個盤子再從柱子 Y 移動到柱子 C，此時問題轉為原始河內塔版本，即 g(n-1, X, C)。

12

Let T be an undirected tree. The diameter of T is the maximal distance over all pairs of vertices. Design an algorithm to find the diameter of the given tree.

(回學校再補)

13

UVa 146 ID Codes

想法 : 從最低位逐一往最高位檢查順序，要找下一個排列需盡可能增加越少越好。如果目前排序為遞增就沒辦法讓此字串變大；如果遇到某數 x 開始遞減，就從最低位開始和某數 x 進行比大小，找到比 x 大的數字 y，接著交換 x 和 y 的位置，最後將最低位到 x 的前一位由小到大擺放，則此數即為下一個排列。若一個排列從最低到最高位為遞增代表此數沒有下一個排列了。

14

Consider the iterative method for solving the towers of Hanoi problem described in Unit 2. Prove the correctness of the algorithm

while (1) {
    將最小的盤子移動到下一個柱子 (順時鐘順序)
    若所有盤子都堆在同一根柱子，即完成
    最小盤不動，移動唯一可以移動的盤子
}

將上述迴圈版的演算法對於偶數的盤子成立，但奇數個盤子不成立，問題出在於將最小盤移動到下一個柱子的方式，奇數盤應該要移動到下二個柱子。所以將此演算法更精確地描述如下 :
令起始柱為 A，目標柱為 C，輔助柱為 B。

假設目前位於柱子 i，
當有奇數個盤子，下一個柱子會跳到 (i + 2) mod 3 的位置；
當有偶數個盤子，下一個柱子會跳到 (i + 1) mod 3 的位置；

當 n 為奇數，

1. 在 A 和 C 之間合法移動一個盤子
2. 若所有盤子都在目標柱 C，即完成
3. 在 A 和 B 之間合法移動一個盤子
4. 在 B 和 C 之間合法移動一個盤子
5. 重複上述直到完成

當 n 為偶數，

1. 在 A 和 B 之間合法移動一個盤子
2. 在 A 和 C 之間合法移動一個盤子
3. 在 B 和 C 之間合法移動一個盤子
4. 若所有盤子都在目標柱 C，即完成
5. 重複上述直到完成