\documentclass[UTF8]{ctexart}
\usepackage[ruled, linesnumbered]{algorithm2e}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{boxedminipage}
\usepackage{circuitikz}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{fullpage}
\usepackage{gensymb}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage[hidelinks]{hyperref}
\usepackage{listings}
\usepackage{mflogo}
\usepackage{multirow}
\newcommand{\nop}[1]{}
\usepackage{siunitx}
\usepackage{subfigure}
\usepackage{texnames}
\usepackage{textcomp}
\usepackage{tikz}
\usepackage{titlesec}
\usepackage{wrapfig}
\usepackage{xcolor}
\usepackage{xltxtra}

\setlength{\headheight}{0pt}
\geometry{left=2.5cm,right=2.5cm,headsep=2cm,bottom=2cm,footnotesep=2cm}
\pagestyle{fancy}
\fancyfoot[C]{\thepage}
\fancyhead[L]{计算机科学与技术系}
\fancyhead[C]{
    \begin{huge}
        \textbf{}
    \end{huge}\\
    \vspace{0.4cm}
    \ \ \ \ \ \ \ \ }
\fancyhead[R]{\ \ \ \ \ \ \ \ \ \ \ \ 2023年11月15日}

\ctexset{
    section={
      format+ = \Large \raggedright,
     }
}

\newtheorem{theorem}{定理}
\newtheorem{lemma}{引理}
\newtheorem{definition}{定义}

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{arrows, positioning}

\newcounter{aufgc}
\newenvironment{exercise}[1]%
{\refstepcounter{aufgc}\textbf{问题 \arabic{aufgc}} \emph{#1} \\}
{\vspace{0.2cm}}%

\renewcommand{\labelenumi}{(\alph{enumi})}

\definecolor{mygray}{rgb}{0.4,0.4,0.4}
\definecolor{mygreen}{rgb}{0,0.8,0.6}
\definecolor{myorange}{rgb}{1.0,0.4,0}

\lstset{
    basicstyle=\footnotesize\sffamily\color{black},
    basicstyle=\tt,
    keywordstyle=\color{purple}\bfseries,
    commentstyle=\color{mygray},
    numbers=left,
    numbersep=5pt,
    numberstyle=\tiny\color{mygray},
    showspaces=false,
    showstringspaces=false,
    stringstyle=\color{myorange},
    tabsize=2,
    backgroundcolor=\color[RGB]{245,245,244}
}

\begin{document}

\textbf{Q1.}

1.

给出对应赫夫曼树如下

\begin{tikzpicture}
    \node[draw, circle] (1) {}
    child{node[draw, circle] (2) {}
            child{node[draw, circle] (3) {}
                    child{node[draw, circle] (4) {}
                            child{node[draw, circle] (5) {}
                                    child{node[draw, circle] (6) {}
                                            child{node[draw, circle] (7) {}
                                                    child{node[draw, circle] (8) {a}}
                                                    child{node[draw, circle] (9) {b}}}
                                            child{node[draw, circle] (10) {c}}}
                                    child{node[draw, circle] (11) {d}}}
                            child{node[draw, circle] (12) {e}}}
                    child{node[draw, circle] (13) {f}}}
            child{node[draw, circle] (14) {g}}}
    child{node[draw, circle] (15) {h}};

\end{tikzpicture}

因此有如下的赫夫曼编码

\begin{table}[htbp]
    \centering
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|}
        \hline
        字符 & a       & b       & c      & d     & e    & f   & g  & h \\
        \hline
        编码 & 0000000 & 0000001 & 000001 & 00001 & 0001 & 001 & 01 & 1 \\
        \hline
    \end{tabular}
\end{table}

2. 前 $n$ 个字符中第 $0$ 个字符最优前缀编码为 $\underbrace{0\cdots0}_{n-1\ \mbox{\zihao{6}个}}$，第 $i(1\leqslant i\leqslant n-1)$
个字符最优前缀编码为 $\underbrace{0\cdots0}_{n-1-i\ \mbox{\zihao{6}个}}1$.

\begin{proof}
    只需证明前 $k$ 个字符出现频率之和不大于第 $k+2$ 个字符出现频率，
    这样在建赫夫曼树时，前面 $k+1$ 个字符会先建成一个由前 $k$ 个字符
    的组成的子树加上第 $k+1$ 个字符的叶子节点组成的子树.

    使用归纳法，当 $k=1$ 时，显然成立. 假设当 $k=n-1$ 时成立，即
    $F_0+\cdots+F_{n-2}\leqslant F_n$，则当 $k=n$ 时，有 $F_0+\cdots+F_{n-2}+F_{n-1}\leqslant F_n+F_{n-1}=F_{n+1}$，
    即以上的结论成立.
\end{proof}

\newpage

\textbf{Q2.}

由题，总的代价为 \[\sum_{i=1}^{n}f(i)=n+2\cdot3-1+2\cdot3^2-1+\cdots+2\cdot3^{\lfloor\log_3n\rfloor}-1=n-\lfloor\log_3n\rfloor+6\cdot\frac{1-3^{\lfloor\log_3n\rfloor}}{1-3}=O(n)\]

每次操作摊还代价为 $O(1)$.

\hrulefill\medskip

\textbf{Q3.}

\begin{proof}
    因为字符中最高频率也低于最低频率的两倍，因而选取其中最低频率的两
    个组成子树后，频率之和已经大于最高频率，这样每次选取的都是单独的
    字符，组成了128个子树，每个子树上只有两个字符. 而此时依然有最高
    频率低于最低频率的2倍，这样可以依次循环，最终得到一棵树，树上
    256个节点全都在第9层，因而赫夫曼编码长度也是8位，和固定长度编码
    长度相同.
\end{proof}

\hrulefill\medskip

\textbf{Q4.}

\begin{proof}
    对字符数 $n$ 使用归纳法，当 $n=2$ 时，假设树上两个字符为 $x,y$，
    显然两个字符的深度 $d_T(x)=d_T(y)=1$，内部节点只有根节点 $z$
    一个，编码树的代价为
    \[B(T)=f(x)d_T(x)+f(y)d_T(y)=f(x)+f(y)=f(z\mbox{的一个孩子节点})+f(z\mbox{的第二个孩子节点})\]
    因而成立.

    当 $n=k-1$ 时成立，而对于 $n=k$ 时，有 $B(T)=\sum_{\mbox{\zihao{6}叶子}l\in T}f(l)d_T(l)$，
    考虑 $T$ 上两个有相同双亲节点 $p$ 的叶子节点 $c_1,c_2$，将
    $T$ 上的 $c_1,c_2$ 收缩为 $p$ 得到 $T'$，由归纳假设有
    \[B(T')=\sum_{\mbox{\zihao{6}叶子}l\in T'}f(l)d_{T'}(l)=\sum_{\mbox{\zihao{6}内部节点}i\in T'}[f(i\mbox{的一个孩子节点})+f(i\mbox{的第二个孩子节点})]\]
    而对于 $T$ 有
    \begin{align}B(T)= & \sum_{\mbox{\zihao{6}叶子}l\in T}f(l)d_T(l)\nonumber                                         \\
             =     & \sum_{\mbox{\zihao{6}叶子}l\in T'-\{p\}}f(l)d_{T'}(l)+f(c_1)d_T(c_1)+f(c_2)d_T(c_2)\nonumber \\
             =     & \sum_{\mbox{\zihao{6}叶子}l\in T'-\{p\}}f(l)d_{T'}(l)+f(p)d_{T'}(p)+f(c_1)+f(c_2)\nonumber   \\
             =     & \sum_{\mbox{\zihao{6}叶子}l\in T'}f(l)d_{T'}(l)+f(c_1)+f(c_2)\nonumber                       \\
             =     & \sum_{\mbox{\zihao{6}内部节点}i\in T'}[f(i\mbox{的一个孩子节点})+f(i\mbox{的第二个孩子节点})]\nonumber        \\&+f(p\mbox{的一个孩子节点})+f(p\mbox{的第二个孩子节点})\nonumber \\
             =     & \sum_{\mbox{\zihao{6}内部节点}i\in T}[f(i\mbox{的一个孩子节点})+f(i\mbox{的第二个孩子节点})]\nonumber
    \end{align}
    综上，根据归纳法，得证.
\end{proof}

\textbf{Q5.}

1. 每次都对剩余零钱尝试取当前能用的面额最大硬币，直到完全找尽.

\begin{proof}
    假设存在更优的解，即所需硬币数更少，即可以用更少的硬币找零，
    但不是用当前最大面额硬币，但因为所有硬币面额都不大于更大面额
    硬币面额的一半，因而总能用更大面额硬币替换掉两个小面额硬币，
    这样就得到了一个更优的解，与假设矛盾，因而不存在更优的解.
\end{proof}

2.
\begin{proof}
    和以上题目中的证明一致，$c>1$，因而所有硬币面额都不大于更大
    面额硬币面额的一半，因此贪心算法总能得到最优解.
\end{proof}

3. 1分、3分、4分的硬币，如果要找6分零钱，则如果用贪心算法，会给出4分、1分、1分三枚硬币，但可以只用3分、3分两枚硬币.

\end{document}