-
Notifications
You must be signed in to change notification settings - Fork 1
/
Homework05-2.tex
197 lines (168 loc) · 9.44 KB
/
Homework05-2.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
187
188
189
190
191
192
193
194
195
196
197
\section{0319}
\begin{questions}
\question 有A、B、C三个桩子，A上放有$n$个不同大小的圆盘，按大小递减顺序自下而上。
\begin{parts}
\part 设计算法，用最少的移动步数将A上的圆盘都移到C，每次只能移一个，且任一桩子上的圆盘都必须满足圆盘大小自下而上递减的顺序。
\part 给定数组\texttt{p}，其元素取值只有1，2，3三种，代表了$n$个圆盘目前的位置，1代表A，2代表B，3代表C，\texttt{p[i]}的值为第$i$个圆盘的位置。
例如\texttt{p=[3,3,2,1]}\footnote{\texttt{p[0]}是最小的圆盘}表示共有4个圆盘，第一个和第二个都在C，第三个在B，第4个在A。
如果\texttt{p}代表了(a)中的最优移动过程中某一步的状态，则求出这是第几步。
注意诸如\texttt{p=[2,2]}是不可能出现的，此时算法得到$-1$。
\end{parts}
\begin{solution}
\begin{parts}
\part {
解决汉诺塔问题首要的是注意到当只有两个圆盘存在时问题的解决是十分简单的。
因此当解决有多个圆盘的汉诺塔问题时，可以将其中一部分圆盘看作是一个圆盘，另一部分圆盘看作是另一个圆盘，然后就可以应用两个圆盘的解法解决该问题，此时移动的每一步都是一个规模更小的汉诺塔问题。
最后要注意到分组时必须将最大的圆盘单独放在一组，其他的圆盘单独放在一组，方可保证在移动的过程中任一桩子上的圆盘都满足大小自下而上递减。
\textbf{伪代码见算法\ref{0319:Hanoi}}
}
\part {
由上述算法描述可知，解决$n$个圆盘的汉诺塔问题需要移动圆盘的次数$T(n)$符合表达式$$
T(n) = \begin{cases}
T(n-1) + T(1) + T(n-1) & , n \geq 2 \\
1 & , n=1
\end{cases}
$$
可易解得$T(n) = 2^n - 1$。
分析该算法可知，在解决规模为$n$的问题$H(n)$时，首先要将$n-1$个圆盘从$src$经过$2^{n-1}-1$次操作移至$via$上；
然后经$1$次操作将第$n$个圆盘从$src$移至$dst$上；
最后经$2^{n-1}-1$次操作将$n-1$个圆盘从$via$经过$2^{n-1}-1$次操作移至$dst$上。
因此在这个子问题中，第$n$个圆盘（即该问题中最大的圆盘）只有在$src$和在$dst$上两种状态，不可能存在某一步操作使其出现在$via$上。
因此给出一个解决问题$H(n)$的状态时，考察最大的圆盘的位置：
\begin{itemize}
\item 如果该圆盘在问题$H(n)$的$src$上则记$b_n$为$0$，此时正在解决的子问题$H(n-1)$是要将$n-1$个节点从$src$移至$via$上
\item 如果该圆盘在问题$H(n)$的$dst$上则记$b_n$为$1$，此时正在解决的子问题$H(n-1)$是要将$n-1$个节点从$via$移至$dst$上
\end{itemize}
迭代地进行上述过程，则可得到序列$\left\{b_i\right\}_{i \in [1, n]}$。
当$b_i$从$0$变为$1$时，恰好是第$i$个盘子从其$src$移到$dst$上的结果，此时问题$H(i)$恰好执行了$2^i$步。
因此$N = \sum_{i=1}^n{b_i \cdot 2^{i-1}}$可表示到此状态时已经经过的步数。
\textbf{伪代码见算法\ref{0316:CheckHanoi}}
}
\end{parts}
\end{solution}
\begin{algorithm}[!htp]
\caption{汉诺塔}\label{0319:Hanoi}
\begin{algorithmic}[1]
\Require {
三个栈$a, b, c$，
其中$a$中从栈顶到栈底为$0$到$n-1$共$n$个元素，$b,c$为空栈
}
\Procedure{Main}{}
\State\Call{Hanoi}{$a , b , c , n$}
\EndProcedure
\Statex
\Procedure{Hanoi}{$src , via , dst , n$}
\Statex
\Comment{解决以$via$为中介，从$src$的顶端移$n$个圆盘到$dst$上的汉诺塔问题}
\If{$n=1$}
\State $dst$.push($src$.pop()) \Comment{从$src$上取出最顶端的圆盘，放到$dst$上}
\Else
\State \Call{Hanoi}{$src , dst , via , n-1$}
\State \Call{Hanoi}{$src , via , dst , 1$}
\State \Call{Hanoi}{$via , src , dst , n-1$}
\EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}
\begin{algorithm}[!htp]
\caption{检查汉诺塔状态}\label{0316:CheckHanoi}
\begin{algorithmic}[1]
\Require { 数组$p[0..n-1]$表示用上述算法解决$n$个圆盘的汉诺塔问题的一个中间状态 }
\Ensure { 到达这一状态经过的步数$N$，如果该状态非法则为$-1$ }
\State $src \gets 1, via \gets 2, dst \gets 3$
\State $N \gets 0$
\For {$i \gets n-1$ downto $0$}
\If {$p[i] = src$}
\State $N \gets 2N + 0$
\State \Call{Swap}{$dst, via$}
\ElsIf {$p[i] = dst$}
\State $N \gets 2N + 1$
\State \Call{Swap}{$src, via$}
\Else
\State \Return $-1$
\EndIf
\EndFor
\State \Return $N$
\end{algorithmic}
\end{algorithm}
\question 课上的最大连续子序列是指和最大，如果要求是积最大呢？
{\kaishu
给定实数序列$x_1, x_2, \dots, x_n$，寻找连续子序列$x_i, x_{i+1}, \dots, x_j$使得其数值之积在所有连续子序列数值之积中为最大。
设空序列的积为1，只需求出最大值即可，不需要知道是哪个序列。
}
\begin{solution}
考虑乘积，在一个连续子序列后面加上一个元素时，既要考虑乘积绝对值的变化，也要考虑符号的变化。
若符号在某一次运算后为负数，且后面还有一个负的元素，则后缀的乘积仍有机会变正并大于现有的最大值。
考虑到这一因素，除了$MaxSuffix$以外，还需要一个$MinSuffix$以记录出现负元素时后缀乘积的情况，并按如下规则更新：
\begin{itemize}
\item $MaxSuffix = \max{\left\{MaxSuffix(i) \cdot x_{i+1}, MinSuffix(i) \cdot x_{i+1}, 1\right\}}$
\item 当$MinSuffix(i) < 0$时，$MinSuffix(i+1) = MinSuffix(i) \cdot x_{i+1}$
\item 当$MinSuffix > 0$时，$MinSuffix$应当总等于$MaxSuffix$
\end{itemize}
\textbf{伪代码见算法\ref{0319:MaxProd}}
\end{solution}
\begin{algorithm}[!htp]
\caption{最大乘积连续子序列}\label{0319:MaxProd}
\begin{algorithmic}[1]
\Require { 序列$\left\{ x_i \right\}_{1 \leq i \leq n}$ }
\Ensure { 乘积最大的连续子序列的乘积$MaxProd$ }
\State $MaxProd \gets 1$ \Comment{最大子序列的乘积}
\State $MaxSuffix \gets 1, MinSuffix \gets 1$ \Comment{最大正后缀乘积、最小负后缀乘积}
\For {$i \gets 1$ to $n$}
\State $MaxSuffix \gets MaxSuffix \cdot x_i$
\State $MinSuffix \gets MinSuffix \cdot x_i$
\If {$MaxSuffix < 1$}
\State $MaxSuffix \gets 1$
\EndIf
\If {$MaxSuffix < MinSuffix$}
\State $MaxSuffix \gets MinSuffix$
\EndIf
\If {$MinSuffix \geq 0$}
\State $MinSuffix \gets MaxSuffix$
\EndIf
\If {$MaxSuffix > MaxProd$}
\State $MaxProd \gets MaxSuffix$
\EndIf
\EndFor
\end{algorithmic}
\end{algorithm}
\question 背包问题中如果各种大小的物品的数量不限，那么如何知道背包是否能够恰好放满
{\kaishu
给定一个整数$K$和$n$种不同大小的物品，第$i$中物品的大小为整数$s_i$，每种物品的数量不限。
寻找一个物品的组合，它们的大小之和正好为$K$，或者确定不存在这样的组合。
}
\begin{solution}
\[
P(n,K) = P(n - 1, K) || P(n, K - k_n)
\]
\textbf{伪代码见算法\ref{0316:pack}}
\end{solution}
% \begin{solution}
% 记$s_0 = 0$，$P\left(K, S=\left\{s_1, s_2, \dots, s_n, s_0\right\}\right)$表示从$S$中选取物品是否能恰好装满一个大小为$K$的背包的问题。
% 则有$$
% P(K, \left\{s_1, s_2, \dots, s_n, s_0\right\}) = \bigvee_{K-ms_n \geq 0, \atop m \geq 0} P(K - ms_n, \left\{s_1, \dots, s_{n-1}, s_0\right\})
% $$
% 且$$
% \forall S \supset \left\{s_0\right\}, P(0, S) = \mathsf{true} \quad\quad \forall K > 0, P(K,\left\{s_0\right\})=\mathsf{false}
% $$
% \textbf{伪代码见算法\ref{0316:pack}}
% \end{solution}
\begin{algorithm}[!htp]
\caption{物品数量不限的背包问题}\label{0316:pack}
\begin{algorithmic}[1]
\Require { $K, S[1..n]$ }
\Ensure { 解是否存在 }
\State $P[0..n][0..K] \gets \left\{ \mathsf{false} \right\}$
\State $P[0][0] \gets \mathsf{true}$
\For{$k=0$ to $K$}
\For{$i=1$ to $n$}
\If{$P[i-1][k] = \mathsf{true}$}
\State $P[i][k] \gets \mathsf{true}$
\ElsIf{ $ k - S[i] \ge 0 $ }
\State $P[i][k] \gets P[i][k-S[i]]$
\EndIf
\EndFor
\EndFor
\end{algorithmic}
\end{algorithm}
\end{questions}