\input acentos
\hyphenpenalty=500
\nopagenumbers
\tolerance=500
\overfullrule=0pt
\catcode`@=11 % borrow the private macros of PLAIN (with care)
% (now Appendix E resumes again)
% macros for verbatim scanning
\chardef\other=12
\def\ttverbatim{\begingroup
  \catcode`\\=\other
  \catcode`\{=\other
  \catcode`\}=\other
  \catcode`\$=\other
  \catcode`\&=\other
  \catcode`\#=\other
  \catcode`\%=\other
  \catcode`\~=\other
  \catcode`\_=\other
  \catcode`\^=\other
  \obeyspaces \obeylines \tt}

\outer\def\begintt{$$\let\par=\endgraf \ttverbatim \parskip=\z@
  \catcode`\|=0 \rightskip-5pc \ttfinish}
{\catcode`\|=0 |catcode`|\=\other % | is temporary escape character
  |obeylines % end of line is active
  |obeyspaces|global|let =| % spaces are active
  |gdef|ttfinish#1^^M#2\endtt{#1|vbox{#2}|endgroup$$}}

\centerline{MAC110\hfill\bf PROVA 1\hfill\sl29/4/99}
\bigskip

\medskip
\noindent{\bf 1.} [2 pontos]\enspace
Escreva um programa que recebe como entrada um inteiro {\tt n} (${\tt
n}\geq2$) e {\tt n} inteiros $x_1,\ldots,x_n$ e que decide se estes {\tt n}
inteiros formam uma seqüência crescente, decrescente, ou não-monotônica (isto
é, nem crescente nem decrescente).  Nesta questão, o termo {\it
crescente\/} significa
$$
x_1\leq\cdots\leq x_n, 
$$
e o termo {\it decrescente\/} significa
$$
x_1\geq\cdots\geq x_n. 
$$

\medskip
\noindent{\bf 2.} [2 pontos]\enspace
Escreva um programa que recebe como entrada um inteiro {\tt n} (${\tt
n}\geq1$) e {\tt n} inteiros não-negativos $x_1,\ldots,x_n$ e que determina o
máximo divisor comum destes {\tt n} inteiros.

\medskip
\noindent{\bf 3.} [2 pontos]\enspace
Escreva uma função de protótipo
\begintt
  double cos_aprox(double x, int n);
\endtt
que calcula uma aproximação para $\cos x$ usando a fórmula
$$
\sum_{0\leq k\leq n}(-1)^k{x^{2k}\over(2k)!}.
$$
Você pode assumir que a função é sempre chamada para valores não-negativos de
{\tt n}. 

\medskip
\noindent{\bf 4.} [2 pontos]\enspace
Escreva um programa que recebe como entrada inteiros não-negativos {\tt k} e
{\tt m}, com ${\tt k}\leq{\tt m}$, e que imprime os valores de
$$
{n\choose k}
$$
para todos os valores de $n$ com ${\tt k}\leq n\leq{\tt m}$.

\medskip
\noindent{\bf 5.} [2 pontos]\enspace
Considere o seguinte algoritmo, visto em sala, associado ao teorema de
Bezout (assuma que $m$ e $n$ são inteiros não-negativos dados). 
\medskip
{\parindent=1.7truecm
\item{\it Passo 1.} Ponha $a'\leftarrow b\leftarrow1$, $a\leftarrow b'\leftarrow0$,
          $c\leftarrow m$, $d\leftarrow n$.
\item{\it Passo 2.} Sejam $q$ e $r$ o quociente e resto da divisão de $c$ por $d$:
          $c=qd+r$ com $0\leq r<d$.
\item{\it Passo 3.} Se $r=0$, termine o algoritmo e imprima $a$, $b$ e $d$.
\item{\it Passo 4.} Ponha $c\leftarrow d$, $d\leftarrow r$, $t\leftarrow a'$,
          $a'\leftarrow a$, $a\leftarrow t-qa$, $t\leftarrow b'$,
          $b'\leftarrow b$, $b\leftarrow t-qb$, e vá para o Passo 2.
}
\medskip
\item{({\it i\/})} Implemente o algoritmo acima em {\tt C}.

\item{({\it ii\/})} Suponha que antes de realizarmos o Passo 4, temos
$am+bn=d$, $a'm+b'n=c=qd+r$ ($0<r<d$), e $\hbox{mdc}(c,d)=\hbox{mdc}(m,n)$.
Prove que após executarmos o Passo 4, temos $am+bn=d$, $a'm+b'n=c$, $d>0$, 
e $\hbox{mdc}(c,d)=\hbox{mdc}(m,n)$.  

\item{({\it iii\/})} Deduza que os valores impressos por este algoritmo
satisfazem $am+bn=d$, onde $d=\hbox{mdc}(m,n)$.

\bye
