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

%\begin{document}

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

\chapter{Laços Encaixados e Matrizes}

\begin{center}
\shabox{
  \begin{Bitemize}
    \item[]\textbf{Quais novidades veremos nesta aula?}
    \item repetições encaixadas
    \item matrizes (arrays multi-dimensionais)
  \end{Bitemize}
} % \shabox
\end{center}
\bigskip

\section{Laços encaixados}

Em algumas situações, pode ser necessário implementar um laço dentro de
outro laço. Chamamos esta construção de laços encaixados,  laços
aninhados ou repetições encaixadas. Eis um exemplo bem simples:

\begin{lstlisting}
int i, j;
for (i = 0; i < 5; i++)
    for (j = 0; j < 3; j++)
        System.out.println ("i = " + i + ", j = " + j);
\end{lstlisting}

A idéia é que para cada iteração do for mais externo, o interpretador
Java executa o for mais interno com todas as suas interações. No exemplo
acima, o \texttt{println} é portanto executado 5*3 = 15 vezes.

Agora um exemplo mais complexo: um programa usado para calcular a média
de várias turmas na prova \texttt{P1} de uma disciplina:

\begin{lstlisting}
class MediasNaP1
{
  public static void main (String[] arg)
  {
    int numeroDeAlunos, numeroDeTurmas, turma, aluno;
    double nota, soma;
    System.out.print ("Você quer calcular as médias de quantas turmas? ");
    numeroDeTurmas = SavitchIn.readLineInt ();
    for (turma = 1; turma <= numeroDeTurmas; turma++)
    {
      soma = 0;
      nota = 0;
      System.out.println ("Digite as notas na P1 da turma " + turma);
      System.out.println ("Finalize a seqüência de notas digitando -1.");
      for (numeroDeAlunos = 0; nota >= 0; numeroDeAlunos++)
      {
        nota = SavitchIn.readLineDouble ();
        if (nota >=0)
          soma += nota;
        }
      System.out.println ("A média da turma é " + soma /
                          (numeroDeAlunos-1));
    }
  }
}
\end{lstlisting}


\section{Matrizes (arrays multi-dimensionais)}

Uma matriz de 1 dimensão, também chamada de vetor, é implementada em
Java usando um array unidimensional como vimos numa aula passada.
Matrizes de 2 ou mais dimensões também podem ser representadas em Java
através de arrays multi-dimensionais. Veja um exemplo:

\begin{lstlisting}
// define uma matriz bidimensional
int[][] matriz;

// aloca espaço para uma matriz de 5 linhas e 7 colunas
matriz = new int[5][7];

matriz[0][0] = 3;
matriz[1][1] = matriz[3][4] + matriz [1][2];
\end{lstlisting}

É muito comum utilizarmos repetições encaixadas quando precisamos
percorrer os elementos de matrizes de duas dimensões ou mais:

\begin{lstlisting}
int i, j;
int [][] tabuada = new int[11][11];
for (i = 0; i <= 10; i++)
    for (j = 0; j <= 10; j++)
        tabuada[i][j] = i * j;
\end{lstlisting}
este trecho de código cria uma matriz de duas dimensões contendo a
tabuada de 0 a 10. Note que a primeira linha e a primeira coluna não
precisariam ser inicializados com uma multiplicação, nós poderíamos
atribuir o valor 0 diretamente a elas.

\medskip

\textbf{Nota interessante:} para Java, na verdade uma matriz bidimensional é um
array de arrays. Ou seja, \texttt{tabuada} é um array onde cada posição é do tipo
array de inteiros. Dito isto, pense como podemos fazer para descobrir
quantas linhas e quantas colunas possui uma matriz bidimensional. A
resposta é a seguinte:

\begin{lstlisting}
void imprimeDimensoes (int[][] matriz)
  {
    System.out.println ("A matriz possui " +
                        matriz.length      + " linhas e " +
                        matriz[0].length   + " colunas.");
  }
\end{lstlisting}

\section{Exemplo: LIFE, o jogo da vida}


O LIFE é um jogo simples de simulação de processos biológicos criado pelo
matemático John Conway. O ``ambiente'' onde se passa a simulação é uma grade
quadriculada onde são colocadas ``células'' vivas; cada quadrado da grade pode
conter ou não uma célula viva. A partir de um estado inicial (que pode ser
gerado aleatoriamente, por exemplo), o estado seguinte da grade é determinado
através de 3 regras bem simples:

 \begin{itemize}
   \item Uma célula viva com menos de 2 vizinhos morre.
   \item Uma célula viva com mais de 3 vizinhos morre.
   \item Uma célula viva aparece quando tem 3 vizinhos vivos exatamente.
 \end{itemize}

O processo de simulação é iterativo, ou seja, as regras são aplicadas ao
estado inicial que produz um segundo estado. A este segundo estado são
aplicadas as regras novamente e assim sucessivamente, criando novas ``gerações''
de células ao longo do tempo. Veja um exemplo de implementação do LIFE
abaixo. Estude atentamente cada trecho do programa e depois o execute no DrJava.

\begin{lstlisting}
class Life
{
  int MAX = 10;  // Tamanho da matriz
  int [][] matriz = new int[MAX][MAX];

  void inicializa()
  {
    int i, j;

    for(i = 1; i < MAX - 1; i++)
       for(j = 1; j < MAX - 1; j++)
           matriz[i][j] = (int) (Math.random() * 1.5);
           // o Math.random gera um número em [0,1], multiplicando
           // por 2/3 conseguiremos 2/3 das casas com zeros e 1/3 com 1s
           // o (int) transforma o double obtido em inteiro

    // Os mais observadores podem perceber que as bordas da matriz não
    // foram inicializadas. Fizemos isso para deixá-las zeradas (o Java
    // faz isto automaticamente quando da alocação da matriz (new int).
  }

  void imprimeTabuleiro()
  {
    int i, j;

    for(i = 0; i < MAX; i++)
    {
      for(j = 0; j < MAX; j++)
        if (matriz[i][j] == 1)
           System.out.print("*");
        else
           System.out.print(".");
      System.out.println();
    }
    System.out.println();
  }

  int vizinhos(int i, int j)
  {
    return matriz[i-1][j-1] + matriz[i-1][j] + matriz[i-1][j+1] +
           matriz[i][j-1] + matriz[i][j+1] +
           matriz[i+1][j-1] + matriz[i+1][j] + matriz[i+1][j+1];
  }

  int [][] iteracao()
  {
    int [][] aux = new int[MAX][MAX];
    int i, j;

    for(i = 1; i < MAX - 1; i++)
       for(j = 1; j < MAX - 1; j++)
          {
            if (matriz[i][j] == 1)  // se está viva
            {
               if ((vizinhos(i, j) < 2) || (vizinhos(i, j) > 3))
                 aux[i][j] = 0;     // morre
               else
                 aux[i][j] = 1;     // continua viva
            }
            else                    // se não está viva
             {
              if (vizinhos(i, j) == 3)
                aux[i][j] = 1;      // aparece vida
              else
                aux[i][j] = 0;      // continua como estava
            }
          }
     return aux; // devolve a matriz com a vova iteração
  }

  void simulaVida(int quant)
  {
    int i;

    // faremos a simulação de quantos ciclos
    for(i = 0; i < quant; i++)
    {
      imprimeTabuleiro();
      matriz = iteracao(); // a matris da iteração anterior é recolhida
                           // pelo coletor de lixo.
    }
  }
}
\end{lstlisting}

{\singlespacing
\begin {verbatim}
..........   ..........   ..........   ..........   ..........
...*.****.   ....*****.   ....*****.   ....*****.   ....*****.
....*...*.   ...*....*.   ....*...*.   ...*....*.   ....**..*.
....**....   ......**..   ....***.*.   .......*..   ...**.....
.**.***.*.   .****.**..   .*.**.....   ...**.....   ...***.*..
.*....*...   .*.*..*...   ......**..   ...*.***..   ..**.*.*..
..*...*...   .***.*....   .*.*.*.*..   ..*..*.*..   ..**.*.**.
..*.*.....   ...*..**..   ...*.**...   ..*..*.*..   ....**.*..
.....**.*.   .....*....   ......*...   .....**...   .....**...
..........   ..........   ..........   ..........   ..........
\end{verbatim}
}

\section{Exercícios}

\begin{enumerate}

  \item Escreva um  método para preencher uma matriz com números inteiros
        lidos do teclado. O método recebe a matriz como parâmetro.

  \item Escreva uma classe com os seguintes métodos:
    \begin{itemize}
      \item Um método que recebe 3 matrizes do tipo \texttt{double} como
            parâmetro, calcula a soma das duas primeiras e guarda o resultado
            na terceira.
      \item Um método que recebe 3 matrizes do tipo \texttt{double} como
            parâmetro, calcula o produto das duas primeiras e guarda o
            resultado na terceira.
      \item Para os dois métodos anteriores, escrever uma segunda versão
            que recebe apenas 2 matrizes como parâmetro
            e devolve o resultado através do comando \texttt{return}.
    \end{itemize}

  \item Adicionar à classe do exercício anterior um método que recebe duas
      matrizes quadradas o tipo \texttt{double} e devolve um \texttt{boolean}
      indicando se uma é inversa da
      outra. Lembrando da imprecisão das contas com ponto flutuante considere
      que um número é igual a zero se ele pertencer a [$-10^{-8}$, $10^{8}$].
      De forma análoga considere que um número é igual a 1 se ele
      pertencer a [$1 - 10^{-8}$, $1 + 10^{8}$].

  \item Dizemos que uma matriz $A_{n x n}$ é um \emph{quadrado latino} de ordem
        \texttt{n} se em cada linha e em cada coluna aparecem todos os inteiros
        1,2,3,...,n (ou seja, cada linha e coluna é permutação dos
        inteiros 1,2,...,n). Escreva uma classe com os seguintes métodos:

  \begin{enumerate}
    \item \texttt{imprimeMatriz()}, que imprime uma matriz;
    \item \texttt{estáNoArray()} que recebe como parâmetros um inteiro
          \texttt{j} e um array \texttt{a} de inteiros e verifica se
          \texttt{j} ocorre no array;
    \item \texttt{temTodos} que, usando o método acima, que recebe como
          parâmetros um array \texttt{a} com \texttt{n} inteiros e verifica
          se em \texttt{a} ocorrem todos os inteiros de 1 a \texttt{n} e
    \item \texttt{éLatino()} que, utilizando o método acima, verifica
          se uma dada matriz inteira $A_{n x n}$ é um quadrado latino de
          ordem \texttt{n}.
  \end{enumerate}


Veja um exemplo de uso de um objeto da classe nas seguintes
iterações. Aproveitamos o exemplo abaixo para mostrar como podemos definir
matrizes constantes (usando chaves).

\begin{verbatim}
Welcome to DrJava.
> QuadradoLatino a = new QuadradoLatino();
> int [][] matriz1 = {{1}};
> a.imprimeMatriz(matriz1)
1
> a.éLatino(matriz1)
true
> int [][] matriz2 = {{1,2,3}, {2,3,1}, {3,1,2}};
> a.imprimeMatriz(matriz2)
1 2 3
2 3 1
3 1 2
> a.éLatino(matriz2)
true
> int [][] matriz3 = {{1,2}, {1,2}};
> a.imprimeMatriz(matriz3)
1 2
1 2
> a.éLatino(matriz3)
false
\end{verbatim}


\item  Dizemos que uma matriz $A_{n x n}$ é um \emph{quadrado
    mágico} de ordem \texttt{n} se o valor da soma dos elementos em cada linha
  e em cada coluna é o mesmo. Escreva uma classe que inclua métodos para
  verificar se uma dada matriz (recebida como parâmetro em um de seus métodos)
  é um quadrado mágico ou não.

\item Faça uma classe com dois métodos estáticos:
  \begin{itemize}
  \item \texttt{int pertence(int el, int v[], int tam)} que verifica se um
    inteiro \texttt{el} ocorre em um \emph{array} \texttt{v[]} com
    \texttt{tam} elementos. Se ele ocorre, o método devolve a posição da
    primeira ocorrência, caso contrário devolve -1.

    \item \texttt{void frequencia(int v[])} que imprime a freqüência absoluta
      dos elementos em v.
      
      Dica: para calcular a freqüência absoluta são necessários dois vetores,
      um com os elementos distintos e outro com o número de ocorrências.
      Percorra o \emph{array} \texttt{v} verificando, para cada posição, se o
      número armazenado já apareceu.
  \end{itemize}

\item Um jogo de palavras cruzadas pode ser representado por uma matriz
      $A_{m x n}$ onde cada posição da matriz corresponde a um quadrado do
      jogo, sendo que 0 indica um quadrado branco e -1 indica um
      quadrado preto. Indicar na matriz as posições que são início de
      palavras horizontais e/ou verticais nos quadrados correspondentes
      (substituindo os zeros), considerando que uma palavra deve ter
      pelo menos duas letras. Para isso, numere consecutivamente tais
      posições.\\
      Exemplo: Dada a matriz:

      \begin{tabular}{|c|c|c|c|c|c|c|c|}
      \hline
       0 & -1  &  0 & -1 & -1 &  0 & -1 &  0
      \tabularnewline \hline
       0 &  0  &  0 &  0 & -1 &  0 &  0 &  0
      \tabularnewline \hline
       0 &  0  & -1 & -1 &  0 &  0 & -1 &  0
      \tabularnewline \hline
      -1 &  0  &  0 &  0 &  0 & -1 &  0 &  0
      \tabularnewline \hline
       0 &  0  & -1 &  0 &  0 &  0 & -1 & -1
      \tabularnewline \hline
      \end{tabular}

      A saída deverá ser:

      \begin{tabular}{|c|c|c|c|c|c|c|c|}
      \hline
       1 &      -1 &     2 &    -1 &    -1 &     3 &    -1 &     4
      \tabularnewline \hline
       5 &       6 &     0 &     0 &    -1 &     7 &     0 &     0
      \tabularnewline \hline
       8 &       0 &    -1 &    -1 &     9 &     0 &    -1 &     0
      \tabularnewline \hline
      -1 &      10 &     0 &    11 &     0 &    -1 &    12 &     0
      \tabularnewline \hline
      13 &       0 &    -1 &    14 &     0 &     0 &    -1 &    -1
      \tabularnewline \hline
      \end{tabular}

\item (Difícil) Escreva uma classe com um método que leia um inteiro \texttt{n} e as
      posições de \texttt{n} rainhas em um tabuleiro de xadrez e determina se
      duas rainhas se atacam.

\end{enumerate}

%\end{document}
