page48.html

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

HTML
85 行
字号 
<HTML>
<HEAD>
<TITLE>An Example-Geometric Series Summation</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="tex2html2487" HREF="page49.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page49.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="tex2html2485" 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="tex2html2479" HREF="page47.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page47.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="tex2html2489" 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="tex2html2490" 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="SECTION003210000000000000000">An Example-Geometric Series Summation</A></H2>
<A NAME="secmodelgeometric">&#160;</A>
<P>
In this section we consider the running time
of a program to compute the following
<em>geometric series summation</em><A NAME=810>&#160;</A>.
I.e., given a value <I>x</I> and non-negative integer <I>n</I>,
we wish to compute the summation
<P> <IMG WIDTH=271 HEIGHT=43 ALIGN=BOTTOM ALT="displaymath58625" SRC="img135.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img135.gif"  ><P>
An algorithm to compute this summation
is given in 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>
<P><A NAME="1148">&#160;</A><A NAME="proggeometricc">&#160;</A> <IMG WIDTH=575 HEIGHT=238 ALIGN=BOTTOM ALT="program814" SRC="img137.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img137.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"  ><BR>
<P>
<P>
Table&nbsp;<A HREF="page48.html#tblgeometricc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page48.html#tblgeometricc"><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 time,
as predicted by the simplified model,
for each of the executable statements in 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>
<P><A NAME="1150">&#160;</A>
<P>
    <A NAME="tblgeometricc">&#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> 
	    6 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2(<I>n</I>+1) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    7a </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2(<I>n</I>+1) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    7b </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=92 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline58645" SRC="img138.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img138.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    7c </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=57 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline58647" SRC="img139.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img139.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    8 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=57 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline58647" SRC="img139.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img139.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    9 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4(<I>n</I>+1) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    10 </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>  <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"  > </TD></TR>
</TBODY>
<CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Computing the running time of 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></CAPTION></TABLE>
</P></DIV><P>
<P>
In order to calculate the total cycle counts,
we need to evaluate the two series summations
 <IMG WIDTH=82 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline58657" SRC="img141.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img141.gif"  > and  <IMG WIDTH=45 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline58659" SRC="img142.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img142.gif"  >.
Both of these are
<em>arithmetic series summations</em><A NAME=848>&#160;</A>.
In the next section we show
that the sum of the series  <IMG WIDTH=70 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58661" SRC="img143.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img143.gif"  > is <I>n</I>(<I>n</I>+1)/2.
Using this result we can sum the cycle counts
given in Table&nbsp;<A HREF="page48.html#tblgeometricc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page48.html#tblgeometricc"><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 arrive at the total running time of
 <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>
<HR><A NAME="tex2html2487" HREF="page49.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page49.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="tex2html2485" 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="tex2html2479" HREF="page47.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page47.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="tex2html2489" 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="tex2html2490" 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>

page48.html - 源码说明

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

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

⌨️ 快捷键说明

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