PauloMotta.pro

Bom esse assunto é recorrente na programação e muitas vezes é utilizado como exercício em cursos de programação ou de estrutura de dados. Muitas vezes também é necesário nos cursos de computação gráfica (programada, não curso de usar photoshop ok?)

O truque é puramente matemático e precisamos entender uma propriedade dos números inteiros (tenhamos em mente que os índices de arrays são normalmente números inteiros…) relacionada ao resto da divisão. Quando dividimos um número inteiro por outro, pode acontecer de sobrar um resto, de forma que o resultado mais esse resto é igual ao número dividido, assim temos:

a/ b = q + r

onde “q” é o resultado de a/b e “r” o resto da divisão.

e para achar o número dividio original basta operar: b * q + r

por exemplo: 4/3 = 1 com resto 1 e (1 * 3 ) + 1 = 4

Quem estiver muito interessado nisso pode procurar mais material referente as Classes de Números Inteiros (na matemática, não é nenhuma classe Java não!)

Bom, mas porque essa matemática toda? Porque essa propriedade é fundamental para convertermos um número em dois! Isso mesmo, como o array é indexado por um único número temos que conseguir uma relação que nos permita transformar esse número em um par de números para indexar uma matriz (que na verdade não existe, está sendo representada no array.)

Vamos pensar em uma matriz 3×3 seu array correspondente deve ter tamanho 9 (= 3 * 3) para conseguir comportar todos os elementos da matriz. Dessa maneira nossos índices (considerando as linguagens C, Java, C++, C# e outras que começam a contar em 0) são: 0, 1, 2, 3, 4, 5, 6, 7, 8, porém os índices da matriz são (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2). Pelo menos temos a mesma quantidade de índices e pares de índices, já é uma dica do que esta acontecendo aqui

Vamos começar a analisar primeiro do ponto de vista de entrada, o usuário quer acessar um elemento em sua “matriz” e para isso vai informar dois valores digamos “i” e “j” que serão (1,1) respectivamente. Basta aqui multiplicar “i” pela ordem da matriz (3 nesse caso) e somar o valor de “j” e assim (1 * 3) + 1 = 4. Nossa primeira fórmula:

(i,j) = (i * N) + j (onde N é a ordem da matriz)

Essa foi fácil! Mas ainda não falamos sobre o porque de ter entrado aquela explicação toda sobre resto de divisão… Isso é porque para fazer a operação inversa teremos que converter um único número em dois!

Imaginemos então que o próximo passo seja imprimir a matriz na tela ou em um arquivo em disco, então vamos percorrer nosso array com um único for já que só temos uma dimensão, no entanto para imprimir precisaremos colocar os valores que o usuário conhece que são os pares (i,j), mas como?

Bom, lembrando das propriedades que falamos temos o seguinte, consideremos a posição 4 que já sabemos que equivale ao par (1,1), se dividirmos 4 pela ordem da matriz, 3 neste caso, teremos 1, agora isso é o “i” ou o ” j” ? Vamos explorar outros casos, se pegarmos o 5 por exemplo e dividirmos por 3 também teremos 1 como resultado, se o 4 e o 5 estão na mesma linha então a divisão inteira de números nos dá o componente “i”! Como vamos conseguir então com uma mesma operação e 3 valores distintos conseguir resultados que acessem as colunas? Sim, porque o valor de “j” deve ser crescente para os índices 3, 4 e 5 do array, porém é sempre o mesmo em cada uma das linhas. A resposta está na operação de módulo ou resto da divisão.  Vamos considerar esses valores abaixo:

3 % 3 = 0

4 % 3 = 1

5 % 3 = 2

Então esta é nossa segunda fórmula mágica, o resto da divisão do array pela ordem da matriz nos da o componente “j” do par.

Resumindo temos o seguinte:

dados (i,j) devemos guardar o valor na posição array[(i*N)+j]

dado o valor (idx) o seu valor corresponde ao elemento (i,j) tal que i = idx / N e j = idx % N

Como exemplo de correspondências temos:

array[0] = matriz[0][0]
array[1] = matriz[0][1]
array[2] = matriz[0][2]
array[3] = matriz[1][0]
array[4] = matriz[1][1]
array[5] = matriz[1][2]
array[6] = matriz[2][0]
array[7] = matriz[2][1]
array[8] = matriz[2][2]

A mágica das Classes de Números Inteiros está (muito resumidamente) no fato de que os números apresentam certas propriedades que os relacionam, assim podemos pensar em formato de tabela da seguinte forma (agora para um exemplo maior):

0     1   2   3    4

5     6   7   8    9

10 11 12 13 14

15 16 17 18 19

20 21 22 23 24

Com essa tabela podemos ver que se uma matriz tem ordem 5×5 então ela tem 25 elementos, além disso, podemos perceber que todos os múltiplos de 5 estão na coluna 0, todos os que tem resto de divisão 1 estão na coluna 1, e assim sucessivamente até a coluna 4 onde o próximo número será múltiplo de 5 e por isso voltará para a coluna 0 (mas com o índice de linha incrementado.)

A seguir um código Java para ilustrar o uso dessas fórmulas:

public class ArrayMatriz {
    public static void main(String[] args) {
        int N = 3;
        float matriz[][] = new float[N][N];
        float array[] = new float[(N*N)];

        for (int i = 0; i < array.length; i++) {
            array[i] = i;
            System.out.println("array["+i+"]="+array[i]);
        }
        for (int i = 0; i < matriz.length; i++) {
            for (int j = 0; j < matriz[i].length; j++) {
                matriz[i][j] = (i * N) + j;
                System.out.print("matriz["+i+"]["+j+"]="+
                         (matriz[i][j])+"   ");
            }
            System.out.println("");
        }

        for (int i = 0; i < array.length; i++) {
            array[i] = i;
            int mi = i / N;
            int mj = i % N;
            System.out.println("array["+i+"]="+array[i]+
                     " matriz["+mi+"]["+mj+"]="+matriz[mi][mj]);
        }
        for (int i = 0; i < matriz.length; i++) {
            for (int j = 0; j < matriz[i].length; j++) {
                matriz[i][j] = (i * N) + j;
                System.out.print("matriz["+i+"]["+j+"]="+(matriz[i][j])+
                    " / array["+((i * N) + j)+"]="+array[(i * N) + j]+"   ");
            }
            System.out.println("");
        }
    }
}