1 |
%$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_ras0/c_ras0.tex,v 1.4 2003/11/03 02:14:24 dtashley Exp $ |
%$Header$ |
2 |
|
|
3 |
\chapter[Solutions: \cratzeroxrefcomma{}Chapter \ref{crat0}] |
\chapter[Solutions: \cratzeroxrefcomma{}Chapter \ref{crat0}] |
4 |
{Solutions: \cratzeroxrefcomma{}Chapter \ref{crat0}, \cratzerolongtitle{}} |
{Solutions: \cratzeroxrefcomma{}Chapter \ref{crat0}, \cratzerolongtitle{}} |
5 |
|
|
6 |
\label{cras0} |
\label{cras0} |
7 |
|
|
8 |
\vworkexercisechapterheader{} |
\vworkexercisechapterheader{} |
9 |
\begin{vworkexercisesolution}{\ref{exe:crat0:sexe0:01}} |
\begin{vworkexercisesolution}{\ref{exe:crat0:sexe0:01}} |
10 |
The value of the \texttt{state} variable when |
The value of the \texttt{state} variable when |
11 |
evaluating the \emph{if()} clause on the |
evaluating the \emph{if()} clause on the |
12 |
$n+1$'th invocation is |
$n+1$'th invocation is |
13 |
|
|
14 |
\begin{equation} |
\begin{equation} |
15 |
\label{eq:cras0:exe01:01} |
\label{eq:cras0:exe01:01} |
16 |
K_1 - nK_4 + (n+1) K_2 . |
K_1 - nK_4 + (n+1) K_2 . |
17 |
\end{equation} |
\end{equation} |
18 |
|
|
19 |
We require on the $n+1$'th invocation, in order for the |
We require on the $n+1$'th invocation, in order for the |
20 |
test of the \emph{if()} clause to fail (i.e. that the function |
test of the \emph{if()} clause to fail (i.e. that the function |
21 |
``\texttt{A()}'' has been run on the first $n$ invocations of |
``\texttt{A()}'' has been run on the first $n$ invocations of |
22 |
the base subroutine but is not run on the $n+1$'th invocation), |
the base subroutine but is not run on the $n+1$'th invocation), |
23 |
that: |
that: |
24 |
|
|
25 |
\begin{equation} |
\begin{equation} |
26 |
\label{eq:cras0:exe01:01b} |
\label{eq:cras0:exe01:01b} |
27 |
K_1 - nK_4 + (n+1) K_2 < K_3. |
K_1 - nK_4 + (n+1) K_2 < K_3. |
28 |
\end{equation} |
\end{equation} |
29 |
|
|
30 |
Solving this inequality for the smallest integral |
Solving this inequality for the smallest integral |
31 |
value of $n$ yields: |
value of $n$ yields: |
32 |
|
|
33 |
\begin{equation} |
\begin{equation} |
34 |
\label{eq:cras0:exe01:01c} |
\label{eq:cras0:exe01:01c} |
35 |
n = \left\lceil |
n = \left\lceil |
36 |
\frac{K_1 + K_2 - K_3 + 1}{K_4 - K_2} |
\frac{K_1 + K_2 - K_3 + 1}{K_4 - K_2} |
37 |
\right\rceil . |
\right\rceil . |
38 |
\end{equation} |
\end{equation} |
39 |
|
|
40 |
It can be verified using an example that |
It can be verified using an example that |
41 |
(\ref{eq:cras0:exe01:01c}). For example, with |
(\ref{eq:cras0:exe01:01c}). For example, with |
42 |
$K_1 = 10$, $K_2 = 3$, $K_3 = 7$, and $K_4 = 5$, |
$K_1 = 10$, $K_2 = 3$, $K_3 = 7$, and $K_4 = 5$, |
43 |
(\ref{eq:cras0:exe01:01}) predicts that on the first |
(\ref{eq:cras0:exe01:01}) predicts that on the first |
44 |
$\lceil 7/2 \rceil = 4$ invocations of the base subroutine |
$\lceil 7/2 \rceil = 4$ invocations of the base subroutine |
45 |
the subroutine ``\texttt{A()}'' will be run but on the 5th |
the subroutine ``\texttt{A()}'' will be run but on the 5th |
46 |
invocation it will not. Tracing the algorithm with the |
invocation it will not. Tracing the algorithm with the |
47 |
parameters specified reveals that at the |
parameters specified reveals that at the |
48 |
test in the \emph{if()} statement |
test in the \emph{if()} statement |
49 |
on the first invocation of the |
on the first invocation of the |
50 |
subroutine, \texttt{state}=13 (``\texttt{A()}'' executed); |
subroutine, \texttt{state}=13 (``\texttt{A()}'' executed); |
51 |
on the second invocation of the |
on the second invocation of the |
52 |
subroutine, \texttt{state}=11 (``\texttt{A()}'' executed); |
subroutine, \texttt{state}=11 (``\texttt{A()}'' executed); |
53 |
on the third invocation of the |
on the third invocation of the |
54 |
subroutine, \texttt{state}=9 (``\texttt{A()}'' executed); |
subroutine, \texttt{state}=9 (``\texttt{A()}'' executed); |
55 |
on the fourth invocation of the |
on the fourth invocation of the |
56 |
subroutine, \texttt{state}=7 (``\texttt{A()}'' executed); |
subroutine, \texttt{state}=7 (``\texttt{A()}'' executed); |
57 |
and on the fifth invocation of the |
and on the fifth invocation of the |
58 |
subroutine, \texttt{state}=5 (``\texttt{A()}'' not executed). |
subroutine, \texttt{state}=5 (``\texttt{A()}'' not executed). |
59 |
This is in agreement with |
This is in agreement with |
60 |
(\ref{eq:cras0:exe01:01}). |
(\ref{eq:cras0:exe01:01}). |
61 |
\end{vworkexercisesolution} |
\end{vworkexercisesolution} |
62 |
%\vworkexerciseseparator |
%\vworkexerciseseparator |
63 |
%\begin{vworkexercisesolution}{\ref{exe:cfry0:sexe0:02}} |
%\begin{vworkexercisesolution}{\ref{exe:cfry0:sexe0:02}} |
64 |
%Placeholder. |
%Placeholder. |
65 |
%\end{vworkexercisesolution} |
%\end{vworkexercisesolution} |
66 |
\vworkexercisechapterfooter |
\vworkexercisechapterfooter |
67 |
|
|
68 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
69 |
\vfill |
\vfill |
70 |
\noindent\begin{figure}[!b] |
\noindent\begin{figure}[!b] |
71 |
\noindent\rule[-0.25in]{\textwidth}{1pt} |
\noindent\rule[-0.25in]{\textwidth}{1pt} |
72 |
\begin{tiny} |
\begin{tiny} |
73 |
\begin{verbatim} |
\begin{verbatim} |
74 |
$RCSfile: c_ras0.tex,v $ |
$RCSfile: c_ras0.tex,v $ |
75 |
$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_ras0/c_ras0.tex,v $ |
$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_ras0/c_ras0.tex,v $ |
76 |
$Revision: 1.4 $ |
$Revision: 1.4 $ |
77 |
$Author: dtashley $ |
$Author: dtashley $ |
78 |
$Date: 2003/11/03 02:14:24 $ |
$Date: 2003/11/03 02:14:24 $ |
79 |
\end{verbatim} |
\end{verbatim} |
80 |
\end{tiny} |
\end{tiny} |
81 |
\noindent\rule[0.25in]{\textwidth}{1pt} |
\noindent\rule[0.25in]{\textwidth}{1pt} |
82 |
\end{figure} |
\end{figure} |
83 |
|
|
84 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
85 |
% $Log: c_ras0.tex,v $ |
% $Log: c_ras0.tex,v $ |
86 |
% Revision 1.4 2003/11/03 02:14:24 dtashley |
% Revision 1.4 2003/11/03 02:14:24 dtashley |
87 |
% All duplicate labels as flagged by LaTeX removed. Additional files added |
% All duplicate labels as flagged by LaTeX removed. Additional files added |
88 |
% to Microsoft Visual Studio edit context. |
% to Microsoft Visual Studio edit context. |
89 |
% |
% |
90 |
% Revision 1.3 2003/03/08 04:11:19 dtashley |
% Revision 1.3 2003/03/08 04:11:19 dtashley |
91 |
% Friday evening safety checkin. |
% Friday evening safety checkin. |
92 |
% |
% |
93 |
% Revision 1.2 2001/07/01 21:10:59 dtashley |
% Revision 1.2 2001/07/01 21:10:59 dtashley |
94 |
% Safety check-in after major re-org. |
% Safety check-in after major re-org. |
95 |
% |
% |
96 |
% Revision 1.1.1.1 2001/07/01 00:14:03 dtashley |
% Revision 1.1.1.1 2001/07/01 00:14:03 dtashley |
97 |
% Initial import. |
% Initial import. |
98 |
% |
% |
99 |
% |
% |
100 |
%End of file C_RAS0.TEX |
%End of file C_RAS0.TEX |