% -*- coding: iso-8859-2 -*-
\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{2. feladatsor, 70-71-75-78-79-80. feladat}
\begin{document}
\noindent
\emph{Feladat:} Adjunk egy programozási tételt, aminek segítségével
megkereshető az $[m..n]$ intervallumon értelmezett $\beta$ tulajdonság
leghosszabb konstans igaz szeletének kezdőindexe és megállapítható a
szelet hossza.

\emph{Átfogalmazás:} \\
$R = (\text{kezdoindex}:\Z, \text{hossz}:\N_0)$\\
$\phi:[m-1,n]\nyil R$\\
$\phi(m-1) = (m, 0)$, 
$\forall i\in [m,n]: \phi(i) = F(i, \phi(i-1))$, ahol 
$F: [m,n] \times R \nyil R$ definíciója:\\
\[
F(i, z)=\left\{
\begin{array}{ll}
  (z.\text{kezdoindex}, z.\text{hossz}+1) & \text{, ha } \beta(i) \\
  (i+1, 0) & \text{, ha } \nem\beta(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
szolgáltatja.  Ha nincs $\beta$ tulajdonságú elem az intervallumban,
azt a hossz komponens 0 értéke jelzi.

\vspace{1.3cm}

\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+1 )$\\
$R = ( Q \es \exists i\in[m-1, n]: \phi(i)=\max \es \forall j\in[m-1, n]: \phi(j)\le \max)$

\begin{textblock}{1}(3.0,-1.5)
\begin{tabular}{ccc}
feladat &  & max. ker \\
\hline
$m-1$ & \knyil & $m$ \\
$n$ & \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:=m-1,m-1,\phi(m-1)}
  \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}

A visszavezetés alteres általánosított az $i$ szerint.

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{i,k,\max,z:=m-1,m-1,(m,0),(m,0)}
  \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}[7cm]
  \stm{k,\max,z:=m-1,(m,0),(m,0)}
  \begin{WHILE}{5}{\stm{k \ne n}}
    \begin{IF}[40]{1}{\stm{\nem\beta(k+1)}}
      \stm{z:=(k+2,0)}
      \ELSE
      \stm{z.\text{hossz}:=z.\text{hossz}+1}
    \end{IF}
    \begin{IF}[40]{1}{\stm{z.\text{hossz}\le \max.\text{hossz}}}
      \SKIP
      \ELSE
      \stm{\max:=z}
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

A program felírása közben az utófeltételben nem szereplő $i$-t, mivel
az csak értékadások baloldalán fordult elő, elhagytuk.

A most ismertetendő feladatok az utolsó kivételével mind ennek a
programozási tételnek a speciális esetei, így csak a $\beta$-t és a
struktogramot ismertetjük.

\emph{70. feladat:} Adott a 0,1 értékeket felvevő $f$ függvény.  Keressük
meg a függvény értelmezési tartományának azt az elemét, amely a
leghosszabb egyes-értéksorozat kezdete!

$\beta(i):=f(i)=1$

\begin{stuki}[7cm]
  \stm{k,\max,z:=m-1,(m,0),(m,0)}
  \begin{WHILE}{5}{\stm{k \ne n}}
    \begin{IF}[40]{1}{\stm{f(k+1)=0}}
      \stm{z:=(k+2,0)}
      \ELSE
      \stm{z.\text{hossz}:=z.\text{hossz}+1}
    \end{IF}
    \begin{IF}[40]{1}{\stm{z.\text{hossz}\le \max.\text{hossz}}}
      \SKIP
      \ELSE
      \stm{\max:=z}
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

\emph{75. feladat:} 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!

$n\bnyil n-1, \beta(i):=f(i+1)\ge f(i)$

\begin{stuki}[7cm]
  \stm{k,\max,z:=m-1,(m,0),(m,0)}
  \begin{WHILE}{5}{\stm{k \ne n-1}}
    \begin{IF}[40]{1}{\stm{f(i+1)<f(i)}}
      \stm{z:=(k+2,0)}
      \ELSE
      \stm{z.\text{hossz}:=z.\text{hossz}+1}
    \end{IF}
    \begin{IF}[40]{1}{\stm{z.\text{hossz}\le \max.\text{hossz}}}
      \SKIP
      \ELSE
      \stm{\max:=z}
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

\emph{78. feladat:} 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!

$m\bnyil x.\lob, n\bnyil x.\hib, f\bnyil x, \beta(i):=x_i\ne$ `,'

\begin{stuki}[7cm]
  \stm{k,\max,z:=x.\lob-1,(x.\lob,0),(x.\lob,0)}
  \begin{WHILE}{5}{\stm{k \ne x.\hib}}
    \begin{IF}[40]{1}{\stm{x_{k+1}=\text{`,'}}}
      \stm{z:=(k+2,0)}
      \ELSE
      \stm{z.\text{hossz}:=z.\text{hossz}+1}
    \end{IF}
    \begin{IF}[40]{1}{\stm{z.\text{hossz}\le \max.\text{hossz}}}
      \SKIP
      \ELSE
      \stm{\max:=z}
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

\emph{79. feladat:} Egy $f\colon[a,b]\nyil\Z$ függvény értelmezési
tartományának azon szakaszát, melynek két végpontja a függvény lokális
minimumhelye úgy, hogy a végpontok közötti elemek nem azok, a függvény
egy hegyének nevezzük. Adjuk meg a legszélesebb hegy kezdőpontját!

$m\bnyil a, n\bnyil b, \beta(i):=\nem ((i=a \vagy f(i-1)>f(i)) \es (i=b \vagy f(i+1)>f(i)))$

\begin{stuki}[10cm]
  \stm{k,\max,z:=a-1,(a,0),(a,0)}
  \begin{WHILE}{5}{\stm{k \ne b}}
    \begin{IF}[40]{1}{\stm{(i=a \vagy f(i-1)>f(i)) \es (i=b \vagy f(i+1)>f(i))}}
      \stm{z:=(k+2,0)}
      \ELSE
      \stm{z.\text{hossz}:=z.\text{hossz}+1}
    \end{IF}
    \begin{IF}[40]{1}{\stm{z.\text{hossz}\le \max.\text{hossz}}}
      \SKIP
      \ELSE
      \stm{\max:=z}
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

\emph{80. feladat:} Egy vektornak azt a szakaszát, amely csupa negatív
elemet tartalmaz úgy, hogy a szakaszt jobbról és balról nemnegatív
elem, vagy a vektor vége határolja, a vektor negatív szigetének
nevezzük. Adjuk meg az $x$ vektor legnagyobb negatív szigetének
kezdőindexét!

$m\bnyil x.\lob, n\bnyil x.\hib, f\bnyil x, \beta(i):=x_i<0$

\begin{stuki}[7cm]
  \stm{k,\max,z:=x.\lob-1,(x.\lob,0),(x.\lob,0)}
  \begin{WHILE}{5}{\stm{k \ne x.\hib}}
    \begin{IF}[40]{1}{\stm{x_{k+1}\ge 0}}
      \stm{z:=(k+2,0)}
      \ELSE
      \stm{z.\text{hossz}:=z.\text{hossz}+1}
    \end{IF}
    \begin{IF}[40]{1}{\stm{z.\text{hossz}\le \max.\text{hossz}}}
      \SKIP
      \ELSE
      \stm{\max:=z}
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}


\emph{71. feladat:} Egy függvény értelmezési tartományának azt a
szakaszát, amelyhez tartozó értékek negatívok, úgy hogy a szakaszt
jobbról és balról nemnegatív érték, vagy az értelmezési tartomány vége
határolja, a függvény negatív szigetének nevezzük. Adjuk meg az
függvény értelmezési tartományában a negatív szigetek számát!

Ez a feladat ugyanezen rekurzív függvény $\beta(i):=f(i)<0$
helyettesítéssel kapott változata mellett azon függvényértékek
megszámolásáról szól, amelyek hossz értéke 1.

$A = \alatt{\Z}{m} \times \alatt{\Z}{n} \times \alatt{N_0}{d}$\\
$B = \alatt{\Z}{m'} \times \alatt{\Z}{n'}$\\
$Q = ( m=m' \es n=n' \es m\le n+1 )$\\
$R = ( Q \es d = \sum\limits_{i=m}^n \chi(\phi(i)=1))$

\begin{stuki}[7cm]
  \stm{k,d,z:=m-1,0,(m,0)}
  \begin{WHILE}{5}{\stm{k \ne n}}
    \begin{IF}[40]{1}{\stm{f(k+1)\ge 0}}
      \stm{z:=(k+2,0)}
      \ELSE
      \stm{z.\text{hossz}:=z.\text{hossz}+1}
    \end{IF}
    \begin{IF}[40]{1}{\stm{z.\text{hossz}\ne1}}
      \SKIP
      \ELSE
      \stm{d:=d+1}
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

\end{document}
