📄 page54.html
字号:
<HTML>
<HEAD>
<TITLE>Exercises</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="tex2html2557" HREF="page55.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page55.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="tex2html2555" HREF="page34.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page34.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="tex2html2549" HREF="page53.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page53.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="tex2html2559" 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="tex2html2560" 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>
<H1><A NAME="SECTION003300000000000000000">Exercises</A></H1>
<P>
<OL><LI><A NAME="exercisemodeli"> </A>
Determine the running times predicted by the
detailed model of the computer given in Section <A HREF="page35.html#secmodeldetailed" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page35.html#secmodeldetailed"><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>
for each of the following program fragments:
<OL><LI>
<PRE>for (unsigned int i = 0; i < n; ++i)
++k;</PRE><LI>
<PRE>for (unsigned int i = 1U; i < n; i *= 2U)
++k;</PRE><LI>
<PRE>for (unsigned int i = n - 1U; i != 0; i /= 2U)
++k;</PRE><LI>
<PRE>for (unsigned int i = 0; i < n; ++i)
if (i % 2 == 0)
++k;</PRE><LI>
<PRE>for (unsigned int i = 0; i < n; ++i)
for (unsigned int j = 0; j < n; ++j)
++k;</PRE><LI>
<PRE>for (unsigned int i = 0; i < n; ++i)
for (unsigned int j = i; j < n; ++j)
++k;</PRE><LI>
<PRE>for (unsigned int i = 0; i < n; ++i)
for (unsigned int j = 0; j < i * i; ++j)
++k;</PRE>
</OL><LI>
Repeat Exercise <A HREF="page54.html#exercisemodeli" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page54.html#exercisemodeli"><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 time using the simplified model of the computer
given in Section <A HREF="page47.html#secmodelsimplified" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page47.html#secmodelsimplified"><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>.<LI>
Prove by induction the following summation formulas:
<OL><LI> <IMG WIDTH=113 HEIGHT=50 ALIGN=MIDDLE ALT="tex2html_wrap_inline58937" SRC="img211.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img211.gif" ><LI> <IMG WIDTH=177 HEIGHT=50 ALIGN=MIDDLE ALT="tex2html_wrap_inline58939" SRC="img212.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img212.gif" ><LI> <IMG WIDTH=134 HEIGHT=50 ALIGN=MIDDLE ALT="tex2html_wrap_inline58941" SRC="img213.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img213.gif" ></OL><LI>
Evaluate each of the following series summations:
<OL><LI> <IMG WIDTH=36 HEIGHT=50 ALIGN=MIDDLE ALT="tex2html_wrap_inline58943" SRC="img214.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img214.gif" ><LI> <IMG WIDTH=63 HEIGHT=53 ALIGN=MIDDLE ALT="tex2html_wrap_inline58945" SRC="img215.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img215.gif" ><LI> <IMG WIDTH=63 HEIGHT=53 ALIGN=MIDDLE ALT="tex2html_wrap_inline58947" SRC="img216.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img216.gif" ><LI> <IMG WIDTH=51 HEIGHT=49 ALIGN=MIDDLE ALT="tex2html_wrap_inline58949" SRC="img217.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img217.gif" ></OL><LI>
Show that <IMG WIDTH=101 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline58951" SRC="img218.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img218.gif" >,
for <IMG WIDTH=65 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline58953" SRC="img219.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img219.gif" >.
<b>Hint</b>: Let <IMG WIDTH=91 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline58955" SRC="img220.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img220.gif" > and show
that <IMG WIDTH=162 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58957" SRC="img221.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img221.gif" >.<LI>
Show that <IMG WIDTH=95 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline58959" SRC="img222.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img222.gif" >.
<b>Hint</b>: Let <IMG WIDTH=104 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline58961" SRC="img223.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img223.gif" > and show that
the difference <IMG WIDTH=61 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline58963" SRC="img224.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img224.gif" > is (approximately)
a geometric series summation.<LI>
Solve each of the following recurrences by repeated substitution:
<OL><LI>
<IMG WIDTH=214 HEIGHT=56 ALIGN=MIDDLE ALT="tex2html_wrap_inline58965" SRC="img225.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img225.gif" ><LI>
<IMG WIDTH=259 HEIGHT=56 ALIGN=MIDDLE ALT="tex2html_wrap_inline58967" SRC="img226.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img226.gif" ><LI>
<IMG WIDTH=222 HEIGHT=56 ALIGN=MIDDLE ALT="tex2html_wrap_inline58969" SRC="img227.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img227.gif" ><LI>
<IMG WIDTH=223 HEIGHT=56 ALIGN=MIDDLE ALT="tex2html_wrap_inline58971" SRC="img228.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img228.gif" ><LI>
<IMG WIDTH=202 HEIGHT=56 ALIGN=MIDDLE ALT="tex2html_wrap_inline58973" SRC="img229.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img229.gif" ><LI>
<IMG WIDTH=210 HEIGHT=56 ALIGN=MIDDLE ALT="tex2html_wrap_inline58975" SRC="img230.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img230.gif" ><LI>
<IMG WIDTH=212 HEIGHT=56 ALIGN=MIDDLE ALT="tex2html_wrap_inline58977" SRC="img231.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img231.gif" ></OL></OL><HR><A NAME="tex2html2557" HREF="page55.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page55.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="tex2html2555" HREF="page34.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page34.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="tex2html2549" HREF="page53.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page53.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="tex2html2559" 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="tex2html2560" 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 © 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>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -