djwj233 的博客

djwj233 的博客

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

posted on 2021-11-06 11:46:21 | under 题解 |

做着玩玩,就当颓废了(

以下的解答是自己写的,就当作业本了,不一定对。这里有除了附录以外的全部答案。

附录 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) $$

  1. (以下均有 $|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} $$

  1. $$ \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 $$

  2. $|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} $$

  1. 我们知道

    $$ \mathcal O(f(n))+\mathcal O(g(n))=\mathcal O(f(n)+g(n)) $$

那么原式显然。(也可以用定义代入证明,不过细节多得要死)

  1. $$ \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}$。

  1. $$ \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)$。

  1. $$ \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) $$

  2. 我们参考书中对 $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)$。

  1. 易证 $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}$。

  1. 因为如果直接积分近似,会得到:

    $$ \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} $$ 第二个命题同理。

  1. 考虑数学归纳法。$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| $$ 这就证完了。

  1. 我们写出奇自然数集合的形式 $\mathrm{Odd}=\{2k+1 | k\in \mathbb N\}$,易证每个 $k$ 恰好对应一个元素,因此它与自然数集合一一对应。

  2. 考虑有集合 $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

这部分看着脑子已经不太够了

    • 自反性:$\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$ 不是全序关系。

    • 自反性:$\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$ 个完全剩余系。

  1. a. 考虑关系 $R=\{(a,b):a,b\in \mathbb N^+,a\&b\ne 0\}$( $\&$ 表示按位与)。

    b. 考虑在 $\mathbb R^2$ 上的 $\geq$。

    c. 考虑关系 $R=\varnothing$。

  2. 考虑反证法。设 $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$,矛盾。故所有等价类均为单元集。

  3. 错误。自反性要求对于所有的 $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$,这就是一个合法的答案。