%$Header$ \chapter[Solutions: \cratzeroxrefcomma{}Chapter \ref{crat0}] {Solutions: \cratzeroxrefcomma{}Chapter \ref{crat0}, \cratzerolongtitle{}} \label{cras0} \vworkexercisechapterheader{} \begin{vworkexercisesolution}{\ref{exe:crat0:sexe0:01}} The value of the \texttt{state} variable when evaluating the \emph{if()} clause on the $n+1$'th invocation is $$\label{eq:cras0:exe01:01} K_1 - nK_4 + (n+1) K_2 .$$ We require on the $n+1$'th invocation, in order for the test of the \emph{if()} clause to fail (i.e. that the function \texttt{A()}'' has been run on the first $n$ invocations of the base subroutine but is not run on the $n+1$'th invocation), that: $$\label{eq:cras0:exe01:01b} K_1 - nK_4 + (n+1) K_2 < K_3.$$ Solving this inequality for the smallest integral value of $n$ yields: $$\label{eq:cras0:exe01:01c} n = \left\lceil \frac{K_1 + K_2 - K_3 + 1}{K_4 - K_2} \right\rceil .$$ It can be verified using an example that (\ref{eq:cras0:exe01:01c}). For example, with $K_1 = 10$, $K_2 = 3$, $K_3 = 7$, and $K_4 = 5$, (\ref{eq:cras0:exe01:01}) predicts that on the first $\lceil 7/2 \rceil = 4$ invocations of the base subroutine the subroutine \texttt{A()}'' will be run but on the 5th invocation it will not. Tracing the algorithm with the parameters specified reveals that at the test in the \emph{if()} statement on the first invocation of the subroutine, \texttt{state}=13 (\texttt{A()}'' executed); on the second invocation of the subroutine, \texttt{state}=11 (\texttt{A()}'' executed); on the third invocation of the subroutine, \texttt{state}=9 (\texttt{A()}'' executed); on the fourth invocation of the subroutine, \texttt{state}=7 (\texttt{A()}'' executed); and on the fifth invocation of the subroutine, \texttt{state}=5 (\texttt{A()}'' not executed). This is in agreement with (\ref{eq:cras0:exe01:01}). \end{vworkexercisesolution} %\vworkexerciseseparator %\begin{vworkexercisesolution}{\ref{exe:cfry0:sexe0:02}} %Placeholder. %\end{vworkexercisesolution} \vworkexercisechapterfooter %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \vfill \noindent\begin{figure}[!b] \noindent\rule[-0.25in]{\textwidth}{1pt} \begin{tiny} \begin{verbatim} $HeadURL$ $Revision$ $Date$ $Author$ \end{verbatim} \end{tiny} \noindent\rule[0.25in]{\textwidth}{1pt} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % %End of file C_RAS0.TEX