apostila
259 pág.

apostila

Disciplina:Algoritmos e Estrutura de Dados I542 materiais7.968 seguidores
Pré-visualização50 páginas
esta´ na posic¸a˜o (3,4) do vetor;
• o elemento 2.5 esta´ na posic¸a˜o (4,3) do vetor;

222 CAPI´TULO 10. ESTRUTURAS DE DADOS

18. Considere uma estrutura de vetores para representar uma matriz esparsa, tal
como voceˆ definiu na questa˜o anterior. Fac¸a um procedimento para imprimir
a matriz completa, contendo todos os elementos nulos e na˜o nulos (na˜o precisa
fazer o programa todo, basta o procedimento). Por exemplo, dado vetor com as
informac¸o˜es descritas no exemplo da questa˜o anterior, a sa´ıda do seu programa
deve ser exatamente a matriz apresentada no in´ıcio do exemplo.

19. Considere o tipo PGM para imagens como definido na sec¸a˜o 10.2.5. Nas questo˜es
que seguem, considere as seguintes estruturas de dados e assinaturas de func¸o˜es
e procedimentos:

const MAX=10000;

type
matriz = array [ 1 . .MAX,1 . .MAX] of integer ;

vetor = array [ 1 . .MAX] of integer ;

imagem = record
col , lin , maior : integer ;
m: matriz ;

end;

imgcompactada = record
tam: integer ;
v: vetor ;

end;

function calcula valor medio (var I : imagem) : integer ;
(∗ funcao que retorna o valor medio dos pixels da imagem, isto eh

a soma de todos os elementos dividido pelo numero de elementos ∗)

procedure ler (var I : imagem) ;
(∗ procedimento que le uma imagem no formato PGM ∗)

procedure imprime imagem (var I : imagem) ;
(∗ procedimento que imprime uma imagem no formato PGM ∗)
procedure binariza (var I : imagem; limiar : integer) ;
(∗ procedimento que transforma a imagem de tons de cinza para preto e branco

para isto , os pixels que forem maiores que o limiar devem se tornar brancos
e os que forem menores ou iguais a este mesmo limiar devem se tornar pretos ∗)

procedure compacta imagem (var I : imagem; var C: imgcompactada) ;
(∗ procedimento que recebe uma imagem no formato PGM e cria um vetor C

que eh uma representacao compactada desta ∗)

procedure imprime img compactada (var C: imgcompactada) ;
(∗ procedure que recebe uma imagem compactada e a imprime no formato PGM ∗)

(a) Implemente estas func¸o˜es e procedimentos e fac¸a um programa que receba
um certo nu´mero N de imagens PGM em tons de cinza (onde 0 representa
preto e branco e´ representado pelo maior valor da imagem) e imprima a

10.3. REGISTROS 223

imagem binarizada, isto e´, em preto e branco (onde 0 representa preto e 1
representa branco). Note que o limiar e´ obtido pelo valor me´dio dos pixels.

(b) Implemente um procedimento que gere um vetor que representa a matriz
binarizada de forma compacta. Para isto, use a seguinte ideia: como a
matriz so´ tem zeros e uns, vamos substituir sequeˆncias de uns pelo nu´mero
de uns consecutivos. Os elementos va˜o sendo colocados no vetor, de ma-
neira linear, cada linha seguinte e´ concatenada a` anterior. Veja o exemplo:
Exemplo:
• Imagem binarizada:

P2

11 10

1

1 1 1 1 0 1 1 1 1 1 0

1 1 0 1 1 1 1 1 1 1 1

0 0 1 0 0 0 1 1 1 0 0

1 1 1 1 1 1 1 1 1 1 1

0 0 0 1 1 1 1 1 0 0 0

0 0 0 1 1 1 1 1 1 1 1

1 1 1 0 1 1 1 1 1 1 1

1 1 1 1 1 1 1 0 1 1 1

1 1 1 1 1 1 1 1 1 0 0

0 1 1 1 1 1 1 1 1 1 1

• Imagem compactada:
36

4 0 5 0 2 0 8 0 0 1 0 0 0 3 0 0 11 0 0 0 5 0 0 0 0 0 0 11 0 14 0 12 0 0 0 10

Isto e´, a primeira linha da matriz possui 4 uns consecutivos seguido de um
zero e outros 5 uns consecutivos, por isto, o vetor conte´m seus primeiros
elementos “4, 0 e 5”. Preste atenc¸a˜o antes de escrever o co´digo. Voceˆ
pode definir, se precisar, func¸o˜es, procedimentos ou estruturas de dados
adicionais.

224 CAPI´TULO 10. ESTRUTURAS DE DADOS

Cap´ıtulo 11

Desenvolvendo programas de maior
porte

Neste ponto do curso ja´ temos todas as noc¸o˜es fundamentais de algoritmos e estruturas
de dados que sa˜o necessa´rias para a construc¸a˜o de programas complexos. O objetivo
daqui para frente e´ mostrar como se desenvolver programas de maior porte em relac¸a˜o
aos que vimos ate´ agora.

11.0.1 Campo minado

O primeiro grande problema que vamos tentar resolver e´ o conhecido jogo do Campo
minado, costumeiramente dispon´ıvel gratuitamente em diversos sistemas operacio-
nais modernos. Uma descric¸a˜o do funcionamento deste jogo pode ser encontrada na
Wikipedia1.

Vamos tentar implementar a versa˜o ASCII do jogo, contudo com algumas simpli-
ficac¸o˜es: vamos ignorar as bandeiras que se podem colocar para marcac¸a˜o de prova´veis
bombas e tambe´m vamos ignorar a contagem do tempo e registro dos recordes. Como
a interface e´ ASCII, naturalmente tambe´m na˜o vamos nos preocupar com a beleza da
interface.

A ideia e´ desenvolvermos um co´digo final usando-se a te´cnica de refinamentos
sucessivos, isto e´, vamos partir de um co´digo geral, muitas vezes escritos em pseudo-
linguagem, e a cada etapa detalharmos as estruturas de dados e algoritmos necessa´rios
para a resoluc¸a˜o do problema. Para isto vamos explorar ao ma´ximo as noc¸o˜es de
func¸o˜es e procedimentos da linguagem Pascal.

Vamos partir da existeˆncia de um tabuleiro de dimenso˜es N ×M que conte´m um
certo nu´mero B de bombas em algumas posic¸o˜es. As outras posic¸o˜es conte´m o nu´mero
total de bombas vizinhas. A cada jogada, o usua´rio entra com as coordenadas (i, j)
onde deseja abrir o tabuleiro, se for uma bomba, o jogo acaba, sena˜o e´ exibido o valor
da ce´lula. O jogo tambe´m termina quando o usua´rio abriu todas as posic¸o˜es que na˜o
tem bombas.

O pseudoco´digo que resolve este problema esta´ ilustrado na figura 11.1. Neste
ponto do desenvolvimento, optamos por postergar as definic¸o˜es das estruturas de

1http://pt.wikipedia.org/wiki/Campo_minado

225

226 CAPI´TULO 11. DESENVOLVENDO PROGRAMAS DE MAIOR PORTE

dados necessa´rias.

begin (∗ programa principal ∗)

‘ ‘Criar o campo minado de dimensoes NxM contendo B bombas’’

repeat
‘ ‘ Imprimir o tabuleiro ocultando as celulas nao abertas’’
‘ ‘Ler as coordenadas da celula a ser aberta’’
‘ ‘Abrir a celula indicada’’
‘ ‘Se nao era bomba, entao

atualiza bombas restantes’’
‘ ‘Senao

jogador perdeu’’
until ‘ ‘ jogador ganhou’’ or ‘ ‘ jogador perdeu’’ ;

‘ ‘ Imprimir o tabuleiro final’’ ;
end.

Figura 11.1: Pseudoco´digo para campo minado.

Podemos imaginar algumas func¸o˜es e procedimentos contendo alguns paraˆmetros
parcialmente definidos, mas ja´ com o comportamento desejado. Por exemplo, vamos
supor a existeˆncia dos seguites:

CriaCampoMinado (campo): Procedimento que cria um campo minado contendo
dimenso˜es N ×M com B bombas de maneira que cada elemento deste campo
minado, quando clicado, exibe uma bomba ou o nu´mero de bombas ao redor da
posic¸a˜o. Inicialmente este campo e´ criado de maneira que nenhuma ce´lula ainda
foi aberta.

ImprimeCampoMinado (campo): Procedimento que imprime o campo minado
de maneira que as ce´lulas ainda na˜o abertas na˜o sa˜o exibidas ao usua´rio. Para
as que ja´ foram abertas e´ exibido o nu´mero de ce´lulas vizinhas contendo bombas
ou uma bomba.

LerCoordenadas (i, j, acao): Procedimento que leˆ um par de coordenadas repre-
sentando respectivamente a linha i e a coluna j de uma ce´lula para ser aberta.
O procedimento garante que as coordenadas sa˜o va´lidas. Ac¸a˜o define o que fazer
com a coordenada, se for zero e´ para abrir a ce´lula, se for 1, e´ para marcar com
uma bandeira e se for 2 e´ para desmarcar a bandeira.

AbrirCelula (campo, i, j): Func¸a˜o que abre a ce´lula (i, j) do campo minado e
retorna false caso a ce´lula contenha uma bomba. Sena˜o, retorna true. No
caso da ce´lula conter uma bomba, tambe´m retorna o campo minado com a
informac¸a˜o de que todas as ce´lulas do campo sa˜o agora consideradas abertas.
No caso contra´rio, considera como abertas as ce´lulas da seguinte maneira: se a
ce´lula conte´m um nu´mero diferente de zero bombas, abre somente a coordenada
(i, j). Se for um valor de zero bombas, enta˜o considera como abertas todas as

227

ce´lulas vizinhas de (i, j). Se uma destas tambe´m contiver zero bombas vizinhas,