\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{2. feladatsor, 69. feladat}
\begin{document}
\noindent
\emph{Feladat:} Adott egy $f:[a,b]\nyil\Z$ függvény.  Ezen függvény
értelmezési tartományának egy $i$ pontját a függvény csúcsának
nevezzük, ha $\forall j\in[i+1,b]:f(j)<f(i)$.  Adjuk meg, hogy hány
csúcsa van $f$-nek!

\emph{Átfogalmazás:} Legyen $R = (cs:\L, max:\Z \cup \{-\infty\})$ egy
rekord.  Ekkor $\psi:[a,b+1]\nyil R$ függvény legyen olyan, hogy egy
adott az intervallumbeli szám esetén az eredményrekord $cs$ komponense
akkor és csak akkor igaz, ha az adott szám csúcs, a $max$ komponens
pedig az adott számtól az intervallum végéig előforduló legnagyobb
függvényértéket tartalmazza.  $b+1$ argumentum esetén a lehető
legkisebb értéket, a $-\infty$ értéket adja vissza, hamis $cs$
komponenssel.  Formálisan:
\[
\psi(i) = \left\{
\begin{array}{ll}
  (\hamis, -\infty) & \text{, ha } i=b+1 \\
  (\igaz, f(i)) & \text{, ha } i\in [a,b] \es \forall j\in[i+1,b]:f(j)<f(i) \\
  (\hamis, max(f(i+1), ..., f(b))) & \text{, ha } i\in [a,b] \es \exists j\in[i+1,b]: f(j)\ge f(i)
\end{array}
\right. 
\]

Ennek a függvénynek egy rekurzív átfogalmazása is megadható:
$\phi:[a-1,b]\nyil R$\\
$\phi(a-1) = (\hamis, -\infty)$, 
$\forall i\in [a,b]: \phi(i) = F(i, \phi(i-1))$, ahol 
$F: [a,b] \times R \nyil R$ definíciója:\\
\[
F(i, x)=\left\{
\begin{array}{ll}
  (\igaz, f(b+a-i)) & \text{, ha } x.max<f(b+a-i) \\
  (\hamis, x.max) & \text{, ha } x.max\ge f(b+a-i)
\end{array}
\right.
\]

\emph{Példa: } $f:[-2,6]\nyil Z$ \\
\begin{tabular}{c|c|ccccccccc|c}
$i$ & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
\hline
$f(i)$ & - & 5 & 0 & -12 & 34 & 20 & 8 & 3 & 2 & 5 & -\\
$\psi(i)$ & - & (h, 34)& (h, 34)& (h, 34)& (i, 34)& (i, 20)& (i, 8)& (h, 5) & (h, 5) & (i, 5) & (h, $-\infty$)\\
$F(i,\phi(i-1))$ & - & (i, 5) & (h, 5) & (h, 5) & (i, 8) & (i, 20) & (i, 34) & (h, 34) & (h, 34) & (h, 34) & - \\ 
$\phi(i)$ & (h, $-\infty$) & (i, 5) & (h, 5) & (h, 5) & (i, 8) & (i, 20) & (i, 34) & (h, 34) & (h, 34) & (h, 34) & -\\
\end{tabular}

Vegyük észre, hogy habár a $\psi$ és $\phi$ egymáshoz képest fordított
sorrendű, de ettől még az igaz $cs$ adatkomponensű tagjaik száma
azonos, így bármelyiküket használhatjuk.

Ezzel a $\phi$ függvénnyel már a feladat a számlálásra természetes módon visszavezethető:

\emph{Specifikáció:}\\
$A = \alatt{\N}{a} \times \alatt{\N}{b} \times \alatt{\N_0}{d}$\\
$B = \alatt{\N}{a'} \times \alatt{\N}{b'}$\\
$Q = ( a=a' \es b=b' \es a\le b+1)$\\
$R = ( Q \es d=\sum\limits_{i=a}^b \chi(\phi(i).cs) )$

\begin{textblock}{1}(4.0,-1.5)
\begin{tabular}{ccc}
feladat &  & számlálás \\
\hline
$a$ & \knyil & $m$ \\
$b$ & \knyil & $n$ \\
$\phi(i).cs$ & \knyil & $\beta(i)$
\end{tabular}
\end{textblock}

\begin{textblock}{1}(7.6,-2.0)
\begin{stuki}[6cm]
  \stm{k,d:=a-1,0}
  \begin{WHILE}{3}{\stm{k \ne b}}
    \begin{IF}{1}{\stm{\phi(k+1).cs}}
      \stm{d:=d+1}
      \ELSE
      \SKIP
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}
\end{textblock}

\begin{textblock}{5}(0.0,0.5)
Felhasználva a rekurzív függvény változóval való helyettesítésének programtranszformációs módszerét $\phi$-re:

\begin{stuki}[6cm]
  \stm{z:=(h, -\infty)}
  \stm{k,d:=a-1,0}
  \begin{WHILE}{4}{\stm{k \ne b}}
    \stm{z:=F(k+1, z)}
    \begin{IF}{1}{\stm{z.cs}}
      \stm{d:=d+1}
      \ELSE
      \SKIP
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}
\end{textblock}

\begin{textblock}{7}(5.5,0.5)
Ha ismerjük az elágazással definiált függvény kiszámításának
programozási tételét, akkor ebből megkaphatjuk a megoldó programot, ha
azt $F$-re alkalmazzuk:

\begin{stuki}[10cm]
  \stm{z:=(h, -\infty)}
  \stm{k,d:=a-1,0}
  \begin{WHILE}{5}{\stm{k \ne b}}
    \begin{IF}{1}{\stm{z.max<f(a+b-k-1)}}
      \stm{z:=(\igaz, f(a+b-k-1))}
      \ELSE
      \stm{z:=(\hamis, z.max)}
    \end{IF}
    \begin{IF}{1}{\stm{z.cs}}
      \stm{d:=d+1}
      \ELSE
      \SKIP
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}
\end{textblock}
\vspace{8cm}
Megjegyezzük, hogyha nem engednénk meg az üres intervallumokat, akkor
a kezdeti értékadás lehetne $z:=(h,f(b)-1)$, amivel a $-\infty$
használata a gyakorlatban elkerülhető.
\end{document}