page53.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 79 行 · 第 1/2 页
HTML
79 行
<HTML>
<HEAD>
<TITLE>Example-Geometric Series Summation Yet Again</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="tex2html2545" HREF="page54.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page54.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="tex2html2543" HREF="page47.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page47.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="tex2html2539" HREF="page52.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page52.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="tex2html2547" 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="tex2html2548" 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="SECTION003260000000000000000">Example-Geometric Series Summation Yet Again</A></H2>
<P>
In this example we consider the problem of computing a
<em>geometric series summation</em><A NAME=1077> </A>
for the last time.
We have already seen two algorithms to compute this summation
in Sections <A HREF="page48.html#secmodelgeometric" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page48.html#secmodelgeometric"><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> and <A HREF="page50.html#secmodelgeometric2" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page50.html#secmodelgeometric2"><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>
(Programs <A HREF="page48.html#proggeometricc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page48.html#proggeometricc"><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> and <A HREF="page50.html#proggeometric2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page50.html#proggeometric2c"><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>
An algorithm to compute a geometric series summation
using the closed-form expression (Equation <A HREF="page51.html#eqngeometric" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page51.html#eqngeometric"><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 given in Program <A HREF="page53.html#proggeometric3c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page53.html#proggeometric3c"><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>.
This algorithm makes use of Program <A HREF="page52.html#progpowerc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page52.html#progpowerc"><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> to compute <IMG WIDTH=32 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline58885" SRC="img203.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img203.gif" >.
<P>
<P><A NAME="1158"> </A><A NAME="proggeometric3c"> </A> <IMG WIDTH=575 HEIGHT=124 ALIGN=BOTTOM ALT="program1086" SRC="img204.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img204.gif" ><BR>
<STRONG>Program:</STRONG> Program to compute <IMG WIDTH=52 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline58631" SRC="img136.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img136.gif" > using the closed-form expression<BR>
<P>
<P>
To determine the average running time of Program <A HREF="page53.html#proggeometric3c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page53.html#proggeometric3c"><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>
we will make use of Equation <A HREF="page52.html#eqnmodelpower" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page52.html#eqnmodelpower"><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>,
which gives the average running time for the <tt>Power</tt> function
which is called on line 5.
In this case, the arguments are <I>x</I> and <I>n</I>+1,
so the running time of the call to <tt>Power</tt> is
<IMG WIDTH=173 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline58893" SRC="img205.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img205.gif" >.
Adding to this the additional work done on line 5 gives
the average running time for Program <A HREF="page53.html#proggeometric3c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page53.html#proggeometric3c"><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> <IMG WIDTH=370 HEIGHT=17 ALIGN=BOTTOM ALT="displaymath58883" SRC="img206.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img206.gif" ><P>
<P>
The running times of the three programs
which compute the geometric series summation
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?