\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 2\hfill\sl23/6/99}
\bigskip

\medskip
\noindent{\bf 1.} [2 pontos]\enspace
\item{({\it i\/})}
Escreva uma função de protótipo
\begintt
int leia_v(int a[]);
\endtt
que serve para ler uma seqüência de inteiros positivos (cujo término é
indicado por $0$).  A sua função deve devolver o número de elementos na
seqüência e os elementos lidos devem ser armazenados no vetor que é dado como
argumento.  Você pode assumir que o usuário não vai fornecer uma seqüência
mais longa que o vetor pode armazenar. 

\item{({\it ii\/})}
Escreva uma função de protótipo
\begintt
void imprima_v(int a[], int n);
\endtt
que imprime os primeiros {\tt n} elementos do vetor {\tt a[]}.  

\medskip
\noindent{\bf 2.} [2 pontos]\enspace
Escreva uma função de protótipo 
\begintt
int conte_ocorrencias(string p, string t);
\endtt
que recebe como entrada os strings {\tt p} e {\tt t} e devolve o número de
ocorrências de {\tt p} em {\tt t}.  Nesta questão, você pode usar as funções
da interface {\tt strlib.h} de Roberts ou da interface {\tt string.h} do ANSI
C.  Você pode achar útil o seguinte trecho de {\tt strlib.h}:
\begintt
/* Function: FindString
 * Usage: p = FindString(str, text, start);
 * ----------------------------------------
 * Beginning at position start in the string text, this function searches for
 * the string str and returns the first index at which it appears or -1 if no
 * match is found.
 */
int FindString(string str, string text, int start);
\endtt

\medskip
\noindent{\bf 3.} [3 pontos]\enspace
Considere o seguinte programa: 
\begintt
#include <stdio.h>
#include "genlib.h"
#include "simpio.h"
#include "graphics.h"

void mark(double x, double h)
{ MovePen(1.0 + x, 1.0); DrawLine(0.0, h); }

void rule(double l, double r, int h)
{ double m = (l+r)/2;
  if (h > 0) { rule(l, m, h-1); mark(m, h); rule(m, r, h-1); }
}

main()
{ InitGraphics(); MovePen(1.0, 1.0); DrawLine(5.0, 0.0); 
  rule(0, 5, 3);
}  
\endtt
Descreva a saída deste programa.  Como se alteraria sua resposta se ao invés
de {\tt rule(0, 5, 3)} tivéssemos {\tt rule(0, 5, 5)}?

\medskip
\noindent{\bf 4.} [3 pontos]\enspace
Existe uma fórmula de recorrência simples para determinar os numeradores e
denominadores da seqüência de Farey (veja, por exemplo, Knuth, vol.~1,
Seção~1.3.2, exercício~18, 3a.~edição).  Para a seqüência de Farey de
ordem~$n$ (isto é, com denominadores~$\leq n$), se os termos desta seqüência
são~$x_0/y_0$, $x_1/y_1$, $x_2/y_2,\dots$, temos
$$
x_0=0,\qquad y_0=1; \qquad\qquad x_1=1,\qquad y_1=n;
$$
e, para $k\geq0$,
$$
x_{k+2}=\lfloor(y_k+n)/y_{k+1}\rfloor x_{k+1}-x_k,
$$
$$
y_{k+2}=\lfloor(y_k+n)/y_{k+1}\rfloor y_{k+1}-y_k.
$$
Acima, $\lfloor x\rfloor$ indica o maior inteiro não maior que~$x$.  Em {\tt
C}, existe uma função exportada em {\tt <math.h>} chamada {\tt floor()} que
devolve $\lfloor{\tt x}\rfloor$ quando chamada com argumento {\tt x}.
Escreva uma função de protótipo
\begintt
void Farey(int n, int k, int *pnum, int *pden);
\endtt
que recebe como entrada a ordem~$n$ da seqüência de Farey em que estamos
interessados e põe em {\tt *pnum} e {\tt *pden} o numerador e denominador do
{\tt k}-ésimo elemento desta seqüência de Farey.  Por exemplo, para {\tt n =
7}, e {\tt k = 5}, a função deve determinar a fração~{\tt 2/7}.

\bye
