%\documentclass{beamer} %\documentclass[slidestop,compress,mathserif]{beamer} \documentclass[slidestop,compress,mathserif,xcolor=dvipsnames]{beamer} \usepackage{pgfpages} \usetheme{Berlin} \usecolortheme{seahorse} %\usecolortheme[named=black]{structure} \setbeamercolor{section in head/foot}{fg=white,bg=gray!20!black} \setbeamertemplate{items}[ball] %\setbeamertemplate{blocks}[rounded][shadow=true] \setbeamertemplate{navigation symbols}{} %\setbeamertemplate{headline}{} %<= to suppress the headline otherwise % section and subsection will be displayed in the navigation bar \setbeamertemplate{footline}{} %\beamersetuncovermixins{\opaqueness<1>{25}}{\opaqueness<2->{15}} \usepackage{graphicx}% http://ctan.org/pkg/graphicx \usepackage{booktabs}% http://ctan.org/pkg/booktabs \let\Tiny=\tiny \usepackage{fontspec} \setmainfont{WenQuanYi Micro Hei} \setsansfont{WenQuanYi Micro Hei Mono} \setmonofont{WenQuanYi Micro Hei Mono} \XeTeXlinebreaklocale "zh" \XeTeXlinebreakskip = 0pt plus 1pt \begin{document} \setbeamerfont{subsection in sidebar}{size=\tiny} \setbeamerfont{title in sidebar}{size=\tiny} \title{\fontsize{28}{35}\selectfont UVA 10157\\ \fontsize{14pt}{20pt}\selectfont Expression} %\author{Author Name} \institute{} \frame{\titlepage} \section{題意} \subsection{} \begin{frame} \frametitle{題意1} \uncover<1-> {給你 n 和 d ,你的任務是找出長度為 n,且深度為 d 正確之括號表示式共有多少個。\\} \uncover<2-> {\vspace{\baselineskip}} \uncover<2-> {令 X 表示正確的括號表示式。X 的內容為僅含 '(' 和 ')' 的字串。定義如下:\\} \begin{itemize} \uncover<3-> {\item 空字串屬於 X。\\} \uncover<4-> {\item 假如 A 屬於 X ,那麼 (A) 也屬於 X。\\} \uncover<5-> {\item 假如 A 和 B 都屬於 X ,那麼 AB 也屬於 X。\\} \end{itemize} \end{frame} \subsection{} \begin{frame} \frametitle{題意2} \uncover<1-> {令 E 是一個正確的括號表示式(因此 E 屬於 X)。\\} \uncover<2-> {\vspace{\baselineskip}} \uncover<2-> {E 的長度為字串的長度。\\} \uncover<3-> {\vspace{\baselineskip}} \uncover<3-> {而 E 的深度 D(E) 被定義如下:\\} \uncover<4-> {\vspace{\baselineskip}} \uncover<4-> {$ D(E)=\left\{ \begin{aligned} & 0 \qquad 如果 E 是 \varnothing \\ & D(A)+1 \qquad 如果 E = (A), 並且 A\in{X} \\ & max(D(A),D(B)) \qquad 如果 E = AB, 並且 A,B\in{X} \end{aligned} \right.$} \end{frame} \section*{Input and Output} \begin{frame} \frametitle{Input and Output} Input \\ 6 2\\ 300 150\\ Output \\ 3 \\ 1 \\ \end{frame} \section{思考路線} \subsection{} \begin{frame} \frametitle{要用何種演算法?} \begin{itemize} \uncover<1->{\item{DP}} %\uncover<2->{\item{單邊一直加1?}} %\uncover<3->{\item{左右邊一直加1?}} \end{itemize} \end{frame} \section{解題方法} \subsection{} \begin{frame} \frametitle{遞迴公式} \uncover<1->{$ F(n,d)=\left\{ \begin{aligned} & 1 \ if\ n=0\ \\ & \mathop{\sum_{k=0}^{n-2}}_{k\;is\;even} F(k,d-1)\times{F(n-k-2,d)}\;otherwise \end{aligned} \right.$\\ \vspace{\baselineskip}} \uncover<2->{F(n,d)之值為長度n的情況,深度不超過d之正確括號總數\\ \vspace{\baselineskip}} \uncover<3->{因此,F(n,d)-F(n,d-1)便是長度n深度為d的正確括號總數 \\ \vspace{\baselineskip}} \end{frame} \begin{frame} \frametitle{遞迴公式想法部份} \uncover<1->{$ F(n,d)=\left\{ \begin{aligned} & 1 \ if\ n=0\ \\ & \mathop{\sum_{k=0}^{n-2}}_{k\;is\;even} F(k,d-1)\times{F(n-k-2,d)}\;otherwise \end{aligned} \right.$\\ \vspace{\baselineskip}} \uncover<1->{令E是一個長度為n深度為d之合法的表達式,且不為$\varnothing$,\\ 而A、B為合法表達式 \\ \vspace{\baselineskip}} \uncover<2->{E=(A)B \\ \vspace{\baselineskip}} \uncover<3->{根據上式可得知,\\A的深度等於d-1或B的深度等於d,且A的長度加B的長度為n-2 \\ \vspace{\baselineskip}} \end{frame} \begin{frame} \frametitle{遞迴公式實踐} \uncover<1->{根據上一張投影片的想法,\\便可以得知,任意一個不為$\varnothing$的E都可拆成(A)B且不重覆,\\ \vspace{\baselineskip}} \uncover<2->{$ F(n,d)=\left\{ \begin{aligned} & \mathop{\sum_{k=0}^{n-2}}_{k\;is\;even} F(k,d-1)\times{F(n-k-2,d)} \end{aligned} \right.$ \\ \vspace{\baselineskip}} \uncover<3->{最後加上空集合後,得到,\\ \vspace{\baselineskip}} \uncover<4->{$ F(n,d)=\left\{ \begin{aligned} & 1 \ if\ n=0\ \\ & \mathop{\sum_{k=0}^{n-2}}_{k\;is\;even} F(k,d-1)\times{F(n-k-2,d)}\;otherwise \end{aligned} \right.$\\ \vspace{\baselineskip}} \end{frame} \begin{frame} \frametitle{Result DP table} \begin{tabular}{c||c|c|c|c|c|c|c|c|c|c} {n$\setminus$d}&\textbf{0}&\textbf{1}&\textbf{2}&\textbf{3} &\textbf{4}&\textbf{5}&\textbf{6}&\textbf{7}&\textbf{8}&\textbf{9}\\ \hline \hline \textbf{0}&1&1&1&1&1&1&1&1&1&1 \\ \hline \textbf{2}&0&1&1&1&1&1&1&1&1&1 \\ \hline \textbf{4}&0&1&2&2&2&2&2&2&2&2 \\ \hline \textbf{6}&0&1&4&5&5&5&5&5&5&5 \\ \hline \textbf{8}&0&1&8&13&14&14&14&14&14&14 \\ \hline \textbf{10}&0&1&16&34&41&42&42&42&42&42\\ \end{tabular} \end{frame} \end{document}PDF:UVA 10157 Expression(Result)
2012年10月22日 星期一
使用XeLax與beamer來做pdf版的簡報
2012年10月1日 星期一
linux make command learning
My first Makefile
#example 1:
#usage: make main OR make
#main: nerve.o
# g++ nerve.o -o main
#nerve.o:
# g++ nerve.cpp -c
#clean:
# rm -rf nerve.o
#main: nerve.py
# python nerve.py
main: nerve.cpp
g++ nerve.cpp -o main
若使用vim的make指令時,要注意所在的資料夾位置,可以使用make -C來指定資料夾位置,或是在.vimrc裡面加入:cd 資料夾位置(如:cd ~/program/)
#example 1:
#usage: make main OR make
#main: nerve.o
# g++ nerve.o -o main
#nerve.o:
# g++ nerve.cpp -c
#clean:
# rm -rf nerve.o
#main: nerve.py
# python nerve.py
main: nerve.cpp
g++ nerve.cpp -o main
若使用vim的make指令時,要注意所在的資料夾位置,可以使用make -C來指定資料夾位置,或是在.vimrc裡面加入:cd 資料夾位置(如:cd ~/program/)
訂閱:
文章 (Atom)