\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{2. feladatsor, 77. feladat}
\begin{document}
\noindent
\emph{Feladat:} Keressük meg az $f$ függvény értékei között a $k$ szám
$p$-edik előfordulását!

\emph{Átfogalmazás:} Keressük azt az értéket, ahol a $\varphi$ függvény
először veszi fel a $p$ értéket, ahol $\varphi$ definíciója:

$\varphi:[a-1,b]\nyil \N_0$\\
$\varphi(a-1) = 0$, 
$\forall i\in [a,b]: \varphi(i) = F(i, \varphi(i-1))$, ahol 
$F: [a,b] \times \N_0 \nyil R$ definíciója:\\
\[
F(i, x)=\left\{
\begin{array}{ll}
  x & \text{, ha } f(i)\ne k \\
  x+1 & \text{, ha } f(i)=k
\end{array}
\right.
\]

Paraméteres visszavezetés ($k$, $p$).

\begin{tabular}{p{13cm}p{7cm}}
\begin{minipage}{13cm}
\emph{Specifikáció:}\\
$A = \alatt{\Z}{a} \times \alatt{\Z}{b} \times \alatt{\N}{k} \times \alatt{\N}{p} \times \alatt{\Z}{i} \times \alatt{\L}{l}$\\
$B = \alatt{\N}{a'} \times \alatt{\N}{b'} \times \alatt{\N}{k'} \times \alatt{\N}{p'}$\\
$Q = ( a=a' \es b=b' \es a\le b+1 \es k=k' \es p=p')$\\
$R = ( Q \es l=(\exists j\in [a..b]: \varphi(j)=p) \es l\nyil(i\in [a..b] \es \varphi(i)=p \es f(i)=k))$ \\
$\ekv$ (hiszen, ha $f(i)=k$, akkor éppen először veszi fel $p$ értékét $\varphi$)\\
$( Q \es l=(\exists j\in [a..b]: \varphi(j)=p) \es l\nyil(i\in [a..b] \es \varphi(i)=p \es \forall j\in[a..i-1]:\varphi(j)\ne p))$
\end{minipage}
&
\hspace{-2cm}\begin{tabular}[b]{ccc}
feladat &  & lin. ker. 2.8 \\
\hline
$a$ & \knyil & $m$ \\
$b$ & \knyil & $n$ \\
$\varphi(i)=p$ & \knyil & $\beta(i)$
\end{tabular}
\end{tabular}

\begin{stuki}[6cm]
  \stm{i,l:=a-1,\hamis}
  \begin{WHILE}{2}{\stm{\nem l \es i \ne b}}
    \stm{l:=(\varphi(i+1)= p)}
    \stm{i:=i+1}
  \end{WHILE}
\end{stuki}

\begin{tabular}{p{7cm}cp{7cm}}
Felhasználva a rekurzív függvény változóval való helyettesítésének programtranszformációs módszerét $\varphi$-re:

\vspace{1ex}

\begin{stukibox}[6cm]
  \stm{z:=0}
  \stm{i,l:=a-1,\hamis}
  \begin{WHILE}{3}{\stm{\nem l \es i \ne b}}
    \stm{z:=F(i+1, z)}
    \stm{l:=(z= p)}
    \stm{i:=i+1}
  \end{WHILE}
\end{stukibox}

& \hspace{1.5cm} &

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:

\vspace{1ex}

\begin{stukibox}[6cm]
  \stm{z:=0}
  \stm{i,l:=a-1,\hamis}
  \begin{WHILE}{4}{\stm{\nem l \es i \ne b}}
    \begin{IF}{1}{\stm{f(i+1)=k}}
      \stm{z:=z+1}
      \ELSE
      \stm{z:=z (\ekv \text{SKIP})}
    \end{IF}
    \stm{l:=(z= p)}
    \stm{i:=i+1}
  \end{WHILE}
\end{stukibox}
\end{tabular}

\newpage

Az egyik félévben ZH feladat volt, hogy a szöveget tartalmazó adott
$x$ vektorban keressük meg a harmadik szó kezdetét (ha van benne három
szó).  A szavakat vesszők (akár több is egymás mellett) választják el.

Ha az előző feladatra egy kicsit absztraktabban tekintünk, akkor ezt a
ZH feladat megoldást is megkapjuk.  Írjunk egy olyan programot, ami
egy logikai $\beta$ függvény értékei között a $p$-edik igaz
előfordulást keresi!  Ennek a programnak a megalkotása után a
$\beta(i)$-t $f(i)=k$-val helyettesítve kaphatjuk az előző feladatot,
tehát ez valóban általánosítás.

Az előző feladat megoldóprogramjában az $f(i+1)=k$-t kell
$\beta(i+1)$-re cserélni nyilván, a hozzá tartozó visszavezetés és
rekurzív függvény is analóg módon megkapható, ha minden $f(i)=k$
jellegű vizsgálatot $\beta(i)$-vel helyettesítünk a megoldás során.

$\varphi:[m-1,n]\nyil \N_0$\\
$\varphi(m-1) = 0$, 
$\forall i\in [m,n]: \varphi(i) = F(i, \varphi(i-1))$, ahol 
$F: [m,n] \times \N_0 \nyil R$ definíciója:\\
\[
F(i, x)=\left\{
\begin{array}{ll}
  x & \text{, ha } \nem\beta(i) \\
  x+1 & \text{, ha } \beta(i)
\end{array}
\right.
\]

\begin{stuki}[6cm]
  \stm{z:=0}
  \stm{i,l:=a-1,\hamis}
  \begin{WHILE}{4}{\stm{\nem l \es i \ne b}}
    \begin{IF}{1}{\stm{\beta(i+1)}}
      \stm{z:=z+1}
      \ELSE
      \stm{z:=z (\ekv \text{SKIP})}
    \end{IF}
    \stm{l:=(z= p)}
    \stm{i:=i+1}
  \end{WHILE}
\end{stuki}

Nézzük most a ZH feladat specifikációját:\\
$\V = \vect(\Z, \text{Ch})$\\
$A = \alatt{\V}{x} \times \alatt{\Z}{i} \times \alatt{\L}{l}$\\
$B = \alatt{\V}{x'}$\\
$Q = ( x=x' )$\\
$R = ( Q \es l=(\exists j\in [x.\lob..x.hib]: \varphi(j)=3) \es
l\nyil(i\in [x.\lob..x.\hib] \es \varphi(i)=3 \es \forall
j\in[x.\lob..i-1]:\varphi(j)\ne 3))$, ahol a $\varphi$-ben szereplő
$\beta(i)$ most az, hogy $(i=x.\lob \vagy x_{i-1}=$`,'$) \es
x_i\ne$`,', ugyanis akkor kezdődik valahol új szó, ha betű az aktuális
karakter és előtte vagy a vektor eleje vagy egy vessző van.  Az is
kiolvasható az utófeltételből, hogy az $m$-et $x.\lob$-bal, az $n$-et
$x.\hib$-bel, a $p$-t pedig $3$-mal helyettesítettük, így a
megoldóprogram:
\begin{stuki}[8cm]
  \stm{z:=0}
  \stm{i,l:=x.\lob-1,\hamis}
  \begin{WHILE}{4}{\stm{\nem l \es i \ne x.\hib}}
    \begin{IF}{1}{\stm{(i+1=x.\lob \vagy x_i=\text{`,'}) \es x_i\ne\text{`,'}}}
      \stm{z:=z+1}
      \ELSE
      \stm{z:=z (\ekv \text{SKIP})}
    \end{IF}
    \stm{l:=(z= 3)}
    \stm{i:=i+1}
  \end{WHILE}
\end{stuki}

A struktogram csak olyan ún. lusta kiértékelés mellett helyes, ahol az
$x$ vektor lob indexénél korábbi elem hibás lekérdezésére már nem
kerül sor a vele egy diszjunkcióban szereplő $i+1=x.\lob$ igaz volta
miatt.  Természetesen ha a mi számítógépünk nem lustán értékel ki,
akkor az elágazásfeltételt ki kell transzformálnunk és ezt a
viselkedést egy külön elágazással megvalósíthatjuk.

\end{document}