page463.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 52 行
HTML
52 行
<HTML><HEAD><TITLE>Implementation</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html6499" HREF="page464.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6497" HREF="page461.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6493" HREF="page462.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6501" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0014432000000000000000">Implementation</A></H3><P>Program <A HREF="page463.html#progexamplet"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the method <tt>typeset</tt>which takes three arguments.The first, <tt>l</tt>, is an array of <I>n</I> integers thatgives the lengths of the words in the sequence to be typeset.The second, <tt>D</tt>, specifies the desired paragraph widthand the third, <tt>s</tt>, specifies the normal inter-word space.<P><P><A NAME="33726"> </A><A NAME="progexamplet"> </A> <IMG WIDTH=575 HEIGHT=504 ALIGN=BOTTOM ALT="program33723" SRC="img1886.gif" ><BR><STRONG>Program:</STRONG> Dynamic programming example--typesetting a paragraph.<BR><P><P>The method first computes the lengths, <IMG WIDTH=25 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68303" SRC="img1861.gif" >,of all possible subsequences (lines 3-7).This is done by using the dynamic programming paradigmto evaluate the recursive definition of <IMG WIDTH=25 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68303" SRC="img1861.gif" >given in Equation <A HREF="page461.html#eqnalgslength"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The running time for this computation is clearly <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" >.<P>The next step computes the one-line penalties <IMG WIDTH=23 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68329" SRC="img1866.gif" >as given by Equation <A HREF="page461.html#eqnalgspenalty"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (lines 8-14).This calculation is a straightforward oneand its running time is also <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" >.<P>Finally, the minimum total costs, <IMG WIDTH=24 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68121" SRC="img1817.gif" >,of typesetting each subsequence are determinedfor all possible subsequences (lines 15-26).Again we make use of the dynamic programming paradigmto evaluate the recursive definition of <IMG WIDTH=24 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68121" SRC="img1817.gif" >given in Equation <A HREF="page461.html#eqnalgscost"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The running time for this computation is <IMG WIDTH=40 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58941" SRC="img329.gif" >.As a result, the overall running time required todetermine the best way to typeset a paragraph of <I>n</I> words is <IMG WIDTH=40 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58941" SRC="img329.gif" >.<P><HR><A NAME="tex2html6499" HREF="page464.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6497" HREF="page461.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6493" HREF="page462.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6501" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?