page460.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 119 行
HTML
119 行
<HTML><HEAD><TITLE>Example-Computing Binomial Coefficients</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="tex2html6468" HREF="page461.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6466" HREF="page458.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6460" HREF="page459.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6470" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0014420000000000000000">Example-Computing Binomial Coefficients</A></H2><A NAME="secalgsbinom"> </A><P>Consider the problem of computingthe <em>binomial coefficient</em><P><A NAME="eqnalgsbinomi"> </A> <IMG WIDTH=500 HEIGHT=39 ALIGN=BOTTOM ALT="equation33142" SRC="img1838.gif" ><P>given non-negative integers <I>n</I> and <I>m</I> (see Theorem <A HREF="page369.html#theorempqueuesbinom"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).<P>The problem with implementing directly Equation <A HREF="page460.html#eqnalgsbinomi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>is that the factorials grow quickly with increasing <I>n</I> and <I>m</I>.For example, <IMG WIDTH=169 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline68225" SRC="img1839.gif" >.Therefore, it is not possible to represent <I>n</I>! for <IMG WIDTH=47 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68229" SRC="img1840.gif" >using 32-bit integers.Nevertheless it is possibleto represent the binomial coefficients <IMG WIDTH=22 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline68231" SRC="img1841.gif" > up to <I>n</I>=33without overflowing.For example, <IMG WIDTH=175 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline68235" SRC="img1842.gif" >.<P>Consider the following <em>recursive</em> definitionof the binomial coefficients:<P><A NAME="eqnalgsbinomii"> </A> <IMG WIDTH=500 HEIGHT=67 ALIGN=BOTTOM ALT="equation33158" SRC="img1843.gif" ><P>This formulation does not require the computation of factorials.In fact, the only computation needed is addition.<P>If we implement Equation <A HREF="page460.html#eqnalgsbinomii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> directly as a recursive method,we get a method whose running time is given by<P> <IMG WIDTH=468 HEIGHT=67 ALIGN=BOTTOM ALT="displaymath68215" SRC="img1844.gif" ><P>which is very similar to Equation <A HREF="page460.html#eqnalgsbinomii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.In fact, we can show that <IMG WIDTH=125 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline68237" SRC="img1845.gif" >which (by Equation <A HREF="page460.html#eqnalgsbinomi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>) is not a very good running time at all!Again the problem with the direct recursive implementation is thatit does far more work than is needed because it solves the same subproblem many times.<P>An alternative to the top-down recursive implementationis to do the calculation from the bottom up.In order to do this we compute the series of sequences<P> <IMG WIDTH=500 HEIGHT=133 ALIGN=BOTTOM ALT="eqnarray33178" SRC="img1846.gif" ><P>Notice that we can compute <IMG WIDTH=28 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68197" SRC="img1834.gif" > from the information containedin <IMG WIDTH=13 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67035" SRC="img1616.gif" > simply by using Equation <A HREF="page460.html#eqnalgsbinomii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Table <A HREF="page460.html#tblpascal"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows the sequence in tabular form--the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > row of the table corresponds the sequence <IMG WIDTH=13 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67035" SRC="img1616.gif" >.This tabular representation of the binomial coefficients isknown as <em>Pascal's triangle</em><A NAME=33205> </A>.<A NAME="tex2html825" HREF="footnode.html#33459"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A><P><P><A NAME="33209"> </A><P> <A NAME="tblpascal"> </A> <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=9 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><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>n</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=19 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline68249" SRC="img1847.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=18 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline68251" SRC="img1848.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=19 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline68253" SRC="img1849.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=18 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline68255" SRC="img1850.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=19 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline68257" SRC="img1851.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=18 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline68259" SRC="img1852.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=19 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline68261" SRC="img1853.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=18 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline68263" SRC="img1854.gif" > </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>0 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </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></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </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></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </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></TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </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></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 6 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 6 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 6 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 15 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 20 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 15 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 6 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 7 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 7 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 21 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 35 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 35 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 21 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 7 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD></TR></TBODY><CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Pascal's triangle.</CAPTION></TABLE></P></DIV><P><P>Program <A HREF="page460.html#progexamples"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the method <tt>binom</tt>which takes two integer arguments <I>n</I> and <I>m</I>and computes the binomial coefficient <IMG WIDTH=22 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline68231" SRC="img1841.gif" >by computing Pascal's triangle.According to Equation <A HREF="page460.html#eqnalgsbinomii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,each subsequent row depends only on the preceding row--it is only necessary to keep track of one row of data.The implementation shown uses an array of length <I>n</I>to represent a row of Pascal's triangle.Consequently, instead of a table of size <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" >,the algorithm gets by with <I>O</I>(<I>n</I>) space.The implementation has been coded carefullyso that the computation can be done in place.That is, the elements of <IMG WIDTH=28 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68197" SRC="img1834.gif" > are computedin reverse so that they can be written over the elements of <IMG WIDTH=13 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67035" SRC="img1616.gif" >that are no longer needed.<P><P><A NAME="33242"> </A><A NAME="progexamples"> </A> <IMG WIDTH=575 HEIGHT=200 ALIGN=BOTTOM ALT="program33239" SRC="img1855.gif" ><BR><STRONG>Program:</STRONG> Dynamic programming example--computing Binomial coefficients.<BR><P><P>The worst-case running time of the <tt>binom</tt>method given in Program <A HREF="page460.html#progexamples"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is clearly <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" >.<P><HR><A NAME="tex2html6468" HREF="page461.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6466" HREF="page458.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6460" HREF="page459.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6470" 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 + -
显示快捷键?