% -*- coding: iso-8859-2 -*-
\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{2. feladatsor, 64. feladat}
\begin{document}
\noindent
\emph{Feladat:} Határozzuk meg az $f$ függvénynek azt az
értékét, amit a legtöbb nála nagyobb elem előz meg!

\emph{Specifikáció:}\\
$f\colon[m,n]\to\Z$ \\
$A = \alatt{\Z}{m} \times \alatt{\Z}{n} \times \alatt{\Z}{i} \times \alatt{\Z}{e}$\\
$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=m}^{i-1}\chi(f(i)< f(j))$\\
$R = ( R' \es e=f(i))$

Látható, hogy $R' \kov \lf(e:=f(i), R)$.

Visszavezetés a maximumkeresésre, alteres általánosított (a $\max$
értékre nem vagyunk kiváncsiak).

\begin{tabular}{ccc}
  feladat &  & max. ker. \\
  \hline
  $-$ & \knyil & $\max$ \\
  $g$ & \knyil & $f$
\end{tabular}

\begin{tabular}{rcl}
  \begin{parbox}[t]{0cm}{
      \vspace{-4.6cm}\vbox{$Q$}
      \vspace{3.4cm}\vbox{$R'$}
      \vspace{0.2cm}\vbox{$R$}
    }\end{parbox} &
  \begin{stukibox}[7cm]
    \stm{i,k,\max:=m,m,0}
    \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}
    \stm{e:=f(i)}
  \end{stukibox} &
  \hspace{-0.3cm}\parbox{0.5cm}{\vspace{-4.3cm}{$\left.\vbox{\vspace{1cm}}\right\}$}}
  \parbox{8cm}{\vspace{-4.3cm}
    A $g(k+1)$ függvényt helyettesítettuk a $z$ változóval a program ezen részében:
     \begin{stuki}[8cm]
       \begin{IF}{1}{\stm{g(k+1) > \max}}
         \stm{i,\max:=k+1,g(k+1)}
         \ELSE
         \SKIP
       \end{IF}
     \end{stuki}
   }
\end{tabular}

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

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

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

\begin{stuki}[7cm]
  \stm{j,z:=m-1,0}
  \begin{WHILE}{3}{\stm{j\ne k}}
    \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}