Re: [obm-l] Armazenamento de Matriz em Vetor

["Ojesed Mirror" <ojesed@xxxxxxxxxx>]

Para calcular a linha use i=(sqrt(8*pos + 9)-3)/2 e arredonde para cima.
Para calcular a coluna use a formula que calcula pos.

Ojesed.

----- Original Message ----- 
From: "Henrique Renn�" <henrique.renno@gmail.com>
To: <obm-l@mat.puc-rio.br>
Sent: Tuesday, April 11, 2006 11:11 AM
Subject: [obm-l] Armazenamento de Matriz em Vetor


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
=========================================================================


-- 
No virus found in this incoming message.
Checked by AVG Free Edition.
Version: 7.1.385 / Virus Database: 268.4.1/307 - Release Date: 10/4/2006


=========================================================================
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
=========================================================================