%$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$ \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} $RCSfile: c_ras0.tex,v$ $Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_ras0/c_ras0.tex,v$ $Revision: 1.4$ $Author: dtashley$ $Date: 2003/11/03 02:14:24$ \end{verbatim} \end{tiny} \noindent\rule[0.25in]{\textwidth}{1pt} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % $Log: c_ras0.tex,v$ % Revision 1.4 2003/11/03 02:14:24 dtashley % All duplicate labels as flagged by LaTeX removed. Additional files added % to Microsoft Visual Studio edit context. % % Revision 1.3 2003/03/08 04:11:19 dtashley % Friday evening safety checkin. % % Revision 1.2 2001/07/01 21:10:59 dtashley % Safety check-in after major re-org. % % Revision 1.1.1.1 2001/07/01 00:14:03 dtashley % Initial import. % % %End of file C_RAS0.TEX