page50.html

来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 85 行

HTML
85 行
字号 
<HTML>
<HEAD>
<TITLE>Example-Geometric Series Summation 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="tex2html2511" HREF="page51.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page51.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="tex2html2509" 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="tex2html2503" HREF="page49.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page49.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="tex2html2513" 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="tex2html2514" 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="SECTION003230000000000000000">Example-Geometric Series Summation Again</A></H2>
<P>
<A NAME="secmodelgeometric2">&#160;</A>
<P>
In this example we revisit the problem of computing a
<em>geometric series summation</em><A NAME=898>&#160;</A>.
We have already seen an algorithm to compute this summation
in Section&nbsp;<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> (Program&nbsp;<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>).
This algorithm was shown to take  <IMG WIDTH=112 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline58655" SRC="img140.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img140.gif"  > cycles.
<P>
The problem of computing the geometric series summation
is identical to that of computing the value of a polynomial
in which all of the coefficients are one.
This suggests that we could make use of
<em>Horner's rule</em><A NAME=906>&#160;</A>
as discussed in Section&nbsp;<A HREF="page39.html#secmodelhorner" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page39.html#secmodelhorner"><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>.
An algorithm to compute a geometric series summation
using Horner's rule is given in Program&nbsp;<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>
<P><A NAME="1151">&#160;</A><A NAME="proggeometric2c">&#160;</A> <IMG WIDTH=575 HEIGHT=143 ALIGN=BOTTOM ALT="program909" SRC="img153.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img153.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 Horner's rule<BR>
<P>
<P>
The executable statements in Program&nbsp;<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>
comprise lines&nbsp;3-6.
Table&nbsp;<A HREF="page50.html#tblgeometric2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page50.html#tblgeometric2c"><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> gives the running times,
as given by the simplified model,
for each of these statements.
<P>
<P><A NAME="1153">&#160;</A>
<P>
    <A NAME="tblgeometric2c">&#160;</A>
    <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=2 BORDER FRAME=HSIDES RULES=GROUPS>
<COL ALIGN=CENTER><COL ALIGN=CENTER>
<TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
	    statement </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> time </TD></TR>
</TBODY><TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    4a </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    4b </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3(<I>n</I>+2) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    4c </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4(<I>n</I>+1) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 6(<I>n</I>+1) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    6 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD></TR>
</TBODY><TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>TOTAL </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 13<I>n</I>+22 </TD></TR>
</TBODY>
<CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Computing the running time
	of Program&nbsp;<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></CAPTION></TABLE>
</P></DIV><P>
<P>
In Programs&nbsp;<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&nbsp;<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>
we have seen two different algorithms to compute the same
geometric series summation.
We determined the running time of the former to be
 <IMG WIDTH=112 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline58655" SRC="img140.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img140.gif"  > cycles
and of the latter to be 13<I>n</I>+22 cycles.
In particular, note that for all non-negative values of <I>n</I>,
 <IMG WIDTH=206 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline58719" SRC="img154.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img154.gif"  >.
Hence, according to our simplified model of the computer,
Program&nbsp;<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>, which uses Horner's rule,
<em>always</em> runs faster than Program&nbsp;<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>!
<P>
<HR><A NAME="tex2html2511" HREF="page51.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page51.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="tex2html2509" 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="tex2html2503" HREF="page49.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page49.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="tex2html2513" 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="tex2html2514" 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> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright &#169; 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.

</ADDRESS>
</BODY>
</HTML>

page50.html - 源码说明

本页面展示了「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」中的 page50.html 源码文件，采用 HTML 编程语言编写，共 85 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫下载站收录了大量与jkhrjqwhrwq相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

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