page79.html

来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 132 行

HTML
132 行
字号 
<HTML><HEAD><TITLE>Exercises</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="tex2html2114" HREF="page80.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2112" HREF="page58.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2106" HREF="page78.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html2116" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION003500000000000000000">Exercises</A></H1><P><OL><LI>	Consider the function  <IMG WIDTH=133 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline60231" SRC="img544.gif"  >.	Using Definition&nbsp;<A HREF="page59.html#defnbigoh"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> show that  <IMG WIDTH=93 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58535" SRC="img241.gif"  >.<LI>	Consider the function  <IMG WIDTH=133 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline60231" SRC="img544.gif"  >.	Using Definition&nbsp;<A HREF="page68.html#defnomega"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> show that  <IMG WIDTH=91 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59395" SRC="img408.gif"  >.<LI>	Consider the functions  <IMG WIDTH=133 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline60231" SRC="img544.gif"  > and  <IMG WIDTH=123 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60241" SRC="img545.gif"  >.	Using Theorem&nbsp;<A HREF="page62.html#theoremii"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> show that  <IMG WIDTH=142 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline60243" SRC="img546.gif"  >.<LI>	Consider the functions  <IMG WIDTH=75 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline60245" SRC="img547.gif"  > and  <IMG WIDTH=84 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60247" SRC="img548.gif"  >.	Using Theorem&nbsp;<A HREF="page62.html#theoremii"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> show that  <IMG WIDTH=148 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline60249" SRC="img549.gif"  >.<LI>	For each pair of functions, <I>f</I>(<I>n</I>) and <I>g</I>(<I>n</I>),	in the following table,	indicate if <I>f</I>(<I>n</I>)=<I>O</I>(<I>g</I>(<I>n</I>)) and if <I>g</I>(<I>n</I>)=<I>O</I>(<I>f</I>(<I>n</I>)).	<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>		<I>f</I>(<I>n</I>) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>g</I>(<I>n</I>) </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>10<I>n</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=61 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline60265" SRC="img550.gif"  > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 		 <IMG WIDTH=16 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline60267" SRC="img551.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=52 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline60269" SRC="img552.gif"  > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 		 <IMG WIDTH=45 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60271" SRC="img553.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=61 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60273" SRC="img554.gif"  > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 		 <IMG WIDTH=32 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59015" SRC="img350.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=22 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline60277" SRC="img555.gif"  > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 		 <IMG WIDTH=25 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline57989" SRC="img111.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=32 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59015" SRC="img350.gif"  > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 		 <IMG WIDTH=69 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60283" SRC="img556.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=32 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59015" SRC="img350.gif"  > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 		 <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60287" SRC="img557.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=32 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59015" SRC="img350.gif"  > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 		 <IMG WIDTH=15 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline60291" SRC="img558.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=24 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline60293" SRC="img559.gif"  > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 		 <IMG WIDTH=21 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline59477" SRC="img415.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=22 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline60297" SRC="img560.gif"  > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 		 <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60299" SRC="img561.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60301" SRC="img562.gif"  > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 		 <IMG WIDTH=16 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline60303" SRC="img563.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=63 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline60305" SRC="img564.gif"  > </TD></TR></TBODY></TABLE></P></DIV><LI><A NAME="exerciseasymptoticfib">&#160;</A>	Show that the Fibonacci numbers (see Equation&nbsp;<A HREF="page75.html#eqnasymptoticfibonacci"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>)	satisfy the identities	<P> <IMG WIDTH=174 HEIGHT=44 ALIGN=BOTTOM ALT="gather2420" SRC="img565.gif"  ><P>	for  <IMG WIDTH=38 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58983" SRC="img341.gif"  >.<LI>	Prove each of the following formulas:	<OL><LI>  <IMG WIDTH=92 HEIGHT=50 ALIGN=MIDDLE ALT="tex2html_wrap_inline60309" SRC="img566.gif"  ><LI>  <IMG WIDTH=99 HEIGHT=50 ALIGN=MIDDLE ALT="tex2html_wrap_inline60311" SRC="img567.gif"  ><LI>  <IMG WIDTH=99 HEIGHT=50 ALIGN=MIDDLE ALT="tex2html_wrap_inline60313" SRC="img568.gif"  ></OL><LI>	Show that  <IMG WIDTH=107 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline60315" SRC="img569.gif"  >,	where  <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58403" SRC="img216.gif"  > and  <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif"  >.<LI>	Show that  <IMG WIDTH=128 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline60321" SRC="img570.gif"  >.<LI>	Solve each of the following recurrences:	<OL><LI>		 <IMG WIDTH=308 HEIGHT=56 ALIGN=MIDDLE ALT="tex2html_wrap_inline60323" SRC="img571.gif"  ><LI>		 <IMG WIDTH=309 HEIGHT=56 ALIGN=MIDDLE ALT="tex2html_wrap_inline60325" SRC="img572.gif"  ><LI>		 <IMG WIDTH=311 HEIGHT=56 ALIGN=MIDDLE ALT="tex2html_wrap_inline60327" SRC="img573.gif"  ><LI>		 <IMG WIDTH=312 HEIGHT=56 ALIGN=MIDDLE ALT="tex2html_wrap_inline60329" SRC="img574.gif"  ></OL><LI>	Derive tight, big oh expressions for the running times of	example-a,example-b,example-c,example-d,example-f,example-g,example-h,example-i.<LI>	Consider the Python program fragments given below.	Assume that <tt>n</tt>, <tt>m</tt>, and <tt>k</tt>	are non-negative integers and that the methods <tt>e</tt>,	<tt>f</tt>, <tt>g</tt>, and <tt>h</tt> have the following characteristics:	<UL><LI> The worst case running time for <tt>e(n,m,k)</tt> is <I>O</I>(1)		and it returns a value between 1 and (<I>n</I>+<I>m</I>+<I>k</I>).<LI> The worst case running time for <tt>f(n,m,k)</tt> is <I>O</I>(<I>n</I>+<I>m</I>).<LI> The worst case running time for <tt>g(n,m,k)</tt> is <I>O</I>(<I>m</I>+<I>k</I>).<LI> The worst case running time for <tt>h(n,m,k)</tt> is <I>O</I>(<I>n</I>+<I>k</I>).	</UL>	Determine a tight, big oh expression for the worst-case	running time of each of the following program fragments:	<OL><LI><PRE>f(n, 10, 0);g(n, m, k);h(n, m, 1000000);</PRE><LI><PRE>for i in range(n):    f(n, m, k);</PRE><LI><PRE>for i in range (e(n, 10, 100)):    f(n, 10, 0);</PRE><LI><PRE>for i in range (e(n, m, k)):    f(n, 10, 0);</PRE><LI><PRE>for i in range(n):    for j in range(i, n):        f(n, m, k);</PRE><PRE></PRE>	</OL><LI> <A NAME="exerciseasymptoticf">&#160;</A>	Consider the following Python program fragment.	What value does <tt>f</tt> compute?	(Express your answer as a function of <I>n</I>).	Give a tight, big oh expression for the worst-case	running time of the method <tt>f</tt>.<PRE>def f(n):    sum = 0    for i in range(1, n + 1):	sum = sum + i    return sum</PRE><LI> <A NAME="exerciseasymptoticg">&#160;</A>	Consider the following Python program fragment.	(The method <tt>f</tt> is given in Exercise&nbsp;<A HREF="page79.html#exerciseasymptoticf"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).	What value does <tt>g</tt> compute?	(Express your answer as a function of <I>n</I>).	Give a tight, big oh expression for the worst-case	running time of the method <tt>g</tt>.<PRE>def g(n):    sum = 0    for i in range(1, n + 1):	sum = sum + i + f(i)    return sum</PRE><LI>	Consider the following Python program fragment.	(The method <tt>f</tt> is given in Exercise&nbsp;<A HREF="page79.html#exerciseasymptoticf"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>	and the method <tt>g</tt> is given in Exercise&nbsp;<A HREF="page79.html#exerciseasymptoticg"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).	What value does <tt>h</tt> compute?	(Express your answer as a function of <I>n</I>).	Give a tight, big oh expression for the worst-case	running time of the method <tt>h</tt>.<PRE>def h(n):    return f(n) + g(n)</PRE></OL><HR><A NAME="tex2html2114" HREF="page80.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2112" HREF="page58.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2106" HREF="page78.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html2116" 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 &#169; 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.</ADDRESS></BODY></HTML>

page79.html - 源码说明

本页面展示了「Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and」中的 page79.html 源码文件，采用 HTML 编程语言编写，共 132 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

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

⌨️ 快捷键说明

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