\documentclass[a4paper]{article}
\usepackage{progm}
\usepackage{cancel}
\analpacks
\analoldal{2. feladatsor, 88. feladat}
\begin{document}
\noindent
\emph{Feladat:} Adott $n$ fiú és ugyanennyi lány. Egy $t$ logikai
mátrixban tároljuk a fiúk és lányok közötti szimpátiát (ez egy szim-
metrikus reláció) a következ képpen: ${t_i}_j$ igaz, ha az $i$-edik
fiú és a $j$-edik lány szimpatizál egymással, hamis ellenben. A
feladat az, hogy ha lehet, akkor párosítsuk (házasítsuk) össze oket
úgy, hogy minden párban a felek szimpatizáljanak!

A logikai mátrixunk tehát négyzetes.  Legyen olyan, hogy minden sorban
az indexhatárok azonosak a sorok indexhatárával:
$\M=\vect(\Z,\vect(\Z,\Z))$ és $I_\M(t)=(\forall j\in[t.\lob,t.\hib]:
t_j.\lob=t.\lob \es t_j.\hib=t.\hib)$

Ekkor a feladat az, hogy keressünk a $t$ mátrix minden sorához egy-egy
olyan oszlopindexet, hogy egy oszlopindexet sem használunk kétszer, de
minden sorban a kiválaszott oszlopindexű elem igaz.

A visszalépéses keresés jelöléseit konkretizálva megkapható a mi feladatunk:\\
$N := t.\dom$ (a keresés ``dimenziószáma'')\\
$\forall i\in[1..N]: U_i:=[t.\lob,t.\hib]$ (minden dimenzióban egy oszlopindexet keresünk) \\
$\forall i\in[1..N]:\sigma_i=t.\dom$ (tehát minden dimenzió $t.\dom$ lehetséges értéket tartalmaz)\\
$\varphi(i_1,i_2,\dots,i_N):=(i_1+t.\lob, i_2+t.\lob, \dots, i_N+t.\lob)$ ($[0..\sigma_1-1]^N \nyil [t.\lob..t.\hib]^N$ bijekció)\\
$\rho_0:=\text{Igaz} \es \forall i\ge1:\rho_i(u):=(\forall j\in[1,i]:{t_{t.\lob+j-1}}_{u.j}
\es \forall j,k\in[1,i]: (j\ne k)\nyil u.j\ne u.k)$ \\ \hbox{}\hspace{1cm} (az i. sorig a
kiválasztott párok szimpatizálnak és egy lányt sem osztottunk ki két
fiúhoz)\\
Ez a $\rho$ valóban teljesíti a tételben szereplő négy tulajdonságot!

Így a megoldás a visszalépéses keresés szerint:
\begin{stuki*}[7cm]{$\text{növel}(\nu_0, \nu, m)$}
  \stm{\nu_0:=1}
  \begin{WHILE}{2}{\stm{\nu_0\ne 0 \es m\ne 0}}
    \begin{IF}{1}{\stm{\nu_m=\sigma_m-1}}
      \stm{m,\nu_m:=m-1,0}
      \ELSE
      \stm{\nu_0,\nu_m:=0,\nu_m+1}
    \end{IF}
  \end{WHILE}
\end{stuki*}

\begin{stuki*}[5cm]{$\text{keres}(\nu, m, l)$}
  \stm{m,l:=m-1, \igaz}
  \begin{WHILE}{2}{\stm{l \es m\ne n}}
    \stm{l:=\rho_{m+1}(\varphi(\nu))}
    \stm{m:=m+1}
  \end{WHILE}
\end{stuki*}

Amikor a keres a $\rho_{m+1}$-et kiértékeli, $\rho_m$ már biztosított,
így elég ellenőríznünk, hogy a soronkövetkező lány és fiú szimpatizál,
illetve azt, hogy a most beosztott párból a lányt már nem osztottuk ki
korábban:
\begin{stuki*}[6cm]{$l:=\rho_{m+1}(\varphi(\nu))$}
  \stm{k,l:=0,{t_{t.lob+m}}_{\nu_{m+1}+t.\lob}}
  \begin{WHILE}{2}{\stm{l \es k\ne m}}
    \stm{l:=\nu_{m+1}\cancel{+t.lob}\ne\nu_{k+1}\cancel{+t.lob}}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki*}

\begin{stuki}[6cm]
  \stm{\nu,\nu_0,m:=(0,0,0,\dots,0), 0, 1}
  \stm{\text{keres}(\nu, m, l)}
  \begin{WHILE}{3}{\stm{\nem l\es\nu_0 = 0}}
    \stm{\text{növel}(\nu_0, \nu, m)}
    \begin{IF}{1}{\stm{\nu_0 = 0}}
      \stm{\text{keres}(\nu, m, l)}
      \ELSE
      \SKIP
    \end{IF}
  \end{WHILE}
\end{stuki}

\end{document}