Homework06-2.tex

\section{0326}\label{sec:0326}
\begin{questions}

    \question 证明二分查找是有序序列查找的最优算法
    \begin{solution}
        在一个长度为$n$的有序数组中查找一个元素，该元素的位置为$i$的概率为$p_i = \frac{1}{n}$。
        因此，\textbf{在没有附加信息的前提下}，事件“确定一个元素的位置”能提供的信息至少为$I_e = -\log{p_i} = \log n$。
        而一次比较只能给出真、假两种结果，即一次比较能提供的信息为$I_c = \log{2}$。
        所以至少需要经过
        \[\frac{I_e}{I_c} = \frac{ \log{n} }{ \log{2} } = \log_2{n}\]
        次比较方能确定长度为$n$的数组中一个元素的位置。
        即该问题的信息论下界为$\Omega(\log n)$。

        二分查找法的效率恰好为$\Omega(\log n)$，因此二分查找法是最优的基于比较的有序序列查找算法。

        但如果有附加信息存在（例如给定数组的分布情况）使该元素的位置为$i$的概率$p'_i > \frac{1}{n}$，
        则其信息量$I'_e < \log n$。
        此时利用这些附加信息可能不需要$\log_2{n}$次比较即可找到它的位置。

    \end{solution}


    \question 写出两种建堆方法的伪代码
    \begin{solution}
        \textbf{见算法\ref{0326:top-down-heap}、算法\ref{0326:bottom-top-heap}}
    \end{solution}

    \begin{algorithm}[!htp]
        \caption{自顶向下建堆}\label{0326:top-down-heap}
        \begin{algorithmic}[1]
            \Require {$A[1..n]$}
            \Ensure {重排$A$，使其每个非叶子节点的值不小于其子节点的值}
            \For {$i \gets 2$ to $n$}
            \State {$j \gets i$}
            \While {$j > 1 \wedge A[j] > A\left[\left\lfloor j/2 \right\rfloor\right]$}
            \State \Call{Swap}{$A[j] , A\left[\left\lfloor j/2 \right\rfloor\right]$}
            \State $j \gets \left\lfloor j/2 \right\rfloor$
            \EndWhile
            \EndFor
        \end{algorithmic}
    \end{algorithm}

    \begin{algorithm}[!htp]
        \caption{自底向上建堆}\label{0326:bottom-top-heap}
        \begin{algorithmic}[1]
            \Require {$A[1..n]$}
            \Ensure {重排$A$，使其每个非叶子节点的值不小于其子节点的值}
            \For {$i \gets \lfloor n/2 \rfloor$ to $1$}
            \State $j \gets 2i$
            \While {$ j \le n $}
            \If {$ j+1 \le n \wedge A[j+1] > A[j]$}
            \State $j \gets j+1$
            \EndIf
            \If {$ A[j] > A\left[\left\lfloor j/2 \right\rfloor\right]$}
            \State \Call{Swap}{$A[j] , A\left[\left\lfloor j/2 \right\rfloor\right]$}
            \Else
            \State \textbf{break}
            \EndIf
            \State $j \gets 2j$
            \EndWhile
            \EndFor
        \end{algorithmic}
    \end{algorithm}

    \question 对玻璃瓶做强度测试。
    设地面高度为$0$，从$0$往上有刻度$1$到$n$，相邻两个刻度间距离都相等。
    如果一个玻璃瓶从刻度i落到地面没有破碎，而在高度$i+1$处落到地面时碎了，则此类玻璃瓶的强度为$i$。
    \begin{parts}
        \part 若只有一个样品供测试，如何得到该类玻璃瓶的强度
        \begin{solution}
            从刻度$1$开始逐个高度进行测试，找到使其摔碎的最低高度。
        \end{solution}

        \part 如果样品数量充足，如何用尽量少的测试次数得到强度
        \begin{solution}
            使用二分法。首先测试高度$\frac{n}{2}$，若摔碎了则测试$\frac{n}{4}$，若没摔碎则测试$\frac{3}{4}n$，依此类推。
        \end{solution}

        \part 如果有两个样品，如何用尽量少的测试次数得到强度
        \begin{solution}
            第一个瓶子测试高度$k\sqrt{n}$（$k$从$1$到$\sqrt{n}$），可以确定一个高度为$\sqrt{n}$的区间。

            第二个瓶子在上述区间内从最低高度开始逐渐提升高度，最多测试$\sqrt{n}$次。

        \end{solution}
    \end{parts}
\end{questions}