\documentclass[a4paper]{article}
\usepackage{progm}
\usepackage{epsfig}
\analpacks
\analoldal{2. zárthelyi dolgozat, 2006. 03. 30.}
\pagestyle{empty}
\newcommand{\zhpeldak}{
\begin{center}Bevezetés a programozáshoz 2., 2. zárthelyi dolgozat\\2006. március 30. (csütörtök) 8 óra\end{center}

Specifikáld az alábbi feldatokat, majd add meg a megoldó programokat
a visszavezetés módszerével!

\emph{1. Feladat} (10 pont)\\Keressük meg az $[a,b]$ intervallumon
értelmezett, egész értékű $f$ függvénynek az első $n$-nél kisebb vagy
0 értékét!

\emph{Specifikáció:}\\
$A = \alatt{\N}{a} \times \alatt{\N}{b} \times \alatt{\Z}{n} \times \alatt{\N}{i} \times \alatt{\L}{l}$\\
$B = \alatt{\N}{a'} \times \alatt{\N}{b'} \times \alatt{\Z}{n'}$\\
$Q = ( a=a' \es b=b' \es a\le b+1 \es n=n')$\\
$R = ( Q \es l=(\exists j\in[a..b]:(f(j)<n \vagy f(j)=0)) \es l\nyil(i\in[a..b] \es 
(f(i)<n \vagy f(i)=0) \es \forall j\in[a..i-1]:(f(j)\ne n \es f(j) \ne 0)))$

A specifikáció nagyon hasonló a lin. ker. 2.8 programozási tételéhez.  Az
eltéréseket az alábbi táblázattal foglalhatjuk össze:

\begin{tabular}{ccc}
feladat &  & lin. ker. 2.8 \\
\hline
$a$ & \knyil & $m$ \\
$b$ & \knyil & $n$ \\
$f(i)=0 \vagy f(i)<n$ & \knyil & $\beta(i)$
\end{tabular}

Ez a visszavezetés nem természetes, mert az állapottér bővebb és a
helyettesítő táblázatban a $\beta(i)$ helyettesítésekor fel is
használjuk ezt a plusz komponenst.  Ugyanakkor megjegyezhetjük, hogy a
bevezetett $n$ az előfeltétel szerint adott értékű és a program során
nem változik (az utófeltételben is szerepel rejtve a $n=n'$).
Amennyiben ezek a feltételek teljesülnek egy ilyen kiegészítő
komponensre, akkor őt a visszavezetés \emph{paraméterének} nevezzük,
mivel ilyenkor a visszavezetés \emph{paraméteres visszavezetés}.

\begin{stuki}
  \stm{i,l:=a-1,\hamis}
  \begin{WHILE}{2}{\stm{\nem l \es i \ne b}}
    \stm{l:=(f(i+1)=0 \vagy f(i+1)<n)}
    \stm{i:=i+1}
  \end{WHILE}
\end{stuki}

{2. Feladat} (10 pont)\\Keressük meg az $x$ vektorban a
legnagyobb olyan értéket, amely egyenlő a közvetlen szomszédai
átlagával!

\emph{Specifikáció:}\\
$\V = \vect(\Z, \Z)$ \\
$A = \alatt{\V}{x} \times \alatt{\Z}{max} \times \alatt{\L}{l}$\\
$B = \alatt{\V}{x'}$\\
$Q = ( x=x' )$\\
$R = ( Q \es l=(\exists j\in[x.lob+1..x.hib-1]:(x_j=\frac{x_{j-1}+x_{j+1}}{2})) \es l\nyil\exists i\in[x.lob+1..x.hib-1]:
(x_i=\frac{x_{i-1}+x_{i+1}}{2} \es \forall j\in[x.lob+1..x.hib-1]:(x_j=\frac{x_{j-1}+x_{j+1}}{2}\nyil x_j\le x_i) \es max=x_i))$

\begin{tabular}{ccc}
feladat &  & felt. max. ker. \\
\hline
$x.lob+1$ & \knyil & $m$ \\
$x.hib-1$ & \knyil & $n$ \\
$x_i=\frac{x_{i-1}+x_{i+1}}{2}$ & \knyil & $\beta(i)$
\end{tabular}

A visszavezetés alteres általánosított.

\begin{stuki}[17cm]
  \stm{k,l:=x.lob,\hamis}
  \begin{WHILE}{4}{\stm{k \ne x.hib-1}}
    \begin{CASE}{2}{9}
      \WHEN[2]{\stm{x_{k+1}\ne\frac{x_k+x_{k+2}}{2}}}
      \SKIP
      \WHEN[3]{\stm{x_{k+1}=\frac{x_k+x_{k+2}}{2}\es\nem l}}
      \stm{l,i,max:=\igaz,k+1,x_{k+1}}
      \WHEN[4]{\stm{x_{k+1}=\frac{x_k+x_{k+2}}{2} \es l}}
      \begin{CASE}{1}{2}
        \WHEN{\stm{x_{k+1}\ge max}}
        \stm{i,max:=k+1,x_{k+1}}
        \WHEN{\stm{x_{k+1}\le max}}
        \SKIP
      \end{CASE}
    \end{CASE}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

\emph{3. Feladat} (12 pont)\\Adott a kezdőpontja szerint növekvő
sorrendben a számegyenes $N$ darab intervalluma.  Mutassunk egy olyat,
amelyikbe a (szinén adott) $k$ beleesik.\\Megoldás lineáris keresés
3.0-val: +2 pont.

\emph{Specifikáció:}\\
$Iv = (ah:\Z, fh:\Z)$ \\
$I_{Iv}(i)=(i.ah\le i.fh+1)$ \\
$\V = \vect(\Z, Iv)$ \\
$A = \alatt{\V}{v} \times \alatt{\Z}{k} \times \alatt{\Z}{i} \times \alatt{\L}{l}$ \\
$B = \alatt{\V}{v'} \times \alatt{\Z}{k'}$\\
$Q = ( v=v' \es k=k' \es v.hib-v.lob+1=N \es \forall i\in[v.lob..v.hib-1]: v_i.ah\le v_{i+1}.ah)$\\
$R = ( Q \es l=(\exists j\in[v.lob, v.hib]:v_j.ah\le k \le v_j.fh) \es l\knyil(i\in[v.lob,v.hib]\es v_i.ah\le k \le v_j.fh))$

\begin{tabular}{ccc}
  feladat &  & lin. ker. 3.0 \\
  \hline
  $l$ & \knyil & $u$ \\
  $g$ & \knyil & $v$ \\
  $v.lob$ & \knyil & $m$ \\
  $v_i.ah\le k \le v_i.fh$ & \knyil & $\gamma(i)$ \\
  $i>v.hib \vagy v_i.ah > k$ & \knyil & $\delta(i)$ \\
\end{tabular}

A visszavezetés általánosított (a lin. ker. 3.0 nem csak N hosszú
intervallumokra működik), paraméteres (k szerint).  Vegyük észre, hogy
a $Q$-ban lévő rendezettségi kikötést is figyelve az $R$ feltétel
gyengébb, mint a lin. ker. 3.0-ból helyettesítéssel kapott feltétel,
emiatt is általánosított ez a visszavezetés.

\begin{stuki}
  \stm{i,l,g:=v.lob-1,\hamis,\hamis}
  \begin{WHILE}{2}{\stm{\nem l \es \nem g}}
    \stm{l,g:=v_{i+1}.ah\le i \le v_{i+1}.fh,i+1>v.hib \vagy v_{i+1}.ah > k}
    \stm{i:=i+1}
  \end{WHILE}
\end{stuki}

\emph{4. Feladat} (14 pont)\\Adjuk meg az $f$ függvény értelmezési
tartományának azt a leghosszabb szakaszát, amelyen belül az értékek
növekevőek!\\Megoldás rekurzív függvénnyel: +5 pont.

\emph{Átfogalmazás:} \\
$R = (\text{kezdoindex}:\Z, \text{hossz}:\N_0)$\\
$\phi:[m,n]\nyil R$\\
$\phi(m) = (m, 1)$, 
$\forall i\in [m+1,n]: \phi(i) = F(i, \phi(i-1))$, ahol 
$F: [m+1,n] \times R \nyil R$ definíciója:\\
\[
F(i, x)=\left\{
\begin{array}{ll}
  (x.\text{kezdoindex}, x.\text{hossz}+1) & \text{, ha } f_{i-1}\le f_i \\
  (i, 1) & \text{, egyébként}
\end{array}
\right.
\]

Ezzel a $\phi$ függvénnyel a feladat a maximum keresésre vezethető
vissza.  A $\phi$ fv. maximumát keressük, az $R$ típus rendezettségét
annak hossz komponense adja.  Az eredményszakasz kezdőindexét a
megtalált $max$ érték kezdoindex nevű komponensében szolgáltatja a
program, míg a növekvő rész utolsó értéke a kezdoindex+hossz-1
képlettel számolható.

\vspace{1.5cm}

\emph{Specifikáció:}\\
$A = \alatt{\Z}{m} \times \alatt{\Z}{n} \times \alatt{R}{max}$\\
$B = \alatt{\Z}{m'} \times \alatt{\Z}{n'}$\\
$Q = ( m=m' \es n=n' \es m\le n )$\\
$R = ( Q \es \exists i\in[m, n]: \phi(i)=max \es \forall
j\in[m, n]: \phi(j).\text{hossz}\le max.\text{hossz})$

\begin{textblock}{1}(3.0,-1.5)
\begin{tabular}{ccc}
feladat &  & max. ker \\
\hline
$\phi(i)$ & \knyil & $f(i)$
\end{tabular}
\end{textblock}

\begin{textblock}{1}(6.1,-2.3)
\begin{stuki}[8cm]
  \stm{i,k,max:=m,m,\phi(m)}
  \begin{WHILE}{3}{\stm{k \ne n}}
    \begin{CASE}{1}{2}
      \WHEN{\stm{\phi(k+1)\ge max}}
      \stm{i,max:=k+1,\phi(k+1)}
      \WHEN{\stm{\phi(k+1)\le max}}
      \SKIP
    \end{CASE}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}
\end{textblock}

Felhasználva a rekurzív függvény változóval való helyettesítésének
programtranszformációs módszerét $\phi$-re és azt a tényt, hogy két
$R$-beli elemet a hossz komponens alapján hasonlítunk össze:

\begin{stuki}[6cm]
  \stm{z:=(m,1)}
  \stm{i,k,max:=m,m,z}
  \begin{WHILE}{4}{\stm{k \ne n}}
    \stm{z:=F(k+1, z)}
    \begin{IF}{1}{\stm{z.\text{hossz}>max.\text{hossz}}}
      \stm{i,max:=k+1,z}
      \ELSE
      \SKIP
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

Ha ismerjük az esetszétválasztással definiált függvény kiszámításának
programozási tételét, akkor ebből megkaphatjuk a megoldó programot, ha
azt $F$-re alkalmazzuk:

\begin{stuki}[10cm]
  \stm{z:=(m, 1)}
  \stm{i,k,max:=m,m,z}
  \begin{WHILE}{5}{\stm{k \ne n}}
    \begin{IF}{1}{\stm{f(k)\le f(k+1)}}
      \stm{z:=(z.\text{kezdoindex},z.\text{hossz}+1)}
      \ELSE
      \stm{z:=(k+1, 1)}
    \end{IF}
    \begin{IF}{1}{\stm{z.\text{hossz}>max.\text{hossz}}}
      \stm{i,max:=k+1,z}
      \ELSE
      \SKIP
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

\emph{5. Feladat} (14 pont)\\Adott az $x$ vektor, amelynek elemei
karakterek.  A vektor szavakat tartalmaz, amiket egy-egy vessző
választ el egymástól.  Adjuk meg a leghosszabb szónak a
kezdőindexét!\\Megoldás rekurzív függvénnyel: +5 pont.

\emph{Átfogalmazás:} \\
$R = (\text{kezdoindex}:\Z, \text{hossz}:\N_0)$\\
$\phi:[x.lob-1,x.hib]\nyil R$\\
$\phi(x.lob-1) = (x.lob, 0)$,
$\forall i\in [x.lob,x.hib]: \phi(i) = F(i, \phi(i-1))$, ahol 
$F: [x.lob,x.hib] \times R \nyil R$ definíciója:\\
\[
F(i, y)=\left\{
\begin{array}{ll}
  (y.\text{kezdoindex}, y.\text{hossz}+1) & \text{, ha } x_i\ne',' \\
  (i+1, 0) & \text{, ha } x_i= ','
\end{array}
\right.
\]

Ezzel a $\phi$ függvénnyel a feladat a maximum keresésre vezethető
vissza.  A $\phi$ fv. maximumát keressük, az $R$ típus rendezettségét
annak hossz komponense adja.  Az eredményt a megtalált $max$ érték
kezdoindex nevű komponensében szolgáltatja a program.  (Megjegyzés: ha
a feltételes maximumkeresésre vezetnénk vissza a feladatot, akkor egy
bonyolultabb stuktogram árán egy sokkal kevesebb összehasonlítást
végző programot kapnánk.)

\vspace{2cm}

\emph{Specifikáció:}\\
$\V = \vect(\Z, \text{Ch})$ \\
$A = \alatt{\V}{x} \times \alatt{R}{max}$\\
$B = \alatt{\V}{x'}$\\
$Q = ( x=x' \es x.dom>0 )$\\
$R = ( Q \es \exists i\in[x.lob, x.hib]: \phi(i)=max \es \forall
j\in[x.lob, x.hib]: \phi(j).\text{hossz}\le max.\text{hossz})$

\begin{textblock}{1}(3.0,-1.5)
\begin{tabular}{ccc}
feladat &  & max. ker \\
\hline
$x.lob$ & \knyil & $m$ \\
$x.hib$ & \knyil & $n$ \\
$\phi(i)$ & \knyil & $f(i)$
\end{tabular}
\end{textblock}

\begin{textblock}{1}(6.1,-2.5)
\begin{stuki}[8cm]
  \stm{i,k,max:=x.lob,x.lob,\phi(x.lob)}
  \begin{WHILE}{3}{\stm{k \ne x.hib}}
    \begin{CASE}{1}{2}
      \WHEN{\stm{\phi(k+1)\ge max}}
      \stm{i,max:=k+1,\phi(k+1)}
      \WHEN{\stm{\phi(k+1)\le max}}
      \SKIP
    \end{CASE}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}
\end{textblock}

Felhasználva a rekurzív függvény változóval való helyettesítésének
programtranszformációs módszerét $\phi$-re és azt a tényt, hogy két
$R$-beli elemet a hossz komponens alapján hasonlítunk össze:

\begin{stuki}[6cm]
  \stm{z:=(x.lob, 0)}
  \stm{z:=F(x.lob, z)}
  \stm{i,k,max:=x.lob,x.lob,z}
  \begin{WHILE}{4}{\stm{k \ne x.hib}}
    \stm{z:=F(k+1, z)}
    \begin{IF}{1}{\stm{z.\text{hossz}>max.\text{hossz}}}
      \stm{i,max:=k+1,z}
      \ELSE
      \SKIP
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

Ha ismerjük az esetszétválasztással definiált függvény kiszámításának
programozási tételét, akkor ebből megkaphatjuk a megoldó programot, ha
azt $F$-re alkalmazzuk:

\begin{stuki}[10cm]
  \stm{z:=(x.lob, 0)}
  \begin{IF}{1}{\stm{x.lov=','}}
    \stm{z:=(x.lob+1,0)}
    \ELSE
    \stm{z:=(z.\text{kezdoindex},z.\text{hossz}+1)}
  \end{IF}
  \stm{i,k,max:=x.lob,x.lob,z}
  \begin{WHILE}{5}{\stm{k \ne x.hib}}
    \begin{IF}{1}{\stm{x_{k+1}=','}}
      \stm{z:=(k+2,0)}
      \ELSE
      \stm{z:=(z.\text{kezdoindex},z.\text{hossz}+1)}
    \end{IF}
    \begin{IF}{1}{\stm{z.\text{hossz}>max.\text{hossz}}}
      \stm{i,max:=k+1,z}
      \ELSE
      \SKIP
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}
}
\begin{document}

\noindent

\zhpeldak

\end{document}