% -*- 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)) \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}