1. Weisi Dai
  2. homework

Commits

Weisi Dai  committed 92150cb

added compile_hw7

  • Participants
  • Parent commits 450f9da
  • Branches default

Comments (0)

Files changed (1)

File compile_hw7.tex

View file
  • Ignore whitespace
+% multiple1902 <multiple1902@gmail.com>
+% public on https://bitbucket.org/multiple1902/homework
+% licensed under cc by-sa 3.0
+\documentclass[12pt]{article}
+\def\course{编译原理}
+\def\homeworkid{7}
+\usepackage{amsthm,amssymb,fullpage}
+\usepackage{enumerate}
+\usepackage[slantfont,boldfont,CJKnumber,CJKtextspaces,CJKmathspaces]{xeCJK}
+\usepackage{tabularx}
+\usepackage{booktabs}
+\usepackage{multicol}
+\usepackage[
+    colorlinks, %linkcolor=blue,anchorcolor=blue,citecolor=green,
+    pdfcreator={TeX}, pdftitle={\course 作业\homeworkid},
+    pdfauthor={multiple1902@gmail.com}
+    ]{hyperref}
+\def\UrlBreaks{\do-\do_}
+\setCJKmainfont{細明體}
+\setCJKsansfont{微軟正黑體}
+\newcommand{\problem}[1]{
+    \noindent \hskip 0.05\linewidth \fbox{\parbox{0.9\linewidth}{#1}} \\
+}
+\usepackage{pstricks}
+\usepackage{pst-node}
+\usepackage{algpseudocode}
+\usepackage{algorithm}
+
+
+\begin{document}
+
+\noindent\begin{tabularx}{\linewidth}{|X|}
+\hline \vskip -2mm
+{\sf \course} \hfill \today \\
+{\centering \sf \large
+Homework \homeworkid \\ }
+计算机92班 \hfill 戴唯思 09055029 \\ \hline
+\end{tabularx}
+
+\section*{8.4}
+
+    \problem{给出自适应线性表的查/填算法, 注意修改自适应链.}
+
+    见算法\ref{lookup-in-self-fit-list}.
+
+    \begin{algorithm}
+        \caption{自适应线性表的查/填算法}
+        \label{lookup-in-self-fit-list}
+        \begin{algorithmic}[1]
+            \Procedure{Lookup-In-Self-Fit-List}{$x$}
+                \State Visited[$i$]$\gets$False, $i=0,1,2,\cdots,n-1$
+                \State trypos $\gets$ first
+                \State Visited[trypos] $\gets$ True \label{step2}
+                \If{list[trypos]=$x$}
+                    \State first $\gets$ trypos
+                    \State Goto \ref{laststep}
+                \Else
+                    \If{Visited[list[trypos].next]$=$False}
+                        \State trypos $\gets$ list[trypos].next
+                        \State Goto \ref{step2}
+                    \EndIf
+                \EndIf
+                \State index $\gets$ newitem()
+                \State list[index].next $\gets$ first, first $\gets$ index
+                \State Return list[first] \label{laststep}
+            \EndProcedure
+            
+        \end{algorithmic}
+    \end{algorithm}
+
+\section*{8.5}
+
+    \problem{设计一个算法, 它将按字典顺序输出二叉树上各结点的名字.}
+
+    见算法\ref{magical-order-travel}.
+
+    \begin{algorithm}
+        \caption{字典顺序遍历二叉树}
+        \label{magical-order-travel}
+        \begin{algorithmic}[1]
+            \Procedure{Magical-Order-Travel}{BT}
+                \If{BT.rc}
+                    \State Magical-Order-Travel(BT.rc)
+                \EndIf
+                \State Print BT.data
+                \If{BT.lc}
+                    \State Magical-Order-Travel(BT.lc)
+                \EndIf
+            \EndProcedure
+            
+        \end{algorithmic}
+    \end{algorithm}
+
+\section*{8.6}
+    
+    \problem{假定我们有一张10个单元的哈希(链)表和一个足够大的用于登记符号名和连接指示器的存储区域. 用自然数作名字, 定义哈希函数为$H(i)=i\ $(mod 10). 当最初的10个素数$2,3,5,\cdots,29$进入符号表之后, 给出哈希链表和符号表的内容. 当更多的素数进入符号表后, 你能期望它们随机均匀分布于十个子表中吗? 为什么?}
+
+    % [0, 1, 1, 3, 0, 1, 0, 2, 0, 2]
+
+    \begin{table}[h!]
+        \centering
+        \begin{tabular}{ccccc} \toprule
+            哈希表索引 & 哈希表值 & 符号表索引 & 符号表值域 & 符号表next域\\ \midrule
+            0 & --- & 0 & 2 & --- \\
+            1 & 4 & 1 & 3 & 5 \\
+            2 & 0 & 2 & 5 & --- \\
+            3 & 1 & 3 & 7 & 6 \\
+            4 & --- & 4 & 11 & ---\\
+            5 & 2 & 5 & 13 & 8 \\
+            6 & --- & 6 & 17 & --- \\
+            7 & 3 & 7 & 19 & 9 \\
+            8 & --- & 8 & 23 & --- \\
+            9 & 7 & 9 & 29 & --- \\ \bottomrule
+        \end{tabular}
+        \caption{哈希链表和符号表内容}
+        \label{tab:hash-link-list-and-token-table}
+    \end{table}
+
+    它们不会随机均匀分布, 因为根据数学知识, 可以证明没有任何素数以4, 6, 8, 0结尾.
+
+
+\end{document}