📄 page57.html
字号:
<HTML><HEAD><TITLE>Projects</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html1856" HREF="page58.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1854" HREF="page36.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1850" HREF="page56.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1858" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION002400000000000000000">Projects</A></H1><P><OL><LI> Write a non-recursive method to compute the factorial of <I>n</I> according to Equation <A HREF="page42.html#eqnmodelfactorial"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. Calculate the running time predicted by the detailed model given in Section <A HREF="page37.html#secmodeldetailed"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and the simplified model given in Section <A HREF="page49.html#secmodelsimplified"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> Write a non-recursive method to compute <IMG WIDTH=17 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline58189" SRC="img156.gif" > according to Equation <A HREF="page54.html#eqnmodelpow"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. Calculate the running time predicted by the detailed model given in Section <A HREF="page37.html#secmodeldetailed"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and the simplified model given in Section <A HREF="page49.html#secmodelsimplified"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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=35 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57635" SRC="img7.gif" >, <IMG WIDTH=33 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57637" SRC="img8.gif" >, <IMG WIDTH=16 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline57647" SRC="img10.gif" >, <IMG WIDTH=16 HEIGHT=10 ALIGN=MIDDLE ALT="tex2html_wrap_inline57649" SRC="img11.gif" >, <IMG WIDTH=15 HEIGHT=12 ALIGN=MIDDLE ALT="tex2html_wrap_inline57651" SRC="img12.gif" >, <IMG WIDTH=16 HEIGHT=13 ALIGN=MIDDLE ALT="tex2html_wrap_inline57653" SRC="img13.gif" >, <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57655" SRC="img14.gif" >, <IMG WIDTH=26 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57659" SRC="img16.gif" >, <IMG WIDTH=42 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57661" SRC="img17.gif" >, <IMG WIDTH=29 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58033" SRC="img126.gif" >, and <IMG WIDTH=18 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57695" SRC="img31.gif" >) for the machine on which it is run.<LI> Using the program written for Project <A HREF="page57.html#projectmodeliii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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="page39.html#progexamplea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, <A HREF="page41.html#progexampleb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page42.html#progexamplec"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and compare the measured results with those predicted by Equations <A HREF="page39.html#eqnmodelsumc"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, <A HREF="page41.html#eqnmodelhornerc"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page43.html#eqnmodelfactorialc"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (respectively).<LI> Given a sequence of <I>n</I> integers, <IMG WIDTH=121 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58459" SRC="img229.gif" >, and a small positive integer <I>k</I>, write an algorithm to compute <P> <IMG WIDTH=282 HEIGHT=46 ALIGN=BOTTOM ALT="displaymath58429" SRC="img230.gif" ><P> <em>without multiplication</em>. <b>Hint</b>: Use Horner's rule and bitwise shifts.<LI> Verify Equation <A HREF="page45.html#eqnmodelprob"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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_inline58465" SRC="img231.gif" >. For each sequence, test the hypothesis that the probability that <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57849" SRC="img78.gif" > is larger than all its predecessors in the sequence is <IMG WIDTH=96 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58469" SRC="img232.gif" >. (For a good source of random numbers, see Section <A HREF="page465.html#secalgsrng"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).</OL><P><HR><A NAME="tex2html1856" HREF="page58.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1854" HREF="page36.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1850" HREF="page56.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1858" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -