《算法导论》部分习题解答

做着玩玩，就当颓废了（ 以下的解答是自己写的，就当作业本了，不一定对。[这里](https://walkccc.me/CLRS/)有除了附录以外的全部答案。 ## 附录 A 求和 先补补数学 ### A. 1 1. $$ \sum\limits_{k=1}^n (2k-1)=2\sum\limits_{k=1}^n k -n=n(n+1)-n=n^2 $$ 2. $$ \sum_{k=1}^n \dfrac{1}{2k-1}=\sum_{k=1}^n(\dfrac{1}{2k}-\dfrac{1}{2k(2k-1)})=\frac{1}{2}\ln n+\mathcal O(1) -\sum_{k=1}^n (\dfrac{1}{2k-1}-\dfrac{1}{2k}) $$ 注意到后面那个和式显然大于 $0$，而： $$ 0<\sum_{k=1}^n (\dfrac{1}{2k-1}-\dfrac{1}{2k})\le\sum_{k=2}^{2n}(\dfrac{1}{k-1}-\dfrac{1}{k})=1-\dfrac{1}{2n}=\mathcal O(1) $$ 故 $\sum\limits_{k=1}^n (\dfrac{1}{2k-1}-\dfrac{1}{2k})=\mathcal O(1)$。由 $\dfrac{1}{2}\ln n=\ln \sqrt{n}$， $$ \sum_{k=1}^n \dfrac{1}{2k-1}=\ln \sqrt{n}+\mathcal O(1) $$ 3. （以下均有 $|x|<1$）由 $$ \sum_{k=0}^{\infty}kx^k=\dfrac{x}{(1-x)^2} $$ 两边分别求导可得 $$ \sum_{k=0}^{\infty}k^2x^{k-1}=\dfrac{1+x}{(1-x)^3} $$ 那么 $$ \sum_{k=0}^{\infty}k^2x^k=\dfrac{x(1+x)}{(1-x)^3} $$ 4. $$ \sum_{k=0}^{\infty}\dfrac{k-1}{2^k}=\sum_{k=0}^{\infty}k(\dfrac{1}{2})^k-\sum_{k=0}^{\infty}\dfrac{1}{2^k}=\dfrac{\frac{1}{2}}{(1-\frac{1}{2})^2}-2=0 $$ 5. $|x|<1$ 时， $$ \sum_{k=1}^{\infty}(2k+1)x^{2k}=\sum_{k=1}^{\infty}2kx^{2k}+\sum_{k=1}^{\infty}x^{2k} $$ 令 $x^2=t$，易见 $|t|<1$，有 $$ \text{原式}=2\sum_{k=1}^\infty kt^k+\sum_{k=1}^\infty t^k=\dfrac{2t}{(1-t)^2}+\dfrac{1}{1-t}=\dfrac{t+1}{(t-1)^2}=\dfrac{x^2+1}{x^4-2x^2+1} $$ 6. 我们知道 $$ \mathcal O(f(n))+\mathcal O(g(n))=\mathcal O(f(n)+g(n)) $$ 那么原式显然。（也可以用定义代入证明，不过细节多得要死） 7. 设 $$ \text{原式}=\prod_{k=1}^n2\cdot 4^k=\prod_{k=1}^n2^{2k+1}=S $$ 则 $$ \log_2 S=\sum_{k=1}^n 2k+1=n^2+2n $$ 故 $\text{原式}=2^{n^2+2n}$。 8. $$ \prod_{k=2}^n(1-\dfrac{1}{k^2})=\prod_{k=2}^n\dfrac{k^2-1}{k^2}=\prod_{k=2}^n\dfrac{k-1}{k}\times\dfrac{k+1}{k}=\dfrac{1}{2}\times\dfrac{n+1}{n}=\dfrac{n+1}{2n} $$ ### A. 2 1. $$ \sum_{k=1}^n\dfrac{1}{k^2}=1+\sum_{k=2}^n\dfrac{1}{k^2}\le1+\sum_{k=2}^n\dfrac{1}{k(k-1)}=1+\sum_{k=2}^n(\dfrac{1}{k-1}-\dfrac{1}{k})=1+1-\dfrac{1}{n}\le 2 $$ 故 $\sum\limits_{k=1}^n\dfrac{1}{k^2}=\mathcal O(1)$。 2. $$ \sum_{k=0}^{\left\lfloor\lg n\right\rfloor} \left\lceil \dfrac{n}{2^k} \right\rceil \le \sum_{k=0}^{\left\lfloor\lg n\right\rfloor} (\left\lfloor \dfrac{n}{2^k} \right\rfloor+1)\le n\sum_{k=0}^{\left\lfloor\lg n\right\rfloor} \dfrac{1}{2^k} + \left\lfloor\lg n\right\rfloor\le n\sum_{k=0}^{\infty} \dfrac{1}{2^k} + \lg n=2n+\lg n=\mathcal O(n) $$ 3. 我们参考书中对 $H_n$ 上界的证明，把下标从 $1$ 到 $n$ 划分为 $1+\left\lfloor\log_2 n\right\rfloor$ 段，第 $i$ 段的范围为 $[2^i,2^{i+1})$（其中 $0\le i\le \left\lfloor\log_2 n\right\rfloor$）。那么： $$ H_n=\sum_{k=1}^n\dfrac{1}{k}=\sum_{i=0}^{\left\lfloor\log_2 n\right\rfloor}\sum_{k=1}^{2^i}\dfrac{1}{2^i-k}\ge\sum_{i=0}^{\left\lfloor\log_2 n\right\rfloor}\sum_{k=1}^{2^i}\dfrac{1}{2^i}=\sum_{i=0}^{\left\lfloor\log_2 n\right\rfloor}1=\left\lfloor\log_2 n\right\rfloor $$ 故 $H_n=\Omega(\log n)$。 4. 易证 $y=x^3$ 在 $\mathbb R$ 上单调递增，有： $$ \sum_{k=1}^n k^3\le\int_{1}^{n+1} x^3\text{d}x=\left.\dfrac{1}{4}x^4\right|_1^{n+1}=\dfrac{(n+1)^4-1}{4} $$ 另一方面， $$ \sum_{k=1}^n k^3\ge\int_{0}^{n} x^3dx=\dfrac{n^4}{4} $$ 故 $\dfrac{n^4}{4}\le\sum_{k=1}^n k^3\le\dfrac{(n+1)^4-1}{4}$。 5. 因为如果直接积分近似，会得到： $$ \sum_{k=1}^n \dfrac{1}{k}\le \int_{0}^{n}\dfrac{\text{d}x}{x} $$ 然后我们知道： $$ \lim_{x\to 0} \int_{x}^n\dfrac{\text{d}x}{x}=\infty $$ 因此直接积分啥都得不到。 ### 思考题 **A - 1.**（确定和的界） ~~这三个结论还是十分常用的~~ > 以下 $r,s\ge 0$，均为常数。 - **a.** $\sum_{k=1}^n k^r=\Theta(n^{r+1})$. 对上界，我们有： $$ \sum_{k=1}^n k^r\le \sum_{k=1}^n n^r=n^{r+1} $$ 对下界，我们有： $$ \sum_{k=1}^n k^r=\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor} k^r+\sum_{k=\left\lfloor\frac{n}{2}\right\rfloor+1}^n k^r\ge 0+\sum_{k=\left\lfloor\frac{n}{2}\right\rfloor+1}^n (\dfrac{n}{2})^r=\dfrac{n^{r+1}}{2^{r+1}} $$ 故有 $\sum_{k=1}^n k^r=\Theta(n^{r+1})$ 成立。 - **b.** $\sum_{k=1}^n \log^s k=\Theta(n\log^s n)$. 对上界，我们有： $$ \sum_{k=1}^n \log^s k\le \sum_{k=1}^n \log^s n=n\log^s n $$ 对下界，我们有： $$ \sum_{k=1}^n \log^s k=\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor} \log^s k+\sum_{k=\left\lfloor\frac{n}{2}\right\rfloor+1}^n \log^s k\ge 0+\sum_{k=\left\lfloor\frac{n}{2}\right\rfloor+1}^n \log^s \dfrac{n}{2}=\Omega(n\log^s n) $$ 故有 $\sum_{k=1}^n \log^s k=\Theta(n\log^s n)$ 成立。 - **c.** $\sum_{k=1}^n k^r\log^s k=\Theta(n^{r+1}\log^s n)$ 对上界，我们有： $$ \sum_{k=1}^n k^r\log^s k\le \sum_{k=1}^n n^r\log^s n=n^{r+1}\log^s n $$ 对下界，我们有： $$ \sum_{k=1}^n k^r\log^s k=\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor} k^r\log^s k+\sum_{k=\left\lfloor\frac{n}{2}\right\rfloor+1}^n k^r\log^s k\ge 0+\sum_{k=\left\lfloor\frac{n}{2}\right\rfloor+1}^n (\dfrac{n}{2})^r\log^s \dfrac{n}{2}=\dfrac{n^{r+1}}{2^{r+1}}\log^s\dfrac{n}{2}=\Omega(n^{r+1}\log^s n) $$ 故有 $\sum_{k=1}^n k^r\log^s k=\Theta(n^{r+1}\log^s n)$ 成立。 ## 附录 B 集合等离散数学内容 ### B.1 1. 题不难，懒得画图了。 2. 考虑数学归纳法。对第一个命题，$n=2$ 时，直接应用德 · 摩根定律。现在假设 $n=k$ 时，有： $$ \overline{\bigcap_{i=1}^k A_i}=\bigcup_{i=1}^k \overline{A_i} $$ 成立，那么 $n=k+1$ 时： $$ \overline{\bigcap_{i=1}^k A_i}=\overline{\bigcup_{i=1}^k \overline{A_i}\cap A_{k+1}}=\bigcup_{i=1}^k \overline{A_i}\cup \overline{A_{k+1}}=\bigcup_{i=1}^{k+1} \overline{A_i} $$ 第二个命题同理。 3. 考虑数学归纳法。$n=2$ 时，直接应用等式 (B.3)。现在假设 $n=k$ 时，有： $$ \left|\bigcup_{i=1}^k A_i\right| = \sum_{i=1}^k \sum_{(p_1,p_2,\cdots,p_i)}\left|\bigcap_{t=1}^i A_{p_t}\right| $$ 成立（其中 $(p_1,p_2,\cdots,p_i)$ 表示无序列表，设 $p_1\le p_2\le \cdots \le p_k$），那么 $n=k+1$ 时： $$ \left|\bigcup_{i=1}^{k+1} A_i\right| = \left(\sum_{i=1}^k \sum_{(p_1,p_2,\cdots,p_i)}\left|\bigcap_{t=1}^i A_{p_t}\right|\right) + \left|A_{k+1}\right| + \left|\left(\bigcup_{i=1}^k A_i\right)\bigcap A_{k+1}\right| $$ 还是用归纳法推广一下分配律，就可以把后面那坨东西化开： $$ \left|A_{k+1}\right| + \left|\left(\bigcup_{i=1}^k A_i\right)\bigcap A_{k+1}\right| = \left|A_{k+1}\right|+ \left|\bigcup_{i=1}^k A_{i}\cap A_{k+1}\right| =\sum_{i=0}^k \sum_{(p_1,p_2,\cdots,p_i)}\left|\left(\bigcap_{t=1}^i A_{p_t}\right)\bigcap A_{k+1}\right| = \sum_{i=0}^k \sum_{(p_1,p_2,\cdots,p_i,p_{k+1})}\left|\left(\bigcap_{t=1}^i A_{p_t}\right)\bigcap A_{k+1}\right| $$ 然后把这个东西合并一下能得到： $$ \left|\bigcup_{i=1}^{k+1} A_i\right| = \sum_{i=1}^{k+1} \sum_{(p_1,p_2,\cdots,p_i)}\left|\bigcap_{t=1}^i A_{p_t}\right| $$ 这就证完了。 4. 我们写出奇自然数集合的形式 $\mathrm{Odd}=\{2k+1 | k\in \mathbb N\}$，易证每个 $k$ 恰好对应一个元素，因此它与自然数集合一一对应。 5. 考虑有集合 $S^\prime = S\cup\{x\}(x\notin S)$。我们考虑是否选择 $x$，有： $$ 2^{S^\prime} =2^S\cup\{c\cup x|c\in 2^S\} $$ 然后可以归纳证明方案数是 $2^{|S|}$。 ### B.2 这部分看着脑子已经不太够了 1. - 自反性：$\forall A\sube \mathbb Z$，有 $A\sube A$，这由定义显然。 - 反对称性：$\forall A,B\sube \mathbb Z$，有 $A\sube B,B\sube A\Rightarrow A=B$，这由定义显然。 - 传递性：$\forall A,B,C\sube \mathbb Z$，有 $A\sube B,B\sube C\Rightarrow A\sube C$，这由定义显然。 因此 $\sube$ 是一个偏序关系。 - 但是取 $A=\{1\}$，$B=\{2\}$，$A\sube B$ 和 $B\sube A$ 均不成立。 所以 $\sube$ 不是全序关系。 2. - 自反性：$\forall x\in \mathbb N^+$，$x\equiv x\pmod{n}$，显然。 - 对称性：$\forall x,y\in \mathbb N^+$，$x\equiv y\pmod{n}\Rightarrow y\equiv x\pmod{n}$。 证明：取 $x-y=qn$，则 $y-x=-qn$。 - 传递性：$\forall x,y,z\in \mathbb N^+$，$x\equiv y\pmod{n}, y\equiv z\pmod{n}\Rightarrow x\equiv z\pmod{n}$。 证明：取 $x-y=pn,y-z=qn$，则 $x-z=(p+q)n$。 所以模 $n$ 同余构成了一个等价类。 划分为模 $n$ 意义下的 $n$ 个完全剩余系。 3. **a.** 考虑关系 $R=\{(a,b):a,b\in \mathbb N^+,a\&b\ne 0\}$（ $\&$ 表示按位与）。 **b.** 考虑在 $\mathbb R^2$ 上的 $\geq$。 **c.** 考虑关系 $R=\varnothing$。 4. 考虑反证法。设 $S$ 被 $R$ 划分出的等价类中有一个不是单元集，设为 $[x_1]=\{x_1, x_2,\cdots x_n\}$。 取 $x_1,x_2$，由等价类的性质 $x_1\ R\ x_2$ 且 $x_2\ R\ x_1$，那么 $x_1=x_2$，矛盾。故所有等价类均为单元集。 5. 错误。自反性要求对于所有的 $a$ 均有 $a\ R\ a$ 成立，这个证明只是证明了对 $R$ 的集合中出现过的 $a$ 均有 $a\ R\ a$ 成立。 比如举出定义在 $\mathbb Z^2$ 上的关系 $R = \varnothing$ 就可以反驳他的证明。 ### B.3 1. 设 $f$ 的值域为 $C$，显然 $|A|\ge |C|$。 **a. ** 若 $f$ 是单射，则必有 $|A|=|C|$。由 $C\sube B$ 可知 $|A|=|C|\le |B|$。 **b.** 若 $f$ 是满射，则必有 $|B|=|C|$，那么 $|A|\ge|B|$。 2. 不是；是。 3. 若有二元关系 $R=\{(a_1,b_1), (a_2, b_2),\cdots\}$，我们定义其**逆**为 $R^\prime=\{(b_1,a_1),(b_2,a_2),\cdots\}$。 （或者说，设 $a\ R^\prime\ b$ 当且仅当 $b\ R\ a$） 4. 对于两个自然数 $x,y$，设 $x$ 的十进制表示长度为 $|x|$，$y$ 同理，取 $n=\max(|x|,|y|)$。 在 $x,y$ 前用前导 $0$ 补成 $n$ 位，设 $x=\overline{a_1a_2\cdots a_n}$，$y=\overline{b_1b_2\cdots b_n}$。 我们定义 $g(x,y)=\overline{a_1b_1a_2b_2\cdots a_nb_n}$，容易发现 $g:\mathbb N\times \mathbb N\to \mathbb N$ 构成双射。 定义 $s(x)=\begin{cases}0 & x \ge 0\\ -1 & x<0\end{cases}$， $\text{sgn}(x)=\begin{cases}1 & x > 0\\ 0 & x =0\\-1 & x<0\end{cases}$。 那么 $f_1(x,y)=\text{sgn}(x)(2\times g(|x|,|y|)+s(y))$ 就是一个 $\mathbb Z\times\mathbb Z\to \mathbb Z$ 的双射，求其逆记为 $f$，这就是一个合法的答案。 ### B.4 1. 考虑每条边会对总度数产生 $2$ 的贡献，原式显然。 2. 1. 在这个路径中不断地删去环就可以得到一条简单路径。 2. 在这个环中取 $v_x=v_y,x\le y$（其中 $x\ne 1$ 或 $y\ne n$），截出子串 $\{v_x,v_{x+1},\cdots v_y\}$。 重复以上操作至无法操作即可。 （这两个证明的详细过程懒得写了） 3. 考虑数学归纳法。 - $|V|=1$ 时，显然有 $|E|\ge 0=|V|-1$。 - 设 $|V|=n\ge 1$ 时成立。我们取任意一张 $|V|=n+1$ 的图，找出一个 $x$ 使 $\deg(x)=1$。 由于连通且 $n+1>1$，所以 $\forall x,\deg(x)\ge 1$。如果找不到则说明 $\sum_{i=1}^n \deg(x)\ge 2n$，则 $|E|\ge |V|-1$ 已经成立。 否则我们删去这条边和点 $x$，那么剩下的 $n$ 个点和所有边构成的图依然连通（这可以通过反证说明），至少含有 $n-1$ 条边。 算上删去的这一条就是至少有 $n$ 条边，依然满足。 综上，命题成立。 4. 自反性：考虑路径 $\left<x\right>$，所以每个点都能到达自己； 对称性：将路径反转，我们发现 $x$ 能到达 $y$ 可推出 $y$ 能到达 $x$； 传递性：将两条路径接起来。 因此"从......可达"是等价关系。 自反性和传递性。 5. 纱比题，懒得写了。 6. 就是那个提示里的内容 (?) 不知道这题想干嘛。 ### B.5 1. 为什么这里有那么多煞笔题？？？ 2. 由于 $v_0$ 到每个点都有唯一路径，因此没有一个除 $v_0$ 外的点可以到达 $v_0$，否则就会存在环。 对于任意结点对 $(x,y)$，找出 $v_0$ 到 $x$ 的路径和 $v_0$ 到 $y$ 的路径，把它们去掉一个最长公共前缀然后接在一起即可找到 $G$ 的无向版本的一条简单路径。 因此 $G$ 的无向版本是一张连通图。而若 $G$ 的无向版本中存在环，那么我们把这个环在 $G$ 中找出来。 如果每个点的入度都为 $1$，那么就构成了 $G$ 中的一个环，矛盾。因此至少有一个点入度不为 $1$。 又因为环中入度等于结点数，因此有一个点入度为 $0$ 就意味着有至少一个点入度大于 $1$。因此至少有一个点入度大于 $1$。 任取这个点的两条入边 $(u_1,v)$ 和 $(u_2,v)$，那么 $v_0$ 到 $v$ 就至少有 $v_0\rightsquigarrow u_1\to v$ 和 $v_0\rightsquigarrow u_2\to v$，矛盾。 故 $G$ 是一张无环的无向连通图，即一棵树。