📄 page469.html

📁 wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq
💻 HTML
📖 第 1 页 / 共 2 页
字号:
12 下一页
<HTML>
<HEAD>
<TITLE>Example</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
 <img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms 
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html7715" HREF="page470.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page470.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html7713" HREF="page468.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page468.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html7707" HREF="page468.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page468.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html7717" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html7718" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H3><A NAME="SECTION0015431000000000000000">Example</A></H3>
<P>
Suppose we are given a sequence of <I>n</I>=5 words,
 <IMG WIDTH=173 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69145" SRC="img1980.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1980.gif"  > 
having lengths
 <IMG WIDTH=121 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69147" SRC="img1981.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1981.gif"  >, respectively,
which are to be typeset in a paragraph of width <I>D</I>=60.
Assume that the normal width of an inter-word space is <I>s</I>=10.
<P>
We begin by computing the lengths of all the subsequences of <I>W</I>
using Equation&nbsp;<A HREF="page468.html#eqnalgslength" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page468.html#eqnalgslength"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
The lengths of all <I>n</I>(<I>n</I>-1)/2 subsequences of <I>W</I>
are tabulated in Table&nbsp;<A HREF="page469.html#tblalgsproblem" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page469.html#tblalgsproblem"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
<P>
<P><A NAME="33499">&#160;</A>
<P>
    <A NAME="tblalgsproblem">&#160;</A>
    <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=7 BORDER FRAME=HSIDES RULES=GROUPS>
<COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER>
<TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
	      </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>     </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=5> <IMG WIDTH=23 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69093" SRC="img1970.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1970.gif"  ></TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
<P>
	    <I>i</I></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=8 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69163" SRC="img1982.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1982.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><I>j</I>=1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  5 </TD></TR>
</TBODY><TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1  </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10  </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 20 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 30 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 42 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 92 </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    2  </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10  </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>     </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 20 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 32 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 82 </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    3  </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10  </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>     </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>    </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 22 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 72 </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    4  </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 12  </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>     </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>    </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>    </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 12 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 62 </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    5  </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 50  </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>     </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>    </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>    </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>    </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 50 </TD></TR>
</TBODY>
<CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Typesetting Problem</CAPTION></TABLE>
</P></DIV><P>
<P>
Given  <IMG WIDTH=23 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69093" SRC="img1970.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1970.gif"  >, <I>D</I> and <I>s</I>,
it is a simple matter to apply  <IMG WIDTH=107 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline69173" SRC="img1983.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1983.gif"  >
to obtain the one-line penalties,  <IMG WIDTH=23 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69119" SRC="img1975.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1975.gif"  >,
which measure the amount of stretching or compressing needed
to set all the words in a given subsequence on a single line.
These are tabulated in Table&nbsp;<A HREF="page469.html#tblalgssolution" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page469.html#tblalgssolution"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
<P>
<P><A NAME="33516">&#160;</A>
<P>
    <A NAME="tblalgssolution">&#160;</A>
    <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=11 BORDER FRAME=HSIDES RULES=GROUPS>
<COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER>
<TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
	        </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=5>  <IMG WIDTH=23 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69119" SRC="img1975.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1975.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=5>  <IMG WIDTH=24 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68911" SRC="img1926.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1926.gif"  ></TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
<P>
12 下一页
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -