\documentclass[a4paper]{article}
\usepackage{progm}
\usepackage{verbatim}
\analpacks
\analoldal{}
\pagestyle{empty}
\begin{document}
\noindent

``Program testing can be used to show the presence of bugs, but never to show their absence!''\\
--- Edsger Dijkstra



\begin{center}Programozási alapismeretek 1., csoport ZH\\2006. december 4.\end{center}

\emph{1. Feladat}\\Specifikáld a következõ feladatot: adott egy
egészértékû, az $[1..n]$ intervallumon értelmezett $f$ függvény (ahol
az $n$ szintén adott érték).  Keressük meg a legnagyobb olyan
függvényértéket, ami hárommal osztható!  Az állapottér $l$ logikai
változójában jelezzük azt, hogy egyáltalán van-e hárommal osztható
érték a függvényértékek között, ha $l$ igaz, csak akkor követeljük
meg, hogy a $max$ a maximális értéket, míg $j$ az indexét tartalmazza!
(15 pont)

\emph{Megoldás:}\\
$f:[1,n]\nyil\Z$\\
$A=\alatt{\N}{n}\times\alatt{\L}{l}\times\alatt{\Z}{max}\times\alatt{\N}{j}$\\
$B=\alatt{\N}{n'}$\\
$Q=(n=n')$\\
$R=(Q \es l=(\exists i\in [1,n]: 3|f(i)) \es l\nyil(j\in[1,n] \es 3|f(j) \es max=f(j) \es \forall i\in[1,n]: (3|f(i)\nyil f(i)\le max)))$

\emph{2. Feladat}\\Az 1. feladatot megoldottam UNIX scripttel:
\verbatiminput{keres}
\begin{itemize}
  \item Írd fel a csillagok között lévõ részprogram struktogramját!
  Használj olyan matematikai jelöléseket, amit struktogramokban és
  specifikáció során szoktunk, azaz a struktogramban pl. az $f$
  függvényre szerepeljenek a vizsgálatok és ne kezeld benne a szamok
  nevû fájlt! (10 pont)

\emph{Megoldás:}\\
\begin{stuki}[16cm]
  \stm{i,l:=0,\hamis}
  \begin{WHILE}{5}{\stm{i\ne n}}
    \begin{IF}[90]{3}{\stm{f(i+1)\text{ mod }3 = 0}}
      \begin{IF}[35]{2}{\stm{\nem l}}
        \stm{l,max,j:=\igaz,f(i+1),i+1}
        \ELSE
        \begin{IF}{1}{\stm{f(i+1)>max}}
          \stm{max,j:=f(i+1),i+1}
          \ELSE
          \SKIP
        \end{IF}
      \end{IF}
      \ELSE
      \SKIP
    \end{IF}
    \stm{i:=i+1}
  \end{WHILE}
\end{stuki}

  \item Írd fel, hogyha a $21, 43, 11, 9, 81, 24, 23$ számok közül
  szeretnéd a programmal megkeresni a legnagyobb hárommal oszhatót,
  akkor milyen input fájlt kell írnod! (5 pont)

\emph{Megoldás:}\\\texttt{21:43:11:9:81:24:23}

  \item Végezd el a program papíros ``futtatását'' az említett esetre,
  legyen látható, hogy a program a futása során hogyan határozza meg a
  $81$-et! (5 pont)

\emph{Megoldás:}$n=7$ végig, a többi változó:

\begin{tabular}{cccc}
  i & l & j & max \\
  \hline
  0 & \hamis & - & - \\
  0 & \igaz & 1 & 21 \\
  1 & \igaz & 1 & 21 \\
  2 & \igaz & 1 & 21 \\
  3 & \igaz & 1 & 21 \\
  4 & \igaz & 1 & 21 \\
  4 & \igaz & 5 & 81 \\
  5 & \igaz & 5 & 81 \\
  6 & \igaz & 5 & 81 \\
  7 & \igaz & 5 & 81
\end{tabular}
\end{itemize}

\emph{3. Feladat}\\Specifikáld a következõ feladatot: állapítsuk meg,
hogy az adott $[m,n]$ intervallumban van-e prímszám! (10 pont)

\emph{Megoldás:}\\
$A=\alatt{\N}{m}\times\alatt{\N}{n}\times\alatt{\L}{l}$\\
$B=\alatt{\N}{m'}\times\alatt{\N}{n'}$\\
$Q=(n=n' \es m=m' \es m\le n+1)$\\
$R=(Q \es l=(\exists i \in [m,n]: prim(i)))$

\emph{4. Feladat}\\Specifikáld az alábbi feladatot: állapítsuk meg az
adott $n$ természetes szám valódi páros osztóinak a számát! (5 pont)

\emph{Megoldás:}\\
$A=\alatt{\N}{n}\times\alatt{\N_0}{o}$\\
$B=\alatt{\N}{n'}$\\
$Q=(n=n')$\\
$R=(Q \es o=\sum\limits_{i=2}^{n-1}\chi(2|i \es i|n))$

\emph{5. Feladat}\\Tekintsük az alábbi programot:
\begin{stuki}
\stm{k,d:=2,0}
\begin{WHILE}{3}{\stm{k < n}}
  \begin{IF}{1}{\stm{(n\text{ mod }k)=0 \es (k\text{ mod }2)=0}}
      \stm{d:=d+1}
      \ELSE
      \SKIP
  \end{IF}
  \stm{k:=k+1}
\end{WHILE}
\end{stuki}
\begin{itemize}
\item Írd fel UNIX szkripttel! (5 pont)

\emph{Megoldás:}
\verbatiminput{osztok}

\item Írd fel a példalefutásokat n=8-ra és n=10-re! (5 pont)

\emph{Megoldás:}

\begin{tabular}{cccc}
  k & d \\
  \hline
  2 & 0 \\
  2 & 1 \\
  3 & 1 \\
  4 & 1 \\
  4 & 2 \\
  5 & 2 \\
  6 & 2 \\
  7 & 2 \\
  8 & 2 \\
\end{tabular} \hspace{5cm}
\begin{tabular}{cccc}
  k & d \\
  \hline
  2 & 0 \\
  2 & 1 \\
  3 & 1 \\
  4 & 1 \\
  4 & 1 \\
  5 & 1 \\
  6 & 1 \\
  7 & 1 \\
  8 & 1 \\
  9 & 1 \\
  10 & 1 \\
\end{tabular}

\end{itemize}
\end{document}
