\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{2. feladatsor, felt. max. ker. \nyil max. ker.}
\begin{document}
\noindent
\emph{Feladat:} Adott az $[m,n]$ intervallumon értelmezett $\beta$ logikai értékű és $f$ egész értékű függvény.
\[
g:\Z\nyil\L\times\Z, \quad\forall i\in[m,n]:g(i):=(\beta(i), f(i))
\]

A $\L\times\Z$ halmaz elemei összehasonlíthatóak: akkor és
csak akkor legyen egy $a=(a_1, a_2)$ elem nagyobb vagy egyenlő egy
$b=(b_1, b_2)$ elemnél, ha $a_1$ igaz és $b_1$ hamis vagy $a_1$
és $b_1$ is igaz, de $a_2\ge b_2$.

Keressük meg a $g$ legnagyobb értékét és a hozzá tartozó argumentumot
az $[m,n]$ intervallumon!


\emph{Specifikáció:}\\
$\mathbb D=(\L:l, \Z:z)$ rekord, így $g$ felfogható, mint $g:\Z\nyil\mathbb D$ függvény.\\
$A = \alatt{\Z}{m} \times \alatt{\Z}{n} \times \alatt{\mathbb D}{\max} \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 \max=g(i) \es \forall j\in[m,n]: g(j)\le \max)$

\begin{tabular}{cccl}
  feladat &  & max. ker. & \\
  \hline
  $g(i)$ & \knyil & $f(i)$
\end{tabular}

A visszavezetés természetes.

\begin{stuki}
  \stm{k,i,\max := m,m,(\beta(m),f(m))}
  \begin{WHILE}{3}{\stm{k\ne n}}
    \begin{IF}[70]{1}{\stm{\beta(k+1) \es \nem \max.l \vagy \beta(k+1) \es \max.l \es f(k+1)\ge \max.z}}
      \stm{i,\max:=k+1, (\beta(k+1),f(k+1))}
      \ELSE
      \SKIP
    \end{IF}
    \stm{j:=j+1}
  \end{WHILE}
\end{stuki}

Helyettesítsük a max rekordkomponenst két változóval $l$-lel és
max-szal, valamint vegyük észre, hogy az elágazás igaz ágában
$\beta(k+1)$ szüségszerűen igaz!  Alakítsunk egy kicsit a feltételen
is, emeljünk ki $\beta(k+1)$-et!

\begin{stuki}
  \stm{k,i,l,\max := m,m,\beta(m),f(m)}
  \begin{WHILE}{3}{\stm{k\ne n}}
    \begin{IF}[70]{1}{\stm{\beta(k+1) \es (\nem l \vagy l \es f(k+1)\ge \max)}}
      \stm{i,l,\max:=k+1, \igaz,f(k+1)}
      \ELSE
      \SKIP
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

Vigyázat, a $\nem l \vagy l$ nem hagyható el a precedencia sorrend
miatt, az ``és'' erősebben köt!

A kitűzött feladat lényegében a feltételes maximumkeresés és a kapott
program is nagyon hasonlít hozzá.  Különbség, hogy mivel
maximumkeresésre vezettünk vissza, a program üres intervallumon nem
működik, az előfeltétel meg is követeli, hogy legalább egy eleme
legyen az intervallumnak.  Ez persze nem lényeges megszorítás, így
érdekes eredmény, hogy a maximumkeresés tekinthető olyan általánosnak,
mint a feltételes változata.  Trivalitás, hogy a másik irány is
teljesül (konstans igaz $\beta$ függvénnyel), így a két feladat
ekvivalens, ami az egyikre visszavezethető, biztos, hogy a másikra is
(esetleg kevésbé praktikusan).

\end{document}