page189.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 171 行
HTML
171 行
<HTML><HEAD><TITLE>Applications</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="tex2html3380" HREF="page190.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3378" HREF="page169.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3374" HREF="page188.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3382" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION007140000000000000000">Applications</A></H2><A NAME="seclistsapp1"> </A><P>The applications of lists and ordered lists are myriad.In this section we will consider only one--the use of an ordered list to represent a polynomial.In general, an <IMG WIDTH=21 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57913" SRC="img94.gif" >-order polynomial in <I>x</I>,for non-negative integer <I>n</I>, has the form<P> <IMG WIDTH=388 HEIGHT=44 ALIGN=BOTTOM ALT="displaymath61181" SRC="img768.gif" ><P>where <IMG WIDTH=47 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline61201" SRC="img769.gif" >.The term <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57849" SRC="img78.gif" > is the <em>coefficient</em> of the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > power of <I>x</I>.We shall assume that the coefficients are real numbers.<P>An alternative representation for such a polynomial consistsof a sequence of ordered pairs:<P> <IMG WIDTH=371 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath61182" SRC="img770.gif" ><P>Each ordered pair, <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61209" SRC="img771.gif" >,corresponds to the term <IMG WIDTH=27 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline61211" SRC="img772.gif" > of the polynomial.That is, the ordered pair is comprised of the coefficient of the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > termtogether with the subscript of that term, <I>i</I>.For example, the polynomial <IMG WIDTH=111 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline61217" SRC="img773.gif" >can be represented by the sequence <IMG WIDTH=159 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61219" SRC="img774.gif" >.<P>Consider now the <IMG WIDTH=35 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline61221" SRC="img775.gif" >-order polynomial <IMG WIDTH=55 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline61223" SRC="img776.gif" >.Clearly, there are only two nonzero coefficients: <IMG WIDTH=57 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline61225" SRC="img777.gif" > and <IMG WIDTH=44 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline61227" SRC="img778.gif" >.The advantage of using the sequence of ordered pairs to representsuch a polynomial is that we can omit from the sequencethose pairs that have a zero coefficient.We represent the polynomial <IMG WIDTH=55 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline61223" SRC="img776.gif" > by the sequence <IMG WIDTH=109 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61231" SRC="img779.gif" ><P>Now that we have a way to represent polynomials,we can consider various operations on them.For example, consider the polynomial<P> <IMG WIDTH=304 HEIGHT=44 ALIGN=BOTTOM ALT="displaymath61183" SRC="img780.gif" ><P>We can compute its <em>derivative</em><A NAME=9677> </A> with respect to <I>x</I>by <em>differentiating</em><A NAME=9679> </A>each of the terms to get<P> <IMG WIDTH=307 HEIGHT=46 ALIGN=BOTTOM ALT="displaymath61184" SRC="img781.gif" ><P>where <IMG WIDTH=108 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61235" SRC="img782.gif" >.In terms of the corresponding sequences,if <I>p</I>(<I>x</I>) is represented by the sequence<P> <IMG WIDTH=408 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath61185" SRC="img783.gif" ><P>then its derivative is the sequence<P> <IMG WIDTH=448 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath61186" SRC="img784.gif" ><P><P>This result suggests a very simple algorithm to differentiatea polynomial which is represented by a sequence of ordered pairs:<OL><LI> Drop the ordered pair that has a zero exponent.<LI> For every other ordered pair, multiply the coefficient by the exponent, and then subtract one from the exponent.</OL>Since the representation of an <IMG WIDTH=21 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57913" SRC="img94.gif" >-order polynomialhas at most <I>n</I>+1 ordered pairs,and since a constant amount of work is necessary for each ordered pair,this is inherently an <IMG WIDTH=32 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60149" SRC="img523.gif" > algorithm.<P>Of course, the worst-case running time of the polynomial differentiationwill depend on the way that the sequence of ordered pairs is implemented.We will now consider an implementation that makes use ofthe <tt>OrderedListAsLinkedList</tt> class.To begin with, we need a class to represent the terms of the polynomial.Program <A HREF="page189.html#progpolynomialb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the definition ofthe <tt>Term</tt> class and several of its methods.<P><P><A NAME="9925"> </A><A NAME="progpolynomialb"> </A> <IMG WIDTH=575 HEIGHT=485 ALIGN=BOTTOM ALT="program9689" SRC="img785.gif" ><BR><STRONG>Program:</STRONG> <tt>Polynomial.Term</tt> class.<BR><P><P>Each <tt>Term</tt> instance has two instance attributes,<tt>_coefficient</tt> and <tt>_exponent</tt>,which correspond to the elements of the ordered pair as discussed above.The former is a <tt>float</tt> and the latter, an <tt>int</tt>.<P>The <tt>Term</tt> class extends the abstract <tt>Object</tt> classintroduced in Program <A HREF="page116.html#progobjecta"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Program <A HREF="page189.html#progpolynomialb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines three methods:<tt>__init__</tt>, <tt>_compareTo</tt>, and <tt>differentiate</tt>.In addition to <tt>self</tt>,the <tt>__init__</tt> method simply takes a pair of arguments andinitializes the corresponding instance attributes accordingly.<P>The <tt>_compareTo</tt> method is used to compare two <tt>Term</tt> instances.Consider two terms , <IMG WIDTH=21 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline61245" SRC="img786.gif" > and <IMG WIDTH=20 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline61247" SRC="img787.gif" >.We define the relation <IMG WIDTH=10 HEIGHT=19 ALIGN=MIDDLE ALT="tex2html_wrap_inline61249" SRC="img788.gif" > on terms of a polynomial as follows:<P> <IMG WIDTH=384 HEIGHT=19 ALIGN=BOTTOM ALT="displaymath61187" SRC="img789.gif" ><P>Note that the relation <IMG WIDTH=10 HEIGHT=19 ALIGN=MIDDLE ALT="tex2html_wrap_inline61249" SRC="img788.gif" > does not depend on the value of the variable <I>x</I>.The <tt>_compareTo</tt> method implements the <IMG WIDTH=10 HEIGHT=19 ALIGN=MIDDLE ALT="tex2html_wrap_inline61249" SRC="img788.gif" > relation.<P>Finally, the <tt>differentiate</tt> method does what its name says:It differentiates a term with respect to <I>x</I>.Given a term such as <IMG WIDTH=41 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61259" SRC="img790.gif" >, it computes the result (0,0);and given a term such as <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61209" SRC="img771.gif" > where <I>i</I><I>></I>0,it computes the result <IMG WIDTH=70 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61267" SRC="img791.gif" >.<P>We now consider the representation of a polynomial.Program <A HREF="page189.html#progpolynomiala"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the abstract <tt>Polynomial</tt> class.The class comprises three abstract methods--<tt>addTerm</tt>, <tt>differentiate</tt>, and <tt>__add__</tt>.The <tt>addTerm</tt> method is used to add terms to a polynomial.The <tt>differentiate</tt> method differentiates the polynomial.The <tt>__add__</tt> method is used to compute the sum of two polynomials.<P><P><A NAME="9930"> </A><A NAME="progpolynomiala"> </A> <IMG WIDTH=575 HEIGHT=352 ALIGN=BOTTOM ALT="program9732" SRC="img792.gif" ><BR><STRONG>Program:</STRONG> Abstract <tt>Polynomial</tt> class.<BR><P><P>Program <A HREF="page189.html#progpolynomialAsOrderedLista"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>introduces the <tt>PolynomialAsOrderedList</tt> class.This concrete class extends the abstract <tt>Polynomial</tt> class.It has a single instance attribute called <tt>_list</tt>.In this case <tt>_list</tt>,an instance of the <tt>OrderedListAsLinkedList</tt> class,is used to contain the terms of the polynomial.<P><P><A NAME="9936"> </A><A NAME="progpolynomialAsOrderedLista"> </A> <IMG WIDTH=575 HEIGHT=371 ALIGN=BOTTOM ALT="program9753" SRC="img793.gif" ><BR><STRONG>Program:</STRONG> <tt>PolynomialAsOrderedList</tt> class.<BR><P><P>Program <A HREF="page189.html#progpolynomiald"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the method <tt>differentiate</tt>which has the effect of changing the polynomial to itsderivative with respect to <I>x</I>.To compute this derivative,it is necessary to call the <tt>differentiate</tt> methodof the <tt>Term</tt> class for each term in the polynomial.Since the polynomial is implemented as a container,there is an <tt>accept</tt> method which can be usedto perform a given operation on all of the objects in that container.In this case, we define a visitor, <tt>DifferentiatingVisitor</tt>,which assumes its argument is an instance of the <tt>Term</tt> classand differentiates it.<P><P><A NAME="9943"> </A><A NAME="progpolynomiald"> </A> <IMG WIDTH=575 HEIGHT=352 ALIGN=BOTTOM ALT="program9777" SRC="img794.gif" ><BR><STRONG>Program:</STRONG> <tt>Polynomial</tt> class <tt>differentiate</tt> method.<BR><P><P>After the terms in the polynomial have been differentiated,it is necessary to check for the term (0,0)which arises from differentiating <IMG WIDTH=41 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61259" SRC="img790.gif" >.The <tt>find</tt> method is used to locate the term,and if one is found the <tt>withdraw</tt> method is used to remove it.<P>The analysis of the running timeof the polynomial <tt>differentiate</tt> method is straightforward.The running time required to differentiate a term is clearly <I>O</I>(1).So too is the running time of the <tt>visit</tt>method of the <tt>DifferentiatingVisitor</tt>.The latter method is called once for each contained object.In the worst case, given an <IMG WIDTH=21 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57913" SRC="img94.gif" >-order polynomial,there are <I>n</I>+1 terms.Therefore, the time required to differentiate the terms is <I>O</I>(<I>n</I>).Locating the zero term is <I>O</I>(<I>n</I>) in the worst case,and so too is deleting it.Therefore, the total running time required to differentiatea <IMG WIDTH=21 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57913" SRC="img94.gif" >-order polynomial is <I>O</I>(<I>n</I>).<P><HR><A NAME="tex2html3380" HREF="page190.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3378" HREF="page169.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3374" HREF="page188.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3382" 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 + -
显示快捷键?