Parent Directory | Revision Log

Revision **278** -
(**show annotations**)
(**download**)
(**as text**)

*Wed Aug 14 23:10:36 2019 UTC*
(4 years, 10 months ago)
by *dashley*

File MIME type: application/x-tex

File size: 2532 byte(s)

File MIME type: application/x-tex

File size: 2532 byte(s)

Change keyword substitution (migration from cvs to svn).

1 | %$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 | $HeadURL$ |

75 | $Revision$ |

76 | $Date$ |

77 | $Author$ |

78 | \end{verbatim} |

79 | \end{tiny} |

80 | \noindent\rule[0.25in]{\textwidth}{1pt} |

81 | \end{figure} |

82 | |

83 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |

84 | % |

85 | %End of file C_RAS0.TEX |

Name | Value |
---|---|

svn:eol-style |
native |

svn:keywords |
Author Date Id Revision URL Header |

dashley@gmail.com | ViewVC Help |

Powered by ViewVC 1.1.25 |