5

Preciso criar um algoritmo em C para rotacionar uma matriz 10x10 em 90 graus, entretanto não posso utilizar uma matriz auxiliar pra isso.

Simplificando o que foi solicitado pra tentar encontrar algum padrão e utilizar ele pra resolver o problema utilizei uma matriz 3x3 e comparei em uma tabela a posição que cada elemento ocupa na matriz original e que irá ocupar na matriz rotacionada.

ORIGINAL     | ROTACIONADA
0x0 0x1 0x2  | 0x2 1x2 2x2
1x0 1x1 1x2  | 0x1 1x1 2x1
2x0 2x1 2x2  | 0x0 1x0 2x0

Dá pra perceber um padrão no qual para a matriz original o valor da linha mantém-se constante a cada ciclo de 3 posições e o valor da coluna é acrescido em 1 neste mesmo ciclo. Para a versão rotacionada da matriz os valores de linha e coluna correspondem, respectivamente, a coluna e linha. Apesar disso não sei como aproveitar essas informações, já que transferindo os valores para as posições correspondentes a versão rotacionada perderei valores que ainda usarei.
Por exemplo:
Transferindo o valor de 0X0 para 2X0 perderei o conteúdo original de 2x0 que precisaria transferir para 2x2 depois.

6
  • 3
    O que você já fez? E não precisa de uma matriz extra, basta uma variável auxiliar dentro de um for... Commented 24/08/2015 às 13:55
  • Na verdade o que eu consegui fazer foi apenas o raciocínio prévio, não consegui fazer um algoritmo justamente pela limitação da perda do conteúdo. E quanto a variável auxiliar eu fiz alguns testes e percebi que precisaria de muitas "variáveis auxiliares", pois em cada ciclo de três posições eu preciso salvar três valores para os próximos ciclos.
    – Vinicius
    Commented 24/08/2015 às 14:55
  • Cara, eu editei a sua pergunta pra tentar deixar mais visual com uma matriz 3x3, poderia verificar se é isso que deve acontecer mesmo? Commented 24/08/2015 às 15:57
  • É exatamente isso que deve acontecer. Obrigado!
    – Vinicius
    Commented 24/08/2015 às 21:19
  • Cara, a lógica é bem simples, você vai ter que alterar o valor entre 4 posições, sendo que todos seguem uma lógica bem simples. Estou meio corrido agora, mas depois eu publico a resposta. (: Commented 24/08/2015 às 22:23

3 Respostas 3

5

Para trocar o valor de 2 variaveis é usual usar uma variável temporária.

// troca a e b
int tmp = a;
a = b;
b = tmp;

No teu caso de rodar a matriz, tens de fazer o mesmo mas com 4 variaveis

// roda 4 variaveis
int tmp = a;
a = b;
b = c;
c = d;
d = tmp;

Agora o problema é seleccionar as variáveis!

Mas não é dificil calcular quais são os elementos que devem rodar para cada um dos elementos da sub matriz 5x5 de cima à esquerda.

O elemento em mat[0][0] deve rodar com mat[9][0], mat[9][9], e mat[0][9].

O elemento em mat[1][3] deve rodar com mat[3][8], mat[8][6], e mat[6][1].

O elemento em mat[row][col] deve rodar com mat[col][10 - row - 1], mat[10 - row - 1][10 - col - 1], e mat[10 - col - 1][row].

Nota: o algoritmo não tem nada a ver com C.

4

O forma mais simples de se fazer isso é rotacionar na tela, ao imprimir. Para uma matriz 3x3 de inteiros, i são as linhas e j são as colunas, você pode exibir ela "tombada" assim:

for(j = 2; j >= 0; j--)       
{
        for(i = 0; i < 3; i++)
        {
               printf("%d      ", mat[i][j]);
        }
        printf("%c", 10);
}

Desta forma você imprime, da direita para a esquerda, colunas como se fossem linhas, "girando" a sua matriz em 90°.

1

Além da resposta do @DaviAragao, é possível que você queira salvar a matriz nela e rotacionar mais de uma vez, bem segue o padrão para rotacionar uma matriz com uma variável auxiliar:

Cada elemento da matriz sempre varia entre 4 posições (Seria equivalente a, em radianos, 0, pi, pi/2 e 3*pi/2), quando completa o ciclo, ela volta para a posição inicial. Isso pode ser verificado na imagem a seguir:

Posições de rotação de elementos de uma borda de uma matriz 4x4

Isso obedece regras de rotação, que você deve subtrair de N (Sendo N o tamanho na matriz, no caso de C seria N-1) o valor da coluna do elemento (que no caso de C começará do 0) e inverter linha com coluna. A ordem que você definir essas operações, definirá o sentido em que a matriz é rotacionada:

  • Trocar linha e coluna e depois subtrair = Sentido horário
  • Subtrair e depois trocar linha e coluna = Sentido anti-horário (igual a imagem)

Em resumo você terá o seguinte meta-algoritmo (isso para uma matriz quadrada NxN e rotação no sentido horário):

para i = 0, i < N/2 e i = i + 1:
    para j = 0, j < N/2 e j = j + 1:
        original = matriz[i][j]
        linha = i
        coluna = j
        para l = 0, l < 3 e l = l + 1:
            se l % 2 = 0:
                matriz[linha][coluna] = matriz[linha][N-coluna]
            senao:
                matriz[linha][coluna] = matriz[N-linha][coluna]
            fimse
            aux = linha
            linha = coluna
            coluna = N-aux
        fimpara
        matriz[linha][coluna] = original
    fimpara
fimpara

Esse algoritmo serve para rotação no sentido horário, para o anti-horário basta alterar a ordem da variável auxiliar e da linha. Vale lembrar que a complexidade desse algoritmo é de O(n²), talvez exista uma forma melhor de resolver esse problema.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .