\documentclass[a4paper]{article}

\usepackage{slovene}

\title{Devete vaje iz ra\v{c}unalni\v{s}tva}
\author{Mojca Murovec}
\date{08.12.1998}

\begin{document}
\maketitle

\section{Dopolnilo k zgledu \texttt{zaporedj.c}}

Na prej\v{s}njih vajah smo s pomo\v{c}jo rekurzije napisali program,
ki nam je ra\v{c}unal \v{c}lene in vsoto poljubnega aritmeti\v{c}nega
zaporedja. Pri programu je bila te\v{z}ava, da se \v{c}leni niso
nehali izpisovati, ker program ni imel ustavljalnega pogoja in se je
izvajal v neskon\v{c}nost. Naj ponovim, zaporedje smo se\v{s}tevali
takole:
%
\begin{enumerate}
\item najprej se\v{s}tejemo ostale \v{c}lene zaporedja z ukazom:
%
{\tt
\begin{verbatim}
 vsota = sestej_zaporedje1(zacetni_clen + korak, korak,
                           stevilo_clenov - 1);
\end{verbatim}
}


\item vsoti pri\v{s}tejemo \v{s}e za\v{c}etni \v{c}len
  aritmeti\v{c}nega zaporedja z:
%
\[
\texttt{vsota += zacetni\_clen;}
\]
\end{enumerate}

Pri tem je nastala prej omenjena te\v{z}ava. Program se ni znal
ustaviti, saj je posku\v{s}al se\v{s}teti neskon\v{c}no
aritmeti\v{c}no zaporedje.

Pri se\v{s}tevanju zaporedja smo zato omejili \v{s}tevilo
se\v{s}tetih \v{c}lenov. Koliko \v{c}lenov smo se\v{s}teli dolo\v{c}a
parameter \verb+ int stevilo_clenov +, ki se nahaja v glavi definicije
funkcije:
%
{\tt
\begin{verbatim}
  int sestej_zaporedje1(int zacetni_clen, int korak,
                        int stevilo_clenov)}
\end{verbatim}
}
%

Dokon\v{c}no napako popravimo takole:
%
\newline
%
Dodati moramo pogoj, ki, ko je \v{s}tevilo \v{c}lenov aritmeti\v{c}nega
zaporedja $0$, vrne vsoto $0$ (kot nam to prika\v{z}e program). V
primeru, ko je \v{s}tevilo \v{c}lenov zaporedja ve\v{c}je od $0$, je
vsota enaka vsoti preostalih \v{c}lenov aritmeti\v{c}nega zaporedja,
ki ji pri\v{s}tejemo za\v{c}etni \v{c}len. To izvedemo z:
%
{\tt
\begin{verbatim}
int sestej_zaporedje1(int zacetni_clen, int korak,
                      int stevilo_clenov)
{
  int vsota;
  if(stevilo_clenov ==0)
    vsota =0;
  else
  {
              /* sestej ostale clene zaporedja */
    vsota = sestej_zaporedje1(zacetni_clen + korak, korak,
                              stevilo_clenov - 1);
              /* pristej zacetni clen */
    vsota += zacetni_clen;
  };
              /* vrni vsoto */
  return vsota;
} /* sestej_zaporedje1 */
\end{verbatim}
}

\section{Geometrijsko zaporedje}

Program spremenimo tako, da nam bo namesto aritmeti\v{c}nega zaporedja
izpisoval geometrijsko zaporedje in vsoto teh \v{c}lenov zaporedja.
%
\begin{itemize}
\item Izpis izvedemo s pomo\v{c}jo zanke \texttt{for}. Torej:
%
{\tt
\begin{verbatim}
void izpisi_geo_zaporedje(int zacetni_clen, int kolicnik,
                          int stevilo_clenov)
{
  int a;             /* tekoci clen zaporedja */
  int i;             /* indeks zaporedja */

  a = zacetni_clen;
                     /* za vse clene do stevilo_clenov: */
  for(i = 1; i <= stevilo_clenov; i++)
  {
                     /* izpisi clen */
    printf("%d", a);
                     /* izracunaj naslednji clen */
    a = a * kolicnik;
  }
                     /* prehod v novo vrstico ob koncu
                        zaporedja */
  printf("\n");
} /* izpisi_geo_zaporedje */
\end{verbatim}
}
%
V glavni del programa pa dodamo:
%
\[
\texttt{izpisi\_geo\_zaporedje(zacetni\_clen, kolicnik, stevilo\_clenov);}
\]

\item Vsoto \v{c}lenov geometrijskega zaporedja se\v{s}tejemo
  rekurzivno.
%
  \begin{itemize}
  \item Ko je \v{s}tevilo \v{c}lenov zaporedja $0$ je vsota $0$.
  \item V primeru, ko je \v{s}tevilo \v{c}lenov zaporedja ve\v{c}je od
    $0$, je vsota enaka vsoti preostalih \v{c}lenov geometrijskega
    zaporedja, kateri pri\v{s}tejemo za\v{c}etni \v{c}len. Preostalo
    geometrijsko zaporedje pa izra\v{c}unamo tako, da poi\v{s}\v{c}emo
    novi \v{c}len, ki je enak produktu koli\v{c}nika in starega
    za\v{c}et\-nega \v{c}lena.
  \end{itemize}
%
  Celotni podprogram izgleda:
%
{\tt
\begin{verbatim}
int sestej_geo_zaporedje1(int zacetni_clen, int kolicnik,
                          int stevilo_clenov)
{
  int vsota;

  if (stevilo_clenov == 0)
    vsota = 0;
  else
  {
                     /* sestej ostale clene zaporedja */
    vsota = sestej_geo_zaporedje1(zacetni_clen * kolicnik,
                                  kolicnik,
                                  stevilo_clenov - 1);
                     /* pristej zacetni clen */
    vsota += zacetni_clen;
  }
                     /* vrni vsoto */
  return vsota;
} /* sestej_geo_zaporedje1 */
\end{verbatim}
}
\end{itemize}

\section{Dogovor med izvajalcem in uporabnikom programa}

Nek program lahko uporabljata izvajalec in uporabnik, \v{c}e poznata
glavo funkci\-je. Kot vemo, moramo vsako funkcijo najprej
\emph{definirati} in \v{s}ele nato \emph{poklicati}. Definicija
funkcije se sestoji iz dveh delov:
%
\begin{itemize}
\item glava,
\item telo (omejeno je z zavitimi oklepaji).
\end{itemize}
%
Kot primer si oglejmo definicijo za rekurzivno se\v{s}tevanje funkcije
(ogledali si bomo glavo funkcije, ki je sestavljena iz treh delov):
%
{\tt
\begin{verbatim}
  int sestej_zaporedje1(int zacetni_clen, int korak,
                        int stevilo_clenov)
\end{verbatim}
}
%
V na\v{s}em primeru je:
%
\begin{itemize}
\item tip funkcije (se\v{s}tevanje je celo\v{s}tevilsko) --
  \texttt{int};
\item ime funkcije -- \texttt{sestej\_zaporedje1};
\item parametri --
  \texttt{int zacetni\_clen, int korak, int stevilo\_clenov}.
%
  Pa\-rametri pomenijo za\v{c}etni \v{c}len, korak in koliko \v{c}lenov
  zaporedja naj se\v{s}teje.
\end{itemize}

Takrat ko nam uporabnik pove, kak\v{s}no funkcijo naj izvaja program
in kak\v{s}na naj bo glava funkcije, dobi izvajalec \emph{definicijski
  modul} (uporabnik in izvajalec ga poznata). Definicijski modul
sestavljata glava funkcije in pogodba (glej spodaj).  Izvajalec
sestavi program in \emph{objektno kodo} izro\v{c}i uporabniku.
Objektna koda je koda, ki jo dobimo po prevajanju \emph{izvorne kode}
in jo lahko uporabnik neposredno uporabi -- uporabnika ne zanima
izvorna koda (npr.\ program v jeziku c).

\subsection{Pogodba pri definicijskem modulu}

Obi\v{c}ajno pogodba ni enoli\v{c}na -- z drugimi besedami, sestavimo
lahko ve\v{c} razli\v{c}nih pogodb z istim pomenom.

Pogodba se sestoji iz petih \v{c}lenov:
%
\begin{enumerate}
\item \texttt{DESC} -- kratek opis delovanja programa
  (\textit{description});
\item \texttt{PARMS} -- pove nam parametre funkcije
  (\textit{parameters});
\item \texttt{RESULT} -- rezultat programa (\textit{result});
\item \texttt{PRE} -- predpogoj, ki pove, kako naj uporabnik dela (kaj
  mora zagotoviti pred klicem podprograma), da bo podprogram pravilno
  deloval (\textit{precondition});
\item \texttt{POST} -- popogoj, ki pove, kak\v{s}en pogoj je
  izpolnjen, ko se funkcija vrne nazaj (\textit{postcondition}).
\end{enumerate}
%
Prva \v{c}lena sta opisna in sta namenjena predvsem razumevanju
funkcije. Zadnji trije \v{c}leni bolj natan\v{c}no dolo\v{c}ajo
funkcijo. Mi jih bomo zapisali v tako imenovani \emph{pol-formalni}
obliki -- zapis ni povsem formalen, ki bi sicer omogo\v{c}al samodejno
preverjanje pravilnosti delovanja programa.

\subsection{Primer}

V primeru \texttt{zaporedj.c} imamo za funkcijo
\texttt{sestej\_zaporedje1} naslednjo po\-god\-bo:
%
{\tt
\begin{verbatim}
/* Desc:    Funkcija sesteje stevilo_clenov aritmeticnega
            zaporedja, ki je definiran z zacetnim clenom
            zacetni_clen in korakom korak.
   Parms:   zacetni_clen - zacetni clen zaporedja (po vrednosti)
            korak - razlika med zaporednima clenoma zaporedja (po
            vrednosti)
            stevilo_clenov - stevilo clenov zaporedja, ki jih
            bomo sesteli (po vrednosti)
   Result:  Sum(ai: ai = zacetni_clen + (i * korak),
                0 <= i < stevilo_clenov)
   Pre:     (RESULT IN int) AND (stevilo_clenov >= 0)
   Post:    -
*/
\end{verbatim}
}
%
Na na\v{s}em podro\v{c}ju si lahko ogledate drugo ina\v{c}ico pogodbe,
pri kateri sta spremenjna \v{clena} ,,Result'' in ,,Post``.

\end{document}
