% -*- coding: iso-8859-2 -*-
\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{2. feladatsor, 63. feladat}
\begin{document}
\noindent
\emph{Feladat:} Állapítsuk meg, hogy melyik az $f$ függvény leggyakrabban felvett értéke!

\emph{Specifikáció:}\\
$f\colon[m,n]\to\Z$ \\
$A = \alatt{\Z}{m} \times \alatt{\Z}{n} \times \alatt{\Z}{i}$\\
$B = \alatt{\Z}{m'} \times \alatt{\Z}{n'}$\\
$Q = ( m=m' \es n=n' \es m\le n )$\\
$R = ( Q \es i\in[m,n] \es \forall j\in[m,n]\colon g(i)\ge g(j))$, ahol $g\colon[m,n]\to\N_0$ és $g(i)=\sum\limits_{j=i+1}^{n}\chi(f(i) = f(j))$.

A $g$ függvény ``trükkös''.  Azért elég a szummának $i+1$-től mennie,
mert az, hogy egy függvényargumentumhoz tartozó érték mennyiszer
fordul elő elég, hogy akkor egyezzen a $g$ függvényértékkel, amikor
először találjuk a szóban forgó értéket.  Például, ha az $f$ értékei
rendre $2,10,4,2,10,4,10$, akkor a $g$ függvényértékei $1, 2, 1, 0, 1,
0, 0$ lesznek, tehát igazából azt írja le a $g$ függvény, hogy az $f$
függvény aktuális értéke még mennyiszer fordul elő később.  De ennek a
maximumhelyén az $f$ függvény értéke számunkra pont a kívánt eredményt
adja.

Tehát visszavezetés a maximumkeresésre $g$-n, alteres általánosított
(a $max$ értékre nem vagyunk kiváncsiak).  Megjegyezzük, hogy az $i$
eredménykomponensben, a keresett elem indexét és nem az értékét adja
vissza a program, de ha mondjuk az értéket az $e$ komponensben
szeretnénk viszontlátni (a feladat szövegezéséhez ragaszkodván), akkor
a függvénykompozíció kiszámításának tételére hivatkozva a programot
megtoldhatjuk az $e:=f(i)$ szekvenciával a kívánt eredmény eléréséhez.

Mivel most tudunk olyan minimum értéket mondani, ami minden
elképzelhető értéknél kisebb, ``megúszhatjuk'', hogy a $g$ függvényt a
ciklus előtt is ki kelljen számolgatni, ezért a maximumkeresést kivételesen $m-1$-től indítjuk.

\begin{tabular}{cc}
\begin{minipage}{5cm}
\begin{tabular}{ccc}
  feladat &  & max. ker. \\
  \hline
  $-$ & \knyil & $max$ \\
  $g$ & \knyil & $f$
\end{tabular}
\end{minipage}
\begin{minipage}{10cm}
\begin{stuki}[7cm]
  \stm{i,k,max:=m-1,m-1,-1}
  \begin{WHILE}{4}{\stm{k\ne n}}
    \stm{z:=g(k+1)}
    \begin{IF}{1}{\stm{z > max}}
    \stm{i,max:=k+1,z}
    \ELSE
    \SKIP
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}
\end{minipage}
\end{tabular}

Most specifikáljuk és vezessük vissza számlálásra a $z:=g(k+1)$ nem
megengedett értékadást:

$A' = \alatt{\Z}{m} \times \alatt{\Z}{n} \times \alatt{\Z}{i} \times \alatt{\Z}{k} \times \alatt{\N_0}{z}$\\
$B' = \alatt{\Z}{m'} \times \alatt{\Z}{n'} \times \alatt{\Z}{i} \times \alatt{\Z}{k}$\\
$Q' = ( m=m' \es n=n' \es d=d' \es k=k' )$\\
$R' = ( Q \es z=\sum\limits_{j=i+1}^{n}\chi(f(i) = f(j))$

\begin{tabular}{ccc}
  feladat &  & számlálás \\
  \hline
  $i+1$ & \knyil & $m$ \\
  $n$ & \knyil & $n$ \\
  $f(i)=f(k+1)$ & \knyil & $\beta(i)$ \\
  $j$ & \knyil & $k$
\end{tabular}

\begin{stuki}[7cm]
  \stm{j,z:=i,0}
  \begin{WHILE}{3}{\stm{j\ne n}}
    \begin{IF}{1}{\stm{f(k+1)=f(j+1)}}
    \stm{z:=z+1}
    \ELSE
    \SKIP
    \end{IF}
    \stm{j:=j+1}
  \end{WHILE}
\end{stuki}

\end{document}