Universidade de São Paulo

Instituto de Ciências Matemáticas e de Computação

Departamento de Ciências da Computação e Estatística

Primeiro Semestre de 1999

Considere o domínio do mundo dos blocos em que existe uma mesa que suporta 3 blocos nos quais podem ser empilhados outros blocos, e que a pilha possa ter qualquer altura. Estados neste domínio podem ser representados por uma lista de 3 listas. Por exemplo:

Escreva um programa imprime(estado) que imprime um dado Estado na forma visual acima.

A solução proposta para o problema foi considerar a lista de listas uma matriz.

Ex: [[a,b,c],[d],[e,f]] =	a	b	c
	d
	e	f

A solução do problema foi então imaginada como a transposição da matriz acima, onde:

a	b	c		a	d	e
d			= t =>	b		f
e	f			c

Nota-se que a diferença entre a transposta da matriz e a representação desejada é a disposição dos elementos vazios da matriz. Esta disposição pode ser alterada invertendo os elementos das linhas da matriz, de maneira que:

a	b	c		c	b	a
d			= i1 =>	d
e	f			f	e

Uma vez invertida a ordem dos elementos da matriz, como ilustrado acima, a transposta da matriz com os elementos invertidos gerará:

c	b	a		c	d	f
d			= t =>	b		e
f	e			a

A matriz transposta difere da representação desejada apenas na ordem das linhas da matriz. Como a matriz é representada através de uma lista de listas, basta então inverter a ordem das listas desta lista, de maneira que:

c	d	f		a
b		e	= i2 =>	b		f
a				c	d	e

Assim, alcançamos o objetivo do trabalho.

O problema foi resolvido através da manipulação de listas. Três operações foram utilizadas:

• Inversão de elementos de uma lista;
• Transposição de uma matriz representada por uma lista de listas, onde cada lista consiste em uma linha da matriz;
• Verificação de listas vazias contidas em uma lista.

A inversão de elementos de uma lista foi facilmente resolvido através de:

Onde elementos da lista de entrada são retirados um a um e colocados em uma lista temporária. Quando a lista de entrada torna-se vazia, a lista temporária é copiada para a lista de saída.

A transposição da matriz foi resolvida em três passos:

• A chamada em alto nível para a transposição:

• A chamada da função recursiva onde dada uma lista de listas MatrizA é feita a separação das linhas desta matriz que posteriormente serão transformadas em colunas. A lista de listas MatrizC é a matriz temporária que armazena os elementos não retirados da MatrizA:

• A chamada da função auxiliar que monta a nova matriz transposta e retorna a matriz com os elementos que ainda não foram transpostos:

A verificação se a lista é composta de listas vazias é feita através de simples comparações:

Uma descrição mais detalhada pode ser observada no arquivo block.pl que implementa a solução descrita acima.

Obs.: A solução proposta não limita que o número de blocos seja 3, permitindo que qualquer número de blocos seja representado.

Aqui estão listados os resultados de alguns testes utilizando a implementação da solução proposta.