page467.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 119 行 · 第 1/2 页
HTML
119 行
<HTML>
<HEAD>
<TITLE>Example-Computing Binomial Coefficients</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="tex2html7691" HREF="page468.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page468.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="tex2html7689" HREF="page465.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page465.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="tex2html7683" HREF="page466.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page466.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="tex2html7693" 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="tex2html7694" 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>
<H2><A NAME="SECTION0015420000000000000000">Example-Computing Binomial Coefficients</A></H2>
<A NAME="secalgsbinom"> </A>
<P>
Consider the problem of computing
the <em>binomial coefficient</em>
<P><A NAME="eqnalgsbinomi"> </A> <IMG WIDTH=500 HEIGHT=38 ALIGN=BOTTOM ALT="equation33331" SRC="img1947.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1947.gif" ><P>
given non-negative integers <I>n</I> and <I>m</I> (see Theorem <A HREF="page371.html#theorempqueuesbinom" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page371.html#theorempqueuesbinom"><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>
The problem with implementing directly Equation <A HREF="page467.html#eqnalgsbinomi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page467.html#eqnalgsbinomi"><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>
is that the factorials grow quickly with increasing <I>n</I> and <I>m</I>.
For example, <IMG WIDTH=170 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline69015" SRC="img1948.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1948.gif" >.
Therefore, it is not possible to represent <I>n</I>! for <IMG WIDTH=46 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline69019" SRC="img1949.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1949.gif" >
using unsigned 32-bit integers.
Nevertheless it is possible
to represent the binomial coefficients <IMG WIDTH=21 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline69021" SRC="img1950.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1950.gif" > up to <I>n</I>=34
without overflowing.
For example, <IMG WIDTH=176 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline69025" SRC="img1951.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1951.gif" >.
<P>
Consider the following <em>recursive</em> definition
of the binomial coefficients:
<P><A NAME="eqnalgsbinomii"> </A> <IMG WIDTH=500 HEIGHT=66 ALIGN=BOTTOM ALT="equation33347" SRC="img1952.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1952.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="page467.html#eqnalgsbinomii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page467.html#eqnalgsbinomii"><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> directly as a recursive function,
we get a routine whose running time is given by
<P> <IMG WIDTH=468 HEIGHT=66 ALIGN=BOTTOM ALT="displaymath69005" SRC="img1953.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1953.gif" ><P>
which is very similar to Equation <A HREF="page467.html#eqnalgsbinomii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page467.html#eqnalgsbinomii"><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>.
In fact, we can show that <IMG WIDTH=124 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline69027" SRC="img1954.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1954.gif" >
which (by Equation <A HREF="page467.html#eqnalgsbinomi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page467.html#eqnalgsbinomi"><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>) is not a very good running time at all!
Again the problem with the direct recursive implementation is that
it does far more work than is needed because
it solves the same subproblem many times.
<P>
An alternative to the top-down recursive implementation
is to do the calculation from the bottom up.
In order to do this we compute the series of sequences
<P> <IMG WIDTH=500 HEIGHT=132 ALIGN=BOTTOM ALT="eqnarray33367" SRC="img1955.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1955.gif" ><P>
Notice that we can compute <IMG WIDTH=29 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68987" SRC="img1943.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1943.gif" > from the information contained
in <IMG WIDTH=12 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67646" SRC="img1662.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1662.gif" > simply by using Equation <A HREF="page467.html#eqnalgsbinomii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page467.html#eqnalgsbinomii"><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>.
Table <A HREF="page467.html#tblpascal" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page467.html#tblpascal"><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> shows the sequence in tabular form--the <IMG WIDTH=17 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58387" SRC="img77.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img77.gif" > row of the table corresponds the sequence <IMG WIDTH=12 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67646" SRC="img1662.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1662.gif" >.
This tabular representation of the binomial coefficients is
known as <em>Pascal's triangle</em><A NAME=33394> </A>.<A NAME="tex2html888" HREF="footnode.html#33649" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/footnode.html#33649"><IMG ALIGN=BOTTOM ALT="gif" SRC="foot_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/foot_motif.gif"></A>
<P>
<P><A NAME="33398"> </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>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?