%cabeçalho para todos os capítulos
%\input{cabecalho}

%\begin{document}

%Opções para o pacote listings
%\input{listingOptions}

\chapter{Laços e Repetições}

\begin{center}
\shabox{
  \begin{Bitemize}
    \item[]\textbf{Quais novidades veremos nesta aula?}
    \item A idéia de laços em linguagens de programação
    \item O laço \texttt{while}
    \item O operador que calcula o resto da divisão inteira: \texttt{\%}
    \end{Bitemize}
} % \shabox
\end{center}
\bigskip

\section{Laços em linguagens de programação}

Vamos apresentar para vocês um novo conceito fundamental de programação:
o \emph{laço}. Mas o que pode ser isso? Um nome meio estranho, não? Nada melhor
do que um exemplo para explicar.

Vamos voltar ao nosso velho conversor de temperatura. Imagine que você
ganhou uma passagem para Nova Iorque e que os EUA não estão em guerra com
ninguém. Você arruma a mala e se prepara para viagem. Antes de viajar
você resolve conversar com um amigo que já morou nos EUA. Ele acaba lhe
dando uma dica: guarde uma tabelinha de conversão de temperaturas de
Fahrenheit para Celsius. Ela será muito útil, por exemplo, para entender
o noticiário e saber o que vestir no dia seguinte. Você então se lembra
das aulas de MAC-110: você já tem um conversor pronto. Basta então
usá-lo para montar a tabela. Você chama então o DrJava e começa uma nova
seção iterativa.

\begin{verbatim}
Welcome to DrJava.
> Conversor4 c = new Conversor4()
> c.fahrenheitParaCelsius(0)
-17.77777777777778
> c.fahrenheitParaCelsius(10)
-12.222222222222221
> c.fahrenheitParaCelsius(20)
-6.666666666666667
> c.fahrenheitParaCelsius(30)
-1.1111111111111112
> c.fahrenheitParaCelsius(40)
4.444444444444445
> c.fahrenheitParaCelsius(50)
10.0
> c.fahrenheitParaCelsius(60)
15.555555555555555
> c.fahrenheitParaCelsius(70)
21.11111111111111
> c.fahrenheitParaCelsius(80)
26.666666666666668
> c.fahrenheitParaCelsius(90)
32.22222222222222
> c.fahrenheitParaCelsius(100)
37.77777777777778
> c.fahrenheitParaCelsius(110)
43.333333333333336
>
\end{verbatim}

Pronto, agora é só copiar as linhas acima para um editor de textos,
retirar as chamadas ao método \\ \texttt{fahrenheitParaCelsius}
(pois elas confundem) e imprimir a tabela.

Será que existe algo de especial nas diversas chamadas do método
\texttt{fahrenheitParaCelsius} acima? Todas elas são muito parecidas e é fácil
adivinhar a próxima se sabemos qual a passada. Ou seja, a lei de formação
das diversas chamadas do método é simples e bem conhecida. Não seria
interessante se fosse possível escrever um trecho de código compacto que
representasse essa idéia? Para isso servem os laços: eles permitem a
descrição de uma seqüência de operações repetitivas.

\section{O Laço \texttt{while}}

O nosso primeiro laço será o \texttt{while}, a palavra inglesa para
\emph{enquanto}.  Ele permite repetir uma seqüência de operações enquanto uma
\emph{condição} se mantiver verdadeira. Mais uma vez, um exemplo é a melhor
explicação.  Experimente digitar as seguintes linhas de código no painel de
interações do DrJava (lembre-se que para digitarmos as 5 linhas do comando
\texttt{while} abaixo, é necessário usarmos \textsf{Shift+Enter} ao invés de
apenas \textsf{Enter} no final das 4 linhas iniciais do \texttt{while}):

\begin{verbatim}
Welcome to DrJava.
> int a = 1;
> while (a <= 10)
{
  System.out.println("O valor atual de a é: " + a);
  a = a + 1;
}
\end{verbatim}
o resultado será o seguinte:
\begin{verbatim}
O valor atual de a é: 1
O valor atual de a é: 2
O valor atual de a é: 3
O valor atual de a é: 4
O valor atual de a é: 5
O valor atual de a é: 6
O valor atual de a é: 7
O valor atual de a é: 8
O valor atual de a é: 9
O valor atual de a é: 10
>
\end{verbatim}

Vamos olhar com calma o código acima. Primeiro criamos uma variável inteira
chamada \texttt{a}. O seu valor inicial foi definido como 1. A seguir vem a
novidade: o laço \texttt{while}. Como dissemos antes, ele faz com que o código
que o segue (e está agrupado usando chaves) seja executado enquanto a condição
\texttt{a <= 10} for verdadeira. Inicialmente \texttt{a} vale 1, por isto este
é o primeiro valor impresso. Logo depois de imprimir o valor de \texttt{a}, o
seu valor é acrescido de 1, passando a valer 2. Neste momento o grupo de
instruções que segue o \texttt{while} terminou. O que o computador faz é
voltar à linha do \texttt{while} e testar a condição novamente. Como
\texttt{a} agora vale 2, ele ainda é menor que 10.  Logo as instruções são
executadas novamente. Elas serão executadas \emph{enquanto} a condição for
verdadeira, lembra?  Mais uma vez, o valor atual de \texttt{a} é impresso e
incrementado de 1, passando a valer 3. De novo o computador volta à linha do
\texttt{while}, testa a condição (que ainda é verdadeira) e executa as
instruções dentro das chaves.  Esse processo continua até que o \texttt{a}
passe a valer 11, depois do décimo incremento.  Neste instante, a condição
torna-se falsa e na próxima vez que a condição do \texttt{while} é testada, o
computador pula as instruções dentro das chaves do \texttt{while}. Ufa, é
isso!  Ainda bem que é o computador que tem todo o trabalho! Uma das
principais qualidades do computador é a sua capacidade de efetuar repetições.
Ele faz isso de forma automatizada e sem se cansar. O laço é uma das formas
mais naturais de aproveitarmos essa característica da máquina.

Agora vamos ver como esse novo conhecimento pode nos ajudar a montar a nossa
tabela de conversão de forma mais simples e flexível. Se pensarmos bem,
veremos que as operações realizadas para calcular as temperaturas para tabela
são semelhantes ao laço apresentado. Só que no lugar de simplesmente imprimir
os diferentes valores de uma variável, para gerar a tabela chamamos o método
\texttt{fahrenheitParaCelsius} várias vezes. Vamos agora adicionar um método novo à
classe \texttt{Conversor4}, que terá a função de imprimir tabelas de conversão
para diferentes faixas de temperatura. O código final seria:

\begin{lstlisting}
class Conversor5
{
  /**
   * Converte temperatura de Celsius para Fahrenheit.
   */
  double celsiusParaFahrenheit(double celsius)
  {
    return celsius * 9.0 / 5.0 + 32;
  }

  /**
   * Converte temperatura de Fahrenheit para Celsius.
   */
  double fahrenheitParaCelsius(double fahr)
  {
    return (fahr - 32.0) * 5.0 / 9.0;
  }

  /**
   * Imprime uma tabela de conversão Faranheit => Celsius.
   */
  void imprimeTabelaFahrenheitParaCelsius(double inicio, double fim)
  {
    double fahr = inicio;
    double celsius;

    while (fahr <= fim)
    {
      celsius = fahrenheitParaCelsius(fahr);
      System.out.println(fahr + "F = " + celsius + "C");
      fahr = fahr + 10.0;
    }
  }
}
\end{lstlisting}

Muito melhor, não?

\section{Números primos}

Vejamos agora um novo exemplo. Todos devem se lembrar o que é um número
primo: um número natural que possui exatamente dois divisores naturais
distintos, o 1 e o próprio número. Vamos tentar escrever uma classe
capaz de reconhecer e, futuramente gerar, números primos.

Como podemos reconhecer números primos? A própria definição nos dá um
algoritmo. Dado um candidato a primo \texttt{x}, basta verificar se algum
inteiro entre 2 e \texttt{x} - 1 divide \texttt{x}. Então para verificar se um
número é primo podemos usar um laço que testa se a divisão exata ocorreu.

Porém, ainda falta um detalhe. Como podemos verificar se uma divisão entre
números inteiros é exata. Já sabemos que se dividirmos dois números inteiros
em Java a resposta é inteira. E o resto da divisão?  Felizmente, há um
operador especial que devolve o resto da divisão, é o operador \texttt{\%}.
Vejamos alguns exemplos:

\begin{verbatim}
Welcome to DrJava.
> 3 / 2
1
> 3 % 2
1
> 5 / 3
1
> 5 % 3
2
> int div = 7 / 5
> int resto = 7 % 5
> div
1
> resto
2
> div*5 + resto
7
>
\end{verbatim}
Deu para pegar a idéia, não?

\vspace{5mm}

Agora vamos escrever uma classe contendo um método que verifica
se um inteiro é primo ou não, imprimindo a resposta na tela. O nome que
daremos à nossa classe é \texttt{GeradorDePrimos}. A razão para esse nome
ficará clara na próxima aula.

\begin{lstlisting}
class GeradorDePrimos
{
  /**
   * Imprime na tela se um número inteiro positivo é primo ou não.
   */
  void verificaPrimalidade(int x)
  {
    // Todos os números inteiros positivos são divisíveis por 1.
    int numeroDeDivisores = 1;
    // O primeiro candidato a divisor não trivial é o 2.
    int candidatoADivisor = 2;

    // Testa a divisão por todos os números menores ou iguais a x.
    while (candidatoADivisor <= x)
    {
      if (x % candidatoADivisor == 0)
        numeroDeDivisores = numeroDeDivisores + 1;
      candidatoADivisor = candidatoADivisor + 1;
    }

    // Imprime a resposta.
    if (numeroDeDivisores == 2)
      System.out.println(x + " é primo.");
    else
      System.out.println(x + " não é primo.");
  }
}
\end{lstlisting}

\section{Exercícios}

\begin{enumerate}
  
\item Crie uma classe \texttt{Fatorial} com um método
  \texttt{calculaFatorial(int x)} que calcula o fatorial de \texttt{x}
  se este for um número inteiro positivo e \texttt{-1} se \texttt{x} for
  negativo.
  
\item Crie uma classe contendo um método que devolve a média dos valores $1$,
  $2$, $3$, ..., $N$, onde $N$ é o valor absoluto de um número fornecido ao
  método.
  
\item Adicione as seguintes funcionalidades à classe \texttt{Conversor5} vista
  neste capítulo:

  \begin{enumerate}
  \item Crie o método \texttt{imprimeTabelaCelsiusParaFahrenheit}, que converte no
    sentido oposto do método \texttt{imprimeTabelaFahrenheitParaCelsius}.
  \item Adicione um parâmetro aos métodos acima que permita a impressão de
    uma tabela com passos diferentes de 10.0. Ou seja, o passo entre a
    temperatura atual e a próxima será dado por esse novo parâmetro.
  \end{enumerate}
  
\item Escreva uma classe Fibonacci, com um método
  \texttt{imprimeFibonacciAte50}, que imprime os 50 primeiros números da
  seqüência de Fibonacci. Seqüência de Fibonacci:

\begin{itemize}
\item F1 = 1;
\item F2 = 1;
\item Fn = F(n-1) + F(n-2), para todo n > 2, n inteiro.
\end{itemize}

O método deve então imprimir F1, F2, F3, ..., F49, F50.

\item Abaixo, apresentamos uma pequena variação do método \texttt{verificaPrimalidade}.
  Ela não funciona corretamente em alguns casos. Você deve procurar
  um exemplo no qual esta versão não funciona e explicar o defeito
  usando suas próprias palavras. Note que a falha é sutil, o que
  serve como alerta: programar é uma tarefa difícil, na qual
  pequenos erros podem gerar resultados desastrosos. Toda atenção é
  pouca!

\begin{lstlisting}
/**
 * Imprime na tela se um número inteiro positivo é primo ou não.
 */
void verificaPrimalidade(int x)
{
  // Todos os números inteiros positivos são divisíveis por 1.
  int numeroDeDivisores = 1;
  // O primeiro candidato a divisor não trivial é o 2.
  int candidatoADivisor = 2;

  // Testa a divisão por todos os números menores ou iguais a x.
  while (candidatoADivisor <= x)
  {
    candidatoADivisor = candidatoADivisor + 1;
    if (x % candidatoADivisor == 0)
      numeroDeDivisores = numeroDeDivisores + 1;
  }

  // Imprime a resposta.
  if (numeroDeDivisores == 2)
    System.out.println(x + " é primo.");
  else
    System.out.println(x + " não é primo.");
}
\end{lstlisting}

\item O laço no nosso \texttt{verificaPrimalidade} é executado mais vezes do que o
  necessário. Na verdade poderíamos parar assim que \texttt{candidatoADivisor}
  chegar em \texttt{x/2} ou mesmo ao chegar na raiz quadrada de \texttt{x}.
  Pense como mudar o programa levando em consideração estes novos limitantes.
  
\item Escreva uma classe Euclides, com um método \texttt{mdc} que recebe dois
  números inteiros \texttt{a1} e \texttt{a2}, estritamente positivos, com
  \texttt{a1 >= a2}, e devolve o máximo divisor comum entre eles, utilizando o
  algoritmo de Euclides.
  
  Breve descrição do algoritmo de Euclides (para maiores detalhes, consulte
  seu professor de Álgebra):

{\singlespacing
\begin{itemize}
\item[-] Dados \texttt{a1} e \texttt{a2}, com \texttt{a1} >= \texttt{a2}, quero o m.d.c.(\texttt{a1}, \texttt{a2}).
\item[-] Calcule \texttt{a3} = \texttt{a1} \% \texttt{a2}.
\item[-] Se \texttt{a3} = 0, fim. A solução é \texttt{a2}.
\item[-] Calcule \texttt{a4} = \texttt{a2} \% \texttt{a3}.
\item[-] Se \texttt{a4} = 0, fim. A solução é \texttt{a3}.
\item[-] Calcule \texttt{a5} = \texttt{a3} \% \texttt{a4}.
\item[-] ...
\end{itemize}
}

Nota importante: o operador binário \% calcula o resto da divisão de n por m,
quando utilizado da seguinte maneira: n \% m. Curiosidade: ele também funciona
com números negativos! Consulte seu professor de Álgebra ;-)

\end{enumerate}

%\end{document}