1 |
dashley |
140 |
%$Header$ |
2 |
|
|
|
3 |
|
|
\chapter[Solutions: \cratzeroxrefcomma{}Chapter \ref{crat0}] |
4 |
|
|
{Solutions: \cratzeroxrefcomma{}Chapter \ref{crat0}, \cratzerolongtitle{}} |
5 |
|
|
|
6 |
|
|
\label{cras0} |
7 |
|
|
|
8 |
|
|
\vworkexercisechapterheader{} |
9 |
|
|
\begin{vworkexercisesolution}{\ref{exe:crat0:sexe0:01}} |
10 |
|
|
The value of the \texttt{state} variable when |
11 |
|
|
evaluating the \emph{if()} clause on the |
12 |
|
|
$n+1$'th invocation is |
13 |
|
|
|
14 |
|
|
\begin{equation} |
15 |
|
|
\label{eq:cras0:exe01:01} |
16 |
|
|
K_1 - nK_4 + (n+1) K_2 . |
17 |
|
|
\end{equation} |
18 |
|
|
|
19 |
|
|
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 |
21 |
|
|
``\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), |
23 |
|
|
that: |
24 |
|
|
|
25 |
|
|
\begin{equation} |
26 |
|
|
\label{eq:cras0:exe01:01b} |
27 |
|
|
K_1 - nK_4 + (n+1) K_2 < K_3. |
28 |
|
|
\end{equation} |
29 |
|
|
|
30 |
|
|
Solving this inequality for the smallest integral |
31 |
|
|
value of $n$ yields: |
32 |
|
|
|
33 |
|
|
\begin{equation} |
34 |
|
|
\label{eq:cras0:exe01:01c} |
35 |
|
|
n = \left\lceil |
36 |
|
|
\frac{K_1 + K_2 - K_3 + 1}{K_4 - K_2} |
37 |
|
|
\right\rceil . |
38 |
|
|
\end{equation} |
39 |
|
|
|
40 |
|
|
It can be verified using an example that |
41 |
|
|
(\ref{eq:cras0:exe01:01c}). For example, with |
42 |
|
|
$K_1 = 10$, $K_2 = 3$, $K_3 = 7$, and $K_4 = 5$, |
43 |
|
|
(\ref{eq:cras0:exe01:01}) predicts that on the first |
44 |
|
|
$\lceil 7/2 \rceil = 4$ invocations of the base subroutine |
45 |
|
|
the subroutine ``\texttt{A()}'' will be run but on the 5th |
46 |
|
|
invocation it will not. Tracing the algorithm with the |
47 |
|
|
parameters specified reveals that at the |
48 |
|
|
test in the \emph{if()} statement |
49 |
|
|
on the first invocation of the |
50 |
|
|
subroutine, \texttt{state}=13 (``\texttt{A()}'' executed); |
51 |
|
|
on the second invocation of the |
52 |
|
|
subroutine, \texttt{state}=11 (``\texttt{A()}'' executed); |
53 |
|
|
on the third invocation of the |
54 |
|
|
subroutine, \texttt{state}=9 (``\texttt{A()}'' executed); |
55 |
|
|
on the fourth invocation of the |
56 |
|
|
subroutine, \texttt{state}=7 (``\texttt{A()}'' executed); |
57 |
|
|
and on the fifth invocation of the |
58 |
|
|
subroutine, \texttt{state}=5 (``\texttt{A()}'' not executed). |
59 |
|
|
This is in agreement with |
60 |
|
|
(\ref{eq:cras0:exe01:01}). |
61 |
|
|
\end{vworkexercisesolution} |
62 |
|
|
%\vworkexerciseseparator |
63 |
|
|
%\begin{vworkexercisesolution}{\ref{exe:cfry0:sexe0:02}} |
64 |
|
|
%Placeholder. |
65 |
|
|
%\end{vworkexercisesolution} |
66 |
|
|
\vworkexercisechapterfooter |
67 |
|
|
|
68 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
69 |
|
|
\vfill |
70 |
|
|
\noindent\begin{figure}[!b] |
71 |
|
|
\noindent\rule[-0.25in]{\textwidth}{1pt} |
72 |
|
|
\begin{tiny} |
73 |
|
|
\begin{verbatim} |
74 |
dashley |
278 |
$HeadURL$ |
75 |
|
|
$Revision$ |
76 |
|
|
$Date$ |
77 |
|
|
$Author$ |
78 |
dashley |
140 |
\end{verbatim} |
79 |
|
|
\end{tiny} |
80 |
|
|
\noindent\rule[0.25in]{\textwidth}{1pt} |
81 |
|
|
\end{figure} |
82 |
|
|
|
83 |
dashley |
278 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
84 |
dashley |
140 |
% |
85 |
|
|
%End of file C_RAS0.TEX |