\documentclass[a4paper]{article}
\usepackage{progm}
\usepackage{eepic}
\analpacks
\analoldal{2. feladatsor, 52. feladat}
\begin{document}
\noindent
\emph{Feladat:} Adott két egybevágo $2n$ szög.  Mindkettõ oldalait véletlenszerûen kékre
vagy pirosra festettük.  Helyezzük egymásra a két sokszöget úgy, hogy a lehetõ legtöbb
helyen legyenek azonos színû oldalak egymáson!

Útmutatás:
Ábrázoljuk mindkét alakzat oldalait egy-egy $2n$ hosszú vektorral,
aminek minden eleme egy oldal színét tartalmazza.  Valósítsuk meg az $z:=$összehasonlít($x$) programot,
aminek $x$ paramétertérbeli változója és azt tartalamazza, hogy a második vektort mekkora eltolással
kell az elsõvel összevetni.  Az összehasonlítás eredménye az egyezõ oldalak száma.  Ezt a részprogramot
felhasználva az egész probléma már egy maximumkeresésre vezethetõ vissza.

\emph{Specifikáció:}\\
$\V = \vect([0..2n-1], \{\text{kék}, \text{piros}\})$\\
$A = \alatt{\V}{e} \times \alatt{\V}{m} \times \alatt{\N_0}{i}$\\
$B = \alatt{\V}{e'} \times \alatt{\V}{m'}$\\
$Q = ( m=m' \es e=e')$\\
$R = ( Q \es i\in [0..2n-1] \es \forall j\in[0..2n-1]:
\text{hasonlít}(j)\le\text{hasonlít}(i))$

A hasonlít függvény definíciója: $\forall i\in[0..2n-1]: \text{hasonlít}(i):=
\sum\limits_{k=0}^{2n-1}\chi(e[k]=m[(k+i)\text{ mod }2n])$.

Visszavezetés a maximum keresésre:

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

A visszavezetés alteres általánosított, mert a maximumértékre nem
vagyunk kívácsiak.  A stuktogramot felírása transzformáljuk az ismert
módszerekkel olyan alakúra, amiben ``hasonlít'' csak
$z:=\text{hasonlít}(\dots)$ alakban szerepel.

\begin{textblock}{1}(0.0,0.0)
\begin{stuki}
  \stm{i,k,max:=0,0,\text{hasonlít}(0)}
  \begin{WHILE}{3}{\stm{k \ne 2n-1}}
    \begin{CASE}{1}{2}
      \WHEN{\stm{\text{hasonlít}(k+1)\ge max}}
      \stm{i,max:=k+1,\text{hasonlít}(k+1)}
      \WHEN{\stm{\text{hasonlít}(k+1)\le max}}
      \SKIP
    \end{CASE}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}
\end{textblock}

\begin{textblock}{1}(8.0,0.0)
\begin{stuki}[6cm]
  \stm{z:=\text{hasonlít}(0)}
  \stm{i,k,max:=0,0,z}
  \begin{WHILE}{4}{\stm{k \ne 2n-1}}
    \stm{z:=\text{hasonlít}(k+1)}
    \begin{CASE}{1}{2}
      \WHEN{\stm{z \ge max}}
      \stm{i,max:=k+1,z}
      \WHEN{\stm{z \le max}}
      \SKIP
    \end{CASE}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}
\end{textblock}

\vspace{4cm}
Most pedig oldjuk meg a z:=hasonlít(j) feladatot:

$A = \alatt{\V}{e} \times \alatt{\V}{m} \times \alatt{\N_0}{z} \times \alatt{\N_0}{j}$\\
$B = \alatt{\V}{e'} \times \alatt{\V}{m'}$\\
$Q = ( m=m' \es e=e' \es j=j')$\\
$R = ( Q \es z=\sum\limits_{k=0}^{2n-1}\chi(e[k]=m[(k+j)\text{ mod }2n]))$

Ez pedig nem más, mint egy paraméteres ($j$) számlálás.

\begin{textblock}{1}(6.0,0.0)
\begin{stuki}[6cm]
  \stm{k,z:=-1,0}
  \begin{WHILE}{3}{\stm{k \ne 2n-1}}
    \begin{IF}{1}{\stm{e[k+1]=m[(k+1+j)\text{ mod }2n]}}
      \stm{z:=z+1}
      \ELSE
      \SKIP
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}
\end{textblock}

\begin{tabular}{ccc}
  részfeladat &  & számlálás \\
  \hline
  $0$ & \knyil & $m$ \\
  $2n-1$ & \knyil & $n$ \\
  $z$ & \knyil & $d$ \\
  $e[i]=m[(i+j)\text{ mod }2n]$ & \knyil & $\beta(i)$ \\
\end{tabular}

\end{document}
