\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 3\hfill\sl29/6/99}
\bigskip

\medskip
\noindent{\bf 1.} [2 pontos]\enspace
Escreva uma função de protótipo
\begintt
int quadrado(string s);
\endtt
que recebe um string {\tt s} como argumento e devolve {\tt 1} caso
{\tt s} seja um quadrado e {\tt 0} caso contrário.  Aqui, dizemos que
um string é um quadrado se ele for a concatenação de dois strings
iguais.  Por exemplo, {\tt abab} é um quadrado, já que ele é a
concatenação do string {\tt ab} com ele mesmo (podemos escrever ${\tt
abab}={\tt(ab)}^2$).  O string vazio (de comprimento~$0$) é a
concatenação dele com ele mesmo, de forma que ele é também um
quadrado.  

Para esta questão, você deve usar (entre outras) a seguinte função
de {\tt strlib}.
\begintt
/*
 * Function: SubString
 * Usage: t = SubString(s, p1, p2);
 * --------------------------------
 * SubString returns a copy of the substring of s consisting of the
 * characters between index positions p1 and p2, inclusive.  The
 * following special cases apply: 
 *
 * 1. If p1 is less than 0, it is assumed to be 0.
 * 2. If p2 is greater than the index of the last string position,
 *    which is StringLength(s) - 1, then p2 is set equal to
 *    StringLength(s) - 1. 
 * 3. If p2 < p1, SubString returns the empty string.
 */

string SubString(string s, int p1, int p2);
\endtt


\medskip
\noindent{\bf 2.} [2 pontos]\enspace
Considere a seguinte função
\begintt
double p(double x, double a[], int n)
{
  double temp = 0; int k;
  for (k = n; k >= 0; k--) temp = temp * x + a[k];
  return temp;
}
\endtt

\item{({\it i\/})} Suponha que temos um vetor {\tt c[]} com {\tt c[0] = -2},
{\tt c[1] = -1} e {\tt c[2] = 1}.  Qual é o valor devolvido pelas chamadas
{\tt p(2, c, 2)}, {\tt p(-1, c, 2)} e {\tt p(1, c, 2)}?

\item{({\it ii\/})} Suponha que os elementos de um vetor {\tt c[]} são tais que 
{\tt c[i] = i + 1} para todo~$0\leq{\tt i}\leq{\tt n}$.  Encontre uma
fórmula para o valor devolvido pela chamada {\tt p(x, c, n)}.  [Ignore erros
de arredondamento.]

\medskip
\noindent{\bf 3.} [3 pontos]\enspace
Por simplicidade, nesta questão você deve assumir que {\tt m} e {\tt
n} são sempre inteiros não-negativos primos entre si.  Procure
justificar suas respostas desta questão com especial cuidado.
\item{({\it i\/})} Escreva uma função de protótipo
\begintt
void f(int x, int *a, int *b, int m, int n);
\endtt
que recebe um inteiro {\tt x} e que põe em {\tt *a} o valor ${\tt
x\bmod m}$ e põe em {\tt *b} o valor ${\tt x\bmod n}$.  

\item{({\it ii\/})} Suponha agora que você tem à disposição uma função
de protótipo 
\begintt
void euclides(int m, int n, int *r, int *s);
\endtt
que recebe os inteiros~{\tt m} e {\tt n} e põe em {\tt *r} e {\tt *s},
respectivamente, inteiros $\alpha$ e $\beta$ tais que $\alpha{\tt
m}+\beta{\tt n}=1$.  Escreva uma função de protótipo
\begintt
void g(int m, int n, int *b1, int *b2);
\endtt
que recebe os inteiros~{\tt m} e {\tt n} e põe em {\tt *b1} e {\tt
*b2}, respectivamente, inteiros $e_1$ e $e_2$ tais que
$$e_1\equiv1\pmod{\hbox{\tt m}},
  \qquad e_1\equiv0\pmod{\hbox{\tt n}}, 
\qquad 
  e_2\equiv0\pmod{\hbox{\tt m}},
  \qquad e_2\equiv1\pmod{\hbox{\tt n}}.$$ 
[{\it Sugestão}.  Considere os números $\alpha{\tt m}$ e $\beta{\tt
n}$.] 
\item{({\it iii\/})} Escreva uma função de protótipo
\begintt
int h(int a, int b, int m, int n);
\endtt
que recebe inteiros {\tt a}, {\tt b}, {\tt m} e {\tt n} e devolve um
inteiro {\it x\/} tal que
$$
\cases{
  x\equiv a\pmod{\hbox{\tt m}}\cr
  x\equiv b\pmod{\hbox{\tt n}}.\cr
}
$$
[{\it Sugestão}.  Considere $ae_1+be_2$.]

\medskip
\noindent{\bf 4.} [3 pontos]\enspace
\item{({\it i\/})} Escreva uma função de protótipo
\begintt
void elimine(int a[], int i, int n);
\endtt
que elimina do vetor fornecido {\tt a[]} o item {\tt a[i]}.  Os elementos {\tt
a[i+1],...,a[n-1]} devem ser `deslocados' uma posição para a esquerda, de
forma a `fechar' o `espaço' deixado pela eliminação de {\tt a[i]}.  Você pode
assumir que $0\leq{\tt i}\leq{\tt n}-1$.

\item{({\it ii\/})} Escreva uma função de protótipo
\begintt
int reduza(int a[], int i, int n);
\endtt
que recebe um vetor {\tt a[]} com {\tt n} entradas e faz o seguinte: {\tt
reduza()} verifica se o valor {\tt a[i]} ocorre como {\tt a[j]} para algum
{\tt j > i}.  Se isto não ocorrer, {\tt reduza()} deixa o vetor {\tt
a[]} intacto e devolve o valor {\tt n}.  Caso contrário, {\tt reduza()} deve
eliminar de {\tt a[]} todas as ocorrências do valor {\tt a[i]}, a menos
daquela ocorrência como {\tt a[i]} (isto é, todos os {\tt a[j]} com {\tt a[j]
= a[i]} e {\tt j > i} devem ser eliminados).  A função {\tt reduza()} deve
devolver o número de elementos restantes no vetor, após a eliminação de todas
as duplicações do valor {\tt a[i]} como descrito acima.  Você deve usar a
função de~({\it i\/}), mesmo que você não a tenha escrito.

\item{({\it iii\/})} Escreva uma função de protótipo
\begintt
int elimine_duplicacoes(int a[], int n);
\endtt
que elimina do vetor fornecido {\tt a[]} todos os valores duplicados, deixando
nele uma ocorrência de cada valor distinto que nele ocorre.  O usuário desta
função passa em {\tt n} o número de elementos do vetor {\tt a[]}; por sua vez,
a função {\tt elimine\_duplicacoes()} deve devolver o número de elementos
restantes no vetor {\tt a[]} após todas as eliminações de duplicações. Você
deve usar a função de~({\it ii\/}), mesmo que você não a tenha escrito.

\bye
