[obm-l] Armazenamento de Matriz em Vetor

["Henrique Rennó" <henrique.renno@xxxxxxxxx>]

Olá pessoal da lista!!!

Estou com um problema para representar uma matriz na forma de um
vetor. Suponha que tenhamos uma matriz diagonal inferior:

1 0 0 0 0
6 3 0 0 0
4 2 6 0 0
8 3 7 1 0
9 5 2 7 4

Não há necessidade de representar essa matriz armazenando todos os
elementos, pois sabemos que acima da diagonal principal todos os
elementos são zero. Dessa forma, podemos armazenar apenas os elementos
da diagonal principal e da parte inferior seguindo a seguinte regra:

pos = [(1+i)*i]/2 + j

onde pos é a posição no vetor e a posição na matriz inicia em i = 0, j
= 0 (i = linha, j = coluna). Uma matriz de dimensão N tem seus
elementos na forma:

0,0 0,1 0,2 ... 0,N-1
1,0 1,1 1,2 ... 1,N-1
  .    .    .    .    .
  .    .    .    .    .
  .    .    .    .    .
N-1,0 N-1,1 ... N-1,N-1

Por exemplo, se i = 3 e j = 2, pos seria 8 e o elemento 7 estaria
nesta posição. (O vetor se inicia na posição zero - 0).

O problema é saber uma forma de, conhecendo pos (a posição do elemento
no vetor), saber quais os valores de i e j (linha e coluna) do
elemento na matriz.

Estou com essa dúvida porque estou desenvolvendo um programa em C para
mexer com matrizes que estão nessa forma (os elementos acima da
diagonal superior são todos zeros) e para dimensões maiores, por
exemplo 10000, teríamos um número imenso de zeros ocupando memória sem
necessidade.

Obs: caso a matriz possua todos os elementos nulos abaixo da diagonal
principal, acredito que trocando i por j e j por i na igualdade acima
para o cálculo de pos funciona normalmente, mas o que preciso mesmo
não é este caso.

Agradeço a atenção de todos,

Abraços!!!

--
Henrique

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================