Sistemas de numeração e a representação linear de tabelas multi-dimensionais

Apesar do aspecto pomposo do título deste texto, a ideia subjacente ao problema em questão é deveras simples. No artigo "Simulação de uma estrutura de dados multi-dimensional" fiz referência a uma estrutura de dados indexada por um conjunto ordenado de índices inteiros de dimensão arbitrária do qual apresentei uma implementação. Neste artigo pretendo descrever o pormenor fundamental da sua implementação.

Os dados aferentes à estrutura em questão são armazenados num vector, onde as funções que permitem aceder ao valor associado a um determinado multi-índice convertem-no num índice linear. A título de exemplo, consideramos a matriz 2×2 que, ao índice (0,0) fazemos corresponder o 4, ao índice (1,0) fazemos corresponder o 1, ao índice (0,1) fazemos corresponder o 2 e ao índice (1,1) fazemos corresponder o 3, representada pela seguinte tabela

4

2

1

3

Esta matriz é representável numa estrutura linear como [4,1,2,3]. Um pouco de aritmética elementar permite concluir que o elemento correspondente ao índice (1,0) da matriz corresponde à posição linear 1+0x1=1. Em geral, seja [a1,a2,…,an] um vector que representa uma estrutura a1x a2 x … x an. Suponhamos que pretendemos obter a posição linear correspondente ao conjunto ordenado de índices (c1,c2,…,cn) onde ci<ai para todos os valores de i compreendidos entre 1 e n. A sua posição linear p é dada pela fórmula (chama-se a isto contas de mercearia):
p=c1+c2a1+c3a1a2+…+cna1a2…an-1
Se todos os valores ai forem iguais a m, a posição linear correspondente ao conjunto ordenado (c1,c2,…,cn) corresponde à representação decimal do número escrito na base m, (c1c2,…cn)m. Encaramos o problema da representação linear dos índices como um sistema de numeração com bases variáveis. Dada a posição linear p menor que o produto dos ai, como determinar as respectivas coordenadas? Tendo em conta a semelhança entre este problema e os sistemas de numeração, a solução é simples e é dada de forma recursiva: c1=p mod a1, c2=(p-c1)/a1 mod a2, c3=(p-c1-c2a1)/(a1a2) mod a3, e assim sucessivamente. Denotei por a mod b como sendo o resto da divisão inteira de a por b.

Sobre Sérgio O. Marques

Licenciado em Física/Matemática Aplicada (Astronomia) pela Faculdade de Ciências da Universidade do Porto e Mestre em Matemática Aplicada pela mesma instituição, desenvolvo trabalho no PTC (Porto Technical Centre) - Yazaki como Administrador de bases-de-dados. Dentro o meu leque de interesses encontram-se todos os temas afins às disciplinas de Matemática, Física e Astronomia. Porém, como entusiasta, interesso-me por temas relacionados com electrónica, poesia, música e fotografia.
Esta entrada foi publicada em Matemática. ligação permanente.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s