-
Notifications
You must be signed in to change notification settings - Fork 1
/
Homework12-1.tex
186 lines (160 loc) · 7.67 KB
/
Homework12-1.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
\section{0430}\label{sec:0430}
\begin{questions}
\question 已知$n$个矩形，这些矩形的边都平行于坐标轴
\begin{parts}
\part 求出这些矩形的交集
\begin{solution}
求两个矩形的交集所需时间为$O(1)$。
任取两个求交集，求得的交集再与下一个矩形求交集即可。
该交集若存在则仍然是一个矩形。
\textbf{伪代码见算法\ref{alg:0430:1-1}}
\end{solution}
\begin{algorithm}[!htp]
\caption{矩形交集}\label{alg:0430:1-1}
\begin{algorithmic}[1]
\Require {一组矩形$R = \left\{ \langle y_u, x_l, y_b, x_r \rangle \right\}$} \Comment{矩形的四条边，按上左下右的顺序}
\Ensure {这些矩形的交集$\langle Y_u, X_l, Y_b, X_r \rangle$} \Comment{若不存在交集，则这四条边不构成矩形}
\State $\langle Y_u, X_l, Y_b, X_r \rangle \gets \Call{Select}{R}$ \Comment{从集合中任选一个矩形作为当前的交集}
\For { $\langle y_u, x_l, y_b, x_r \rangle$ in $R$ }
\State $Y_u \gets \min(Y_u, y_u), Y_d \gets \max(Y_d, y_d)$
\State $X_l \gets \max(X_l, x_l), X_r \gets \min(X_r, x_r)$
\If{$Y_u \le Y_d \vee X_l \ge X_r$}
\State \textbf{break}
\EndIf
\EndFor
\end{algorithmic}
\end{algorithm}
\part 求出这些矩形能够覆盖的面积
\begin{solution}
使用扫描线算法。
事件列表为所有矩形的竖直边。
扫描线状态为当前扫描线穿过的所有矩形。
当扫描线状态发生变化时，计算当前事件点到上一个事件点之间的有效面积，然后更新当前扫描线上的有效高度。
\textbf{伪代码见算法\ref{alg:0430:1-2}}
\end{solution}
\begin{algorithm}[!htp]
\caption{矩形并集面积}\label{alg:0430:1-2}
\begin{algorithmic}[1]
\Require {一组矩形$R = \left\{ \langle y_u, x_l, y_b, x_r \rangle \right\}$} \Comment{矩形的四条边，按上左下右的顺序}
\Ensure {这些矩形的覆盖面积}
\State 对所有矩形按两条竖直边的横坐标建最小化堆$events$，有元素$2n$个 \Comment{$O(n)$}
\State $state \gets \Call{RedBlackTree.New}{}$
\State $xlast \gets \min(x), ylast \gets 0$
\State $space \gets 0$
\For { $e$ in $events$ }
\State $x, y_u, y_d \gets \Call{Extract}{e}$
\State $space \gets space + (x-xlast) \times ylast$
\If {$x_l$ in $e$} \Comment{遇到左边，出现一个新的矩形}
\State $\Call{RBTree.Insert}{state, \mathsf{key=}y_u, \mathsf{value=}(y_u, \mathsf{up})}$
\State $\Call{RBTree.Insert}{state, \mathsf{key=}y_b, \mathsf{value=}(y_b, \mathsf{bottom})}$
\ElsIf {$x_r$ in $e$} \Comment{遇到右边，这个矩形消失}
\State $\Call{RBTree.Remove}{state, \mathsf{key=}y_u}$
\State $\Call{RBTree.Remove}{state, \mathsf{key=}y_b}$
\EndIf
\State $xlast \gets x, ylast \gets 0$ \Comment{更新当前的有效高度}
\State $current \gets \Call{Stack.New}{}$
\For {$(y, type)$ in $state$}
\If {$type = \mathsf{up}$}
\State $\Call{Stack.Push}{current, y}$
\ElsIf {$type = \mathsf{bottom}$}
\State $ytop \gets \Call{Stack.Pop}{current}$
\If {\Call{Stack.empty}{}}
\State $ylast \gets ylast + (y - ytop)$
\EndIf
\EndIf
\EndFor
\EndFor
\end{algorithmic}
\end{algorithm}
\end{parts}
\question 求$n!$包含质因子$p$的数量，例如$6！$含有4个2，2个3和1个5。
并给出算法的时间复杂性
\begin{solution}
$n!$有 $\left(n / p+n / p^{2}+n / p^{3}+\cdots\right)$ 个因子 $p$
$O(\log n)$
\end{solution}
\begin{solution}
\textbf{伪代码见算法\ref{alg:0430:2}}
时间复杂度为$O(n)$
\end{solution}
\begin{algorithm}[!htp]
\caption{质因子数量}\label{alg:0430:2}
\begin{algorithmic}[1]
\Require {正整数$n$，素数$p$}
\Ensure {$n!$包含质因子$p$的数量$C$}
\State $cnt[1 \dots n] \gets \left\{0\right\}$
\State $C \gets 0$
\For { $k \gets p$ up to $n$ }
\If { $k \equiv 0 \bmod p$ }
\State $cnt[k] \gets cnt[k/p] + 1$
\State $C \gets C + cnt[k]$
\EndIf
\EndFor
\end{algorithmic}
\end{algorithm}
\question 设Fibonacci数列的定义为：
\[
F(n) = \begin{cases}
1 & , n=1,2 \\
F(n-1)+F(n-2) & , n > 2
\end{cases}
\]
证明每个大于$2$的整数$n$都可以写成至多$\log{n}$个Fibonacci数之和，并设计算法对于给定的$n$寻找这样的表示方式
\begin{solution}
首先设计用若干Fibonacci数之和表示给定大于$2$的整数$n$的算法，
并由此证明每个大于$2$的整数$n$都可以写成Fibonacci数之和。
然后证明在这样的表示中，使用的Fibonacci数至多有$\log_2{n}$个。
对于一个大于$2$的整数$n$，若$n$是Fibonacci数，则命题显然成立。
若$n$不是Fibonacci数，则一定存在一个$m(m>2)$，使得\[
F(m) < n < F(m+1)
\]
又\[
F(m+1) = F(m) + F(m-1)
\]
所以\[
0 < n - F(m) < F(m-1)
\]
不妨设$n' = n - F(m)$。
若$n'$是Fibonacci数，则$n = F(m) + n'$表示成了两个Fibonacci数之和。
否则若$n' > 2$，则令$n=n'$，重复上述步骤，直到$0 < n' \le 2$。
此时$n'=1$或$2$仍然是Fibonacci数。
所以每个大于$2$的整数$n$都可以用这种算法写成若干个Fibonacci数之和。
\textbf{伪代码见算法\ref{alg:0430:3}}
注意到\[
F(m') < n' < F(m' + 1) \le F(m-1) < F(m) < n < F(m-1)
\]
所以每个Fibonacci数至多使用一次，且不会有连续两个Fibonacci出现在结果中。
又不超过$n$的最大Fibonacci数为$F(m-2)$，即\[
\frac{F(m)}{F(m')}
\ge \frac{F(m)}{F(m-2)}
= \frac{F(m-1) + F(m-2)}{F(m-2)} = 2 + \frac{F(m-3)}{F(m-2)}
\ge 2
\quad (m \ge 3)
\]
即结果中相邻两个Fibonacci数之间的倍数一定超过$2$。
所以一定不超过$\log_2{n}$个。
\end{solution}
\begin{algorithm}[!htp]
\caption{Fibonacci表示}\label{alg:0430:3}
\begin{algorithmic}[1]
\Require {正整数$n$}
\Ensure {若干个Fibonacci数$repr$，其和为$n$}
\State $repr \gets \Call{Vector.New}{}$
\State $Fib \gets \Call{Stack.New}{}$
\State $\Call{Stack.Push}{Fib, 1}$
\State $last \gets 1$
\Repeat
\State $next \gets last + \Call{Stack.top}{Fib}$
\State $\Call{Stack.Push}{Fib, last}$
\State $last \gets next$
\Until {$last > n$}
\Repeat
\State $next \gets \Call{Stack.Pop}{Fib}$
\If {$n \ge next$}
\State $\Call{Vector.PushBack}{repr, next}$
\State $n \gets n - next$
\EndIf
\Until {$n = 0$}
\end{algorithmic}
\end{algorithm}
\end{questions}