Pratique algoritmo - Matrizes

O que são matrizes em algoritmos

Uma matriz é uma estrutura de dados com duas dimensões: linhas e colunas. Em outras palavras, ela funciona como uma tabela em que cada elemento ocupa uma posição definida por dois índices.

Por convenção, o primeiro índice indica a linha e o segundo indica a coluna. Então, o elemento A[2, 3] fica na linha 2 e na coluna 3 da matriz A.

Quando o número de linhas é igual ao número de colunas, a matriz é quadrada. Nesse caso, falamos apenas da sua dimensão N, e surgem conceitos como diagonal principal e diagonal secundária.

Na maior parte dos exercícios de algoritmos com matrizes, você vai usar dois laços aninhados. O laço externo percorre as linhas, enquanto o laço interno percorre as colunas de cada linha.

// Exercício 1: ler uma matriz 4 x 5 e imprimir seus elementos
var matrix = new int[4, 5];

for (var row = 0; row < matrix.GetLength(0); row++)
{
    for (var col = 0; col < matrix.GetLength(1); col++)
    {
        Console.Write($"A[{row},{col}] = ");
        matrix[row, col] = int.Parse(Console.ReadLine()!);
    }
}

for (var row = 0; row < matrix.GetLength(0); row++)
{
    for (var col = 0; col < matrix.GetLength(1); col++)
        Console.Write($"{matrix[row, col],5}");

    Console.WriteLine();
}

Como resolver algoritmos com matrizes

Antes de partir para a lista, algumas práticas tornam a resolução de algoritmos com matrizes mais tranquila. Primeiro, escreva uma função para gerar a matriz e outra para imprimir, porque quase todos os exercícios repetem essas duas tarefas.

Em seguida, valide sempre as entradas do usuário. Dimensões menores que um, por exemplo, não fazem sentido e devem gerar uma nova solicitação.

Também vale gerar os elementos aleatoriamente sempre que o enunciado permitir. Dessa forma, você testa o algoritmo várias vezes sem digitar dezenas de números.

// Funções reutilizáveis para gerar e imprimir matrizes
static int[,] Generate(int rows, int cols, int maxValue)
{
    var matrix = new int[rows, cols];

    for (var row = 0; row < rows; row++)
        for (var col = 0; col < cols; col++)
            matrix[row, col] = Random.Shared.Next(maxValue);

    return matrix;
}

static void Print(int[,] matrix)
{
    for (var row = 0; row < matrix.GetLength(0); row++)
    {
        for (var col = 0; col < matrix.GetLength(1); col++)
            Console.Write($"{matrix[row, col],5}");

        Console.WriteLine();
    }
}

Por fim, desenhe a matriz no papel quando a regra envolver regiões, como diagonais e triângulos. Na prática, marcar os índices de cada célula revela a condição correta muito mais rápido.

Exercícios básicos de algoritmos com matrizes

Os oito primeiros exercícios trabalham leitura, geração, impressão e busca. Portanto, eles formam a base para todos os outros algoritmos com matrizes da lista.

Diagonais em algoritmos com matrizes

Os algoritmos com matrizes de 9 a 20 trabalham regiões de uma matriz quadrada. Por isso, antes de resolvê-los, vale entender as condições que definem cada diagonal.

A diagonal principal reúne os elementos em que a linha é igual à coluna. Já a diagonal secundária reúne os elementos em que a soma de linha e coluna é igual à dimensão mais um, quando os índices começam em 1.

Em linguagens com índice inicial zero, como C#, a fórmula muda um pouco. Nesse caso, a diagonal secundária atende à condição i + j == n - 1.

Quando o enunciado de algoritmos com matrizes diz "inclusa", a condição usa maior ou igual, ou menor ou igual. Por outro lado, "exclusa" exige a comparação estrita.

// Exercícios 9 e 10: diagonal principal e diagonal secundária
var size = 5;
var matrix = Generate(size, size, 100);
Print(matrix);

for (var i = 0; i < size; i++)
    Console.WriteLine($"Main diagonal: {matrix[i, i]}");

for (var i = 0; i < size; i++)
    Console.WriteLine($"Secondary diagonal: {matrix[i, size - 1 - i]}");

Concatenação e intercalação de matrizes

Os dois próximos algoritmos com matrizes trabalham com mais de uma estrutura ao mesmo tempo. Além disso, eles exigem atenção redobrada com os índices de destino.

21. Escreva um programa para gerar uma matriz (N x M) e outra (N x P), e então gere uma terceira matriz (N x (M+P)) em que, para cada linha, as colunas da primeira e da segunda matriz aparecem concatenadas. Apresente as três matrizes.

22. Escreva um programa para gerar uma matriz (N x M) e outra (N x P), e então gere uma terceira matriz (N x (M+P)) em que, para cada linha, as colunas das duas matrizes aparecem intercaladas. Apresente as três matrizes.

Na concatenação, a coluna j da segunda matriz vai para a posição M + j da matriz final. Na intercalação, contudo, você precisa decidir o que fazer quando M e P forem diferentes, então registre essa regra antes de codificar.

Algoritmos com matrizes e sequências numéricas

Este grupo de algoritmos com matrizes combina a estrutura com sequências clássicas da matemática. Portanto, ele também treina a escrita de funções auxiliares.

23. Escreva um programa para solicitar ao usuário as dimensões de uma matriz. Preencha a matriz com os elementos da sequência de números primos e imprima o resultado.

24. Escreva um programa para solicitar ao usuário as dimensões de uma matriz. Preencha a matriz com os elementos da sequência de Fibonacci e imprima o resultado.

No exercício 23, uma função IsPrime que testa divisores até a raiz quadrada do número já resolve bem. Em seguida, um contador avança até encontrar primos suficientes para preencher todas as posições.

O exercício 29, que aparece mais adiante na lista original, reaproveita essa mesma função de primos. Por isso, ele faz parte deste grupo.

29. Escreva um programa para ler a quantidade de elementos de um vetor, gerar esses elementos e criar uma matriz com uma linha por elemento, em que cada linha tem tantas colunas quanto o valor do elemento mais um. Guarde o elemento do vetor na primeira coluna, preencha as demais posições com a sequência de números primos e imprima a matriz resultante.

Esse enunciado merece um cuidado extra, porque cada linha pode ter um tamanho diferente. Nesse caso, em C#, um jagged array (int[][]) representa melhor a estrutura do que um array retangular.

Ordenação em algoritmos com matrizes

Nos algoritmos com matrizes, a ordenação aparece em quatro variações, que mudam o escopo do que deve ficar em ordem. Assim, você pratica o mesmo raciocínio em níveis diferentes.

25. Escreva um programa para gerar uma matriz Y (N x M). Ordene os elementos da matriz de forma crescente e imprima a matriz original e a matriz ordenada.

26. Escreva um programa para gerar uma matriz W (N x M). Ordene os elementos da matriz de forma decrescente e imprima a matriz original e a matriz ordenada.

27. Escreva um programa para gerar uma matriz X (N x M). Ordene as linhas da matriz de forma crescente e imprima a matriz original e a matriz ordenada.

28. Escreva um programa para gerar uma matriz Z (N x M). Ordene as colunas da matriz de forma crescente e imprima a matriz original e a matriz ordenada.

Uma estratégia simples para o exercício 25 é copiar os elementos para um vetor, ordenar e devolver para a matriz. Dessa forma, você reaproveita algoritmos de ordenação que já conhece.

// Exercício 25: ordenar todos os elementos em ordem crescente
static int[,] SortAll(int[,] source)
{
    var rows = source.GetLength(0);
    var cols = source.GetLength(1);
    var buffer = new int[rows * cols];

    var index = 0;
    foreach (var value in source)
        buffer[index++] = value;

    Array.Sort(buffer);

    var sorted = new int[rows, cols];
    for (var i = 0; i < buffer.Length; i++)
        sorted[i / cols, i % cols] = buffer[i];

    return sorted;
}

Para fins de estudo, porém, vale implementar a ordenação à mão, com Bubble Sort ou Selection Sort. Afinal, o objetivo dos exercícios é treinar a lógica, e não apenas chamar a biblioteca.

Geração com faixa de valores

O último dos algoritmos com matrizes fecha a lista com uma variação da geração aleatória. Ele reforça validação de entrada e uso correto dos limites.

30. Escreva um programa para gerar uma matriz (N x M) com elementos aleatórios dentro de uma faixa de valores inteiros positivos informada pelo usuário (valor inicial e valor final). Ao final, imprima a matriz resultante.

Em C#, o método Random.Shared.Next(min, max) exclui o limite superior. Por isso, para incluir o valor final informado pelo usuário, use max + 1 como segundo argumento.

Conclusão

Você pode usar esses exercícios para fixar os conceitos ensinados em cursos de linguagens de programação. Além disso, eles servem como aquecimento para entrevistas técnicas e desafios de lógica.

Resolva a lista em ordem, porque cada grupo aproveita funções do anterior. Com isso, ao final dos 30 algoritmos com matrizes, você terá uma pequena biblioteca própria para gerar, imprimir, buscar e ordenar dados em duas dimensões.

Cursos relacionados

Gratuito | Fundamentos do C#

Referências

Estas questões são referências diretas ao material produzido por Cristovão Cunha (FEG/UNESP, FATEC), com autorização prévia do autor.

FAQ

Em qual linguagem devo resolver os exercícios?

Use a linguagem com a qual você tem mais facilidade. Os enunciados não dependem de nenhum recurso específico.

Qual a diferença entre matriz e vetor?

O vetor tem uma única dimensão e usa um índice. A matriz tem duas dimensões e usa dois índices, um para a linha e outro para a coluna.

Por que a fórmula da diagonal secundária muda em C#?

Porque os índices em C# começam em zero. Então, a condição deixa de ser i + j = n + 1 e passa a ser i + j = n - 1.

Preciso de matriz quadrada em todos os exercícios?

Não. Somente os exercícios de diagonais e regiões, de 9 a 20, exigem matrizes quadradas.

Posso usar funções prontas de ordenação?

Pode, mas para treinar lógica vale implementar o algoritmo de ordenação por conta própria pelo menos uma vez.