📄 page55.html
字号:
<HTML>
<HEAD>
<TITLE>Projects</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="tex2html2567" HREF="page56.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page56.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="tex2html2565" 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="tex2html2561" HREF="page54.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page54.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="tex2html2569" 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="tex2html2570" 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="SECTION003400000000000000000">Projects</A></H1>
<P>
<OL><LI>
Write a non-recursive routine
to compute the factorial of <I>n</I>
according to Equation <A HREF="page40.html#eqnmodelfactorial" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page40.html#eqnmodelfactorial"><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>.
Calculate the running time predicted by
the detailed model 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>
and the simplified model 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>
Write a non-recursive routine
to compute <IMG WIDTH=15 HEIGHT=10 ALIGN=BOTTOM ALT="tex2html_wrap_inline58739" SRC="img159.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img159.gif" > according to Equation <A HREF="page52.html#eqnmodelpow" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page52.html#eqnmodelpow"><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>.
Calculate the running time predicted by
the detailed model 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>
and the simplified model 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><A NAME="projectmodeliii"> </A>
Write a program that determines the values
of the timing parameters of the detailed model
( <IMG WIDTH=33 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58177" SRC="img7.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img7.gif" >, <IMG WIDTH=33 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58179" SRC="img8.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img8.gif" >, <IMG WIDTH=16 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline58189" SRC="img10.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img10.gif" >, <IMG WIDTH=15 HEIGHT=11 ALIGN=MIDDLE ALT="tex2html_wrap_inline58191" SRC="img11.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img11.gif" >, <IMG WIDTH=15 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58193" SRC="img12.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img12.gif" >, <IMG WIDTH=15 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58195" SRC="img13.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img13.gif" >,
<IMG WIDTH=15 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58197" SRC="img14.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img14.gif" >, <IMG WIDTH=26 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58201" SRC="img16.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img16.gif" >, <IMG WIDTH=42 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58203" SRC="img17.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img17.gif" >, <IMG WIDTH=23 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58579" SRC="img128.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img128.gif" >, <IMG WIDTH=41 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58581" SRC="img129.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img129.gif" >,
and <IMG WIDTH=19 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58237" SRC="img31.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img31.gif" >)
for the machine on which it is run.<LI>
Using the program written for Project <A HREF="page55.html#projectmodeliii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page55.html#projectmodeliii"><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>,
determine the timing parameters of the detailed model
for your computer.
Then, measure the actual running times
of Programs <A HREF="page37.html#progsumc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page37.html#progsumc"><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>, <A HREF="page39.html#proghornerc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page39.html#proghornerc"><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="page40.html#progfactorialc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page40.html#progfactorialc"><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 compare the measured results with those predicted by
Equations <A HREF="page37.html#eqnmodelsumc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page37.html#eqnmodelsumc"><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>, <A HREF="page39.html#eqnmodelhornerc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page39.html#eqnmodelhornerc"><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="page41.html#eqnmodelfactorialc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page41.html#eqnmodelfactorialc"><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> (respectively).<LI>
Given a sequence of <I>n</I> integers, <IMG WIDTH=122 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59011" SRC="img232.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img232.gif" >,
and a small positive integer <I>k</I>,
write an algorithm to compute
<P> <IMG WIDTH=282 HEIGHT=46 ALIGN=BOTTOM ALT="displaymath58979" SRC="img233.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img233.gif" ><P>
<em>without multiplication</em>.
<b>Hint</b>: Use Horner's rule and bitwise shifts.<LI>
Verify Equation <A HREF="page43.html#eqnmodelprob" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page43.html#eqnmodelprob"><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> experimentally as follows:
Generate a large number of random sequences of length <I>n</I>,
<IMG WIDTH=144 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59017" SRC="img234.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img234.gif" >.
For each sequence, test the hypothesis that the probability
that <IMG WIDTH=11 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58389" SRC="img78.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img78.gif" > is larger than all its predecessors in the sequence
is <IMG WIDTH=96 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59021" SRC="img235.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img235.gif" >.
(For a good source of random numbers, see Section <A HREF="page472.html#secalgsrng" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page472.html#secalgsrng"><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>).
</OL>
<P>
<HR><A NAME="tex2html2567" HREF="page56.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page56.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="tex2html2565" 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="tex2html2561" HREF="page54.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page54.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="tex2html2569" 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="tex2html2570" 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 + -