% -*- coding: iso-8859-2 -*-
\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{2. feladatsor, 67. feladat}
\newcommand{\PONT}{\text{PONT}}
\newcommand{\db}{\text{db}}
\begin{document}
\noindent
\emph{Feladat:} Adott a síkon több darab pont egy vektorban.
Állapítsuk meg, melyik a két legtávolabbi pont!

\emph{Specifikáció:}\\
$R_{\PONT} = (x:\Z, y:\Z)$ \\
$\V = \vect(\Z, R_{\PONT})$ \\
$A = \alatt{\V}{v} \times \alatt{\N_0}{i} \times \alatt{R_{\PONT}}{p_1}\times\alatt{R_{\PONT}}{p_2}$ \\
$B = \alatt{\V}{v'}$\\
$Q = ( v=v' \es v.dom\ge 2)$\\
$R' = ( Q \es i\in[0, \db(v)-1] \es \forall j\in [0, \db(v)-1]: t(f(i))\ge t(f(j)))$ \\
$R = ( R' \es p_1=v_{v.\lob+f(i)_1} \es p_2=v_{v.\lob+f(i)_2})$

Ahol:
\begin{itemize}
\item $\db(v):=\frac{v.\dom (v.\dom-1)}{2}$, megadja, hogy a $v$
  vektorban hány összehasonlítandó pontpár van,
\item $f^{(-1)}:\No\times\No \nyil \No, \forall 0\le j<i\le n-1:
  f^{(-1)}(i,j) := \frac{i(i-1)}{2}+j$, bijektív megfeleltetés $[0,
  db(v)-1]$ intervallum elemei és a $(v.lob+i, v.lob+j)$ olyan
  indexpárok között, amik esetén $0\le j<i\le n-1$.  Tehát az $f$
  függvény inverze minden összehasonlítandó indexpárhoz a
  intervallum egy elemét rendeli egyértelműen.  Ez azt jelenti, hogy az
  $f$ függvény maga, az intervallumról az összehasonlítandó
  indexpárokra képez egyértelműen!  Ez nagyon szerencsés, úgyhogy
  számoljuk is ki az $f$ függvényt:

\begin{align*}
x &= \frac{i(i-1)}{2} \\
2x  &= i^2 - i \\
0 &= i^2 -i -2x \\
i &= \frac{1+\sqrt{1+8x}}{2} \quad\text{(ugyanis csak a pozitív gyök érdekes)} \\
f(x)_1 &= \left\lfloor \frac{1+\sqrt{1+8x}}{2}\right\rfloor \\
f(x)_2 &= x-\frac{f(x)_1(f(x)_1-1)}{2}\text{,}
\end{align*}

\item $t((i,j)):=(v_{v.\lob+i}.x-v_{v.\lob+j}.x)^2+(v_{v.\lob+i}.y-v_{v.\lob+j}.y)^2$, megadja két vektorindex által megjelölt pontok távolságnégyzetét.
\end{itemize}

Ha a kiszámolt $f$ függvényben lévő gyökvonás megengedett, akkor a
feladat egyszerűen egy maximumkeresés, ahol csak az $i$
eredménykomponensre vagyunk kiváncsiak, a maximumot pedig a $t(f(i))$
függvény szerint keressük.  A visszavezetés alteres általánosított (max).

\begin{tabular}{ccc}
  feladat &  & max. ker. \\
  \hline
  $0$ & \knyil & $m$ \\
  $\db(v)-1$ & \knyil & $n$ \\
  $t(f(i))$ & \knyil & $f(i)$
\end{tabular}

\begin{stuki}[9cm]
  \stm{i,k,max:=0,0, t(f(0))}
  \begin{WHILE}{3}{\stm{k\ne \db(v)-1}}
    \begin{IF}{1}{\stm{t(f(k+1)) > max}}
    \stm{i,max:=k+1,t(f(k+1))}
    \ELSE
    \SKIP
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
  \stm{(p_1,p_2):=v_{v.\lob+f(i)_1},v_{v.\lob+f(i)_2}}
\end{stuki}

\vspace{-1.3cm}\vbox{\hspace{3.6cm}$R'$}
\vspace{0.2cm}\vbox{\hspace{3.6cm}$R$}

\vspace{-4.3cm}$\left.\vbox{\vspace{1.7cm}}\hspace{13cm}\right\} S_1$

\vspace{1cm}

$R' = \lf((p_1,p_2):=v_{v.\lob+f(i)_1},v_{v.\lob+f(i)_2}, R)$, így az utolsó értékadás valóban helyes.

\pagebreak

Mi a helyzet, ha a gyökvonás nem megengedett?

Nos, ekkor vegyük észre, hogy az $f$ függvény megfogalmazható rekurzívan, az inverze ismerete nélkül közvetlenül is:
\begin{align*}
f &: \No\nyil\No\times\No \\
f(0) &:=(1,0)\\
\forall i>0: f(i) &:= F(i,f(i-1)) \\
F(i,x) &:=\begin{cases}
  (x_1+1, 0) & \text{, ha } x_1-1=x_2 \\
  (x_2, x_2+1) & \text{, ha } x_1-1\ne x_2
  \end{cases}
\end{align*}

$R_{\text{PONTPÁR}}=(p_1:R_{\PONT}, p_2:R_{\PONT})$\\
$A = \alatt{\V}{v} \times \alatt{R_{\text{PONTPÁR}}}{\max}$ \\
$B = \alatt{\V}{v'}$\\
$Q = ( v=v' \es v.dom\ge 2)$\\
$R' = ( Q \es \exists i\in[0, \db(v)-1]: \max = f(i) \es \forall j\in [0,
\db(v)-1]: \max\ge^* f(j))$, ahol a $\ge^*$ reláció pontpárokat
hasonlít össze a $t$ függvény segítségével, úgy, hogy $f(i)\ge^* f(j)$
acsa., ha $t(f(i)) \ge t(f(j))$.\\
$R = ( R' \es (p_1, p_2) = (v_{v.\lob+\max.1}, v_{v.\lob+\max.2}))$

Azaz ez egy alteres általánosított ($i$) visszavezetés az alábbi megfeleltetésekkel:

\begin{tabular}{ccc}
  feladat &  & max. ker. \\
  \hline
  $0$ & \knyil & $m$ \\
  $\db(v)-1$ & \knyil & $n$ \\
  $\ge^*$ & \knyil & $\ge$
\end{tabular}

Az $f$ rekurzív függvény helyettesíthető változóval.  Használjuk
fel azt is, hogy a $db(v)-1=k$ akkor teljesül először, amikor $z.1=n$:
\begin{stuki}[8cm]
  \stm{z:=(1,0)}
  \stm{i,k,max:=0,0, z}
  \begin{WHILE}{5}{\stm{z.1\ne n}}
    \begin{IF}{1}{\stm{z.1-1=z.2}}
      \stm{z:=(z.1+1,0)}
      \ELSE
      \stm{z.2:=z.2+1}
    \end{IF}
    \begin{IF}{1}{\stm{t(z) \ge t(max)}}
    \stm{i,max:=k+1,z}
    \ELSE
    \SKIP
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
  \stm{(p_1,p_2):=v_{\max.1}, v_{\max.2}}
\end{stuki}

A programban $i$ csak értékadások baloldalán szerepel és az
utófeltétel sem támaszkodik rá, eltávolítható.  Eltávolítása után a
programban $k$ csak értékadások baloldalán szerepel, tehát:
\begin{stuki}[8cm]
  \stm{max,z:=(1,0),(1,0)}
  \begin{WHILE}{4}{\stm{z.1\ne n}}
    \begin{IF}{1}{\stm{z.1-1=z.2}}
      \stm{z:=(z.1+1,0)}
      \ELSE
      \stm{z.2:=z.2+1}
    \end{IF}
    \begin{IF}{1}{\stm{t(z) \ge t(max)}}
    \stm{max:=z}
    \ELSE
    \SKIP
    \end{IF}
  \end{WHILE}
  \stm{(p_1,p_2):=v_{v.\lob+\max.1}, v_{v.\lob+\max.2}}
\end{stuki}

\end{document}