\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{3. feladatsor, 21. feladat max. ker., 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.
Adjuk meg, hogy melyik keresztnév fordul elő a legtöbbször!

\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_0)$\\
$A = \alatt{\F}{x} \times \alatt{\U}{max}$\\
\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{\U}{max}$\\
$y=\con(x,<\extr>)$

$B = \alatt{\F'}{y'}$\\
$Q = ( y=y' \es y.dom>0 )$\\
$R = ( max = f(dom(y'))_1)$, ahol $f:[0,dom(y')]\nyil \U\times\KN\times\N_0, f(0):=((\text{``üres''},0),\text{``üres''},0), $\\
$\forall i\in[1,dom(y')]:f(i):=F(i, f(i-1))$
\[
F(i,z):= \left\{
\begin{array}{ll}
(z_1, y_i.kn, 1) & \text{, ha } y_i.kn\ne z_2 \es z_3 \le z_1.d\\
((z_2, z_3), y_i.kn, 1) & \text{, ha } y_i.kn\ne z_2 \es z_3>z_1.d\\
(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{``üres''},0)}
\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}[12cm]
  \stm{\open(y)}
  \stm{sy,dy,y:\Read}
  \stm{max,a,s:=(\text{``üres''},0),\text{``üres''},0}
  \begin{WHILE}{4}{\stm{sy=\norm}}
    \begin{CASE}{2}{3}
      \WHEN{\stm{dy.kn\ne a \es s\le max.d}}
      \stm{a,s:=dy.kn,1}
      \WHEN{\stm{dy.kn\ne a \es s>max.d}}
      \stm{max,a,s:=(a,s),dy.kn,1}
      \WHEN{\stm{dy.kn=a}}
      \stm{s:=s+1}
    \end{CASE}
    \stm{sy,dy,y:\Read}
  \end{WHILE}
\end{stuki}

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}