\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{3. feladatsor, 21. feladat, függvényabsztrakcióval}
\newcommand{\KN}{\text{KN}}
\newcommand{\VN}{\text{VN}}
\newcommand{\NEV}{\text{NEV}}
\newcommand{\NEVE}{\text{NEVE}}
\newcommand{\U}{\mathbb{U}}
\newcommand{\Y}{\mathbb{Y}}
\newcommand{\Ch}{\text{Ch}}
\newcommand{\extr}{\text{extr}}
\renewcommand{\T}{\mathbb{T}}
\begin{document}
\noindent
\emph{Feladat:} Adott az $x$ szekvenciális file (megengedett művelet
az $sx,dx,x:\Read$), melynek elemei egy vezetéknevet és egy
keresztnevet tartalmaznak.  A file a keresztnevek szerint rendezett.
Gyűjtsük ki a file-ból a különböző keresztneveket, és azt, hogy
hányszor szerepelnek.

\emph{Specifikáció:}\\

$\KN = (\seq(\Ch))$\\
$\VN = (\seq(\Ch))$\\
$\NEV = (vn:\VN, kn:\KN)$\\
$\F = \file(\NEV)$\\
$I_\F{f}=(\forall i\in[1,dom(f)-1]: f_i.kn\le f_{i+1}.kn)$\\
$\U = (kn:\KN, d:\N)$\\
$\F' = \file(\U)$\\
$A = \alatt{\F}{x} \times \alatt{\F'}{z}$\\
\vspace{1cm}

A feladat állapotterét először áttranszformáljuk egy olyanra, ahol a
file végén van extremális elem, még mielőtt az olvasás során abnorm
értéket kapnánk, mert így könnyebb lesz felírni a kiértékelendő
rekurzív függvényt.

$\NEVE=\NEV \cup \{\extr\}, \F''=file(\NEVE)$\\
$A' = \alatt{\F''}{y} \times \alatt{\F'}{z}$\\
$y=\con(x,<\extr>)$

$B = \alatt{\F''}{y'}$\\
$Q = ( y=y' \es dom(y)\ge 1)$\\
$R = ( z = f(dom(y'))_1)$, ahol $f:[0,dom(y')]\nyil \F'\times\KN\times\N, f(1):=(<>,y_1,1),$\\
$\forall i\in[1,dom(y')]: f(i):=F(i, f(i-1))$
\[
F(i,z):= \left\{
\begin{array}{ll}
(hiext(z_1,(z_2,z_3)), y_i.kn, 1) & \text{, ha } y_i.kn\ne z_2 \\
(z_1, z_2, z_3 + 1) & \text{, ha } y_i.kn = z_2
\end{array}
\right.
\]

\begin{textblock}{1}(7.0,-7.4)
\begin{stuki*}[4cm]{open($y$)}
  \stm{sx,dx,x:\Read}
  \stm{dy:=(\text{``valami''},1)}
\end{stuki*}
\end{textblock}

\begin{textblock}{1}(6.0,-6.2)
\begin{stuki*}[8cm]{$sy,dy,y:\Read$}
\begin{IF}[60]{4}{\stm{dy\ne\extr}}
  \stm{sy:=\norm}
  \begin{IF}{2}{\stm{sx=\norm}}
    \stm{dy:=dx}
    \stm{sx,dx,x:\Read}
    \ELSE
    \stm{dy:=\extr}
  \end{IF}
  \ELSE
  \stm{sy:=\abnorm}
\end{IF}
\end{stuki*}
\end{textblock}

A megoldóprogramot a rekurzív függvényérték kiszámításának tételével kapjuk:

\begin{stuki}[7cm]
  \stm{\open(y)}
  \stm{sy,dy,y:\Read}
  \stm{z,a,s:=<>,dy.kn,1}
  \stm{sy,dy,y:\Read}
  \begin{WHILE}{4}{\stm{sy=\norm}}
    \begin{IF}{2}{\stm{dy.kn\ne a}}
      \stm{z:\hiext(a,s)}
      \stm{a,s:=dy.kn,1}
    \ELSE
      \stm{s:=s+1}
    \end{IF}
    \stm{sy,dy,y:\Read}
  \end{WHILE}
\end{stuki}

A két előolvasásra azért volt szükség, mert 1-től és nem 0-tól
indítottuk a rekurziót, illetve azt is vegyük észre, hogy a kész
programban sehol nem használtuk ki, hogy az utolsó elem a speciális
extr, így igazából az új típusra nincs is szükség, azt is írhatjuk
helyette, hogy ``Gábor'', ``Gábor''.


\end{document}