apostila

esta´ na posic¸a\u2dco (3,4) do vetor;
\u2022 o elemento 2.5 esta´ na posic¸a\u2dco (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\u2c6 definiu na questa\u2dco anterior. Fac¸a um procedimento para imprimir
a matriz completa, contendo todos os elementos nulos e na\u2dco nulos (na\u2dco precisa
fazer o programa todo, basta o procedimento). Por exemplo, dado vetor com as
informac¸o\u2dces descritas no exemplo da questa\u2dco anterior, a sa´\u131da do seu programa
deve ser exatamente a matriz apresentada no in´\u131cio do exemplo.
19. Considere o tipo PGM para imagens como definido na sec¸a\u2dco 10.2.5. Nas questo\u2dces
que seguem, considere as seguintes estruturas de dados e assinaturas de func¸o\u2dces
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 ;
(\u2217 funcao que retorna o valor medio dos pixels da imagem, isto eh
a soma de todos os elementos dividido pelo numero de elementos \u2217)
procedure ler (var I : imagem) ;
(\u2217 procedimento que le uma imagem no formato PGM \u2217)
procedure imprime imagem (var I : imagem) ;
(\u2217 procedimento que imprime uma imagem no formato PGM \u2217)
procedure binariza (var I : imagem; limiar : integer) ;
(\u2217 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 \u2217)
procedure compacta imagem (var I : imagem; var C: imgcompactada) ;
(\u2217 procedimento que recebe uma imagem no formato PGM e cria um vetor C
que eh uma representacao compactada desta \u2217)
procedure imprime img compactada (var C: imgcompactada) ;
(\u2217 procedure que recebe uma imagem compactada e a imprime no formato PGM \u2217)
(a) Implemente estas func¸o\u2dces 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\u2c6ncias de uns pelo nu´mero
de uns consecutivos. Os elementos va\u2dco sendo colocados no vetor, de ma-
neira linear, cada linha seguinte e´ concatenada a` anterior. Veja o exemplo:
Exemplo:
\u2022 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
\u2022 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 \u201c4, 0 e 5\u201d. Preste atenc¸a\u2dco antes de escrever o co´digo. Voce\u2c6
pode definir, se precisar, func¸o\u2dces, procedimentos ou estruturas de dados
adicionais.
224 CAPI´TULO 10. ESTRUTURAS DE DADOS
Cap´\u131tulo 11
Desenvolvendo programas de maior
porte
Neste ponto do curso ja´ temos todas as noc¸o\u2dces fundamentais de algoritmos e estruturas
de dados que sa\u2dco necessa´rias para a construc¸a\u2dco de programas complexos. O objetivo
daqui para frente e´ mostrar como se desenvolver programas de maior porte em relac¸a\u2dco
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´\u131vel gratuitamente em diversos sistemas operacio-
nais modernos. Uma descric¸a\u2dco do funcionamento deste jogo pode ser encontrada na
Wikipedia1.
Vamos tentar implementar a versa\u2dco ASCII do jogo, contudo com algumas simpli-
ficac¸o\u2dces: vamos ignorar as bandeiras que se podem colocar para marcac¸a\u2dco 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\u2dco 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\u2dco do problema. Para isto vamos explorar ao ma´ximo as noc¸o\u2dces de
func¸o\u2dces e procedimentos da linguagem Pascal.
Vamos partir da existe\u2c6ncia de um tabuleiro de dimenso\u2dces N ×M que conte´m um
certo nu´mero B de bombas em algumas posic¸o\u2dces. As outras posic¸o\u2dces 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\u2dco e´ exibido o valor
da ce´lula. O jogo tambe´m termina quando o usua´rio abriu todas as posic¸o\u2dces que na\u2dco
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\u2dces das estruturas de
1http://pt.wikipedia.org/wiki/Campo_minado
225
226 CAPI´TULO 11. DESENVOLVENDO PROGRAMAS DE MAIOR PORTE
dados necessa´rias.
begin (\u2217 programa principal \u2217)
\u2018 \u2018Criar o campo minado de dimensoes NxM contendo B bombas\u2019\u2019
repeat
\u2018 \u2018 Imprimir o tabuleiro ocultando as celulas nao abertas\u2019\u2019
\u2018 \u2018Ler as coordenadas da celula a ser aberta\u2019\u2019
\u2018 \u2018Abrir a celula indicada\u2019\u2019
\u2018 \u2018Se nao era bomba, entao
atualiza bombas restantes\u2019\u2019
\u2018 \u2018Senao
jogador perdeu\u2019\u2019
until \u2018 \u2018 jogador ganhou\u2019\u2019 or \u2018 \u2018 jogador perdeu\u2019\u2019 ;
\u2018 \u2018 Imprimir o tabuleiro final\u2019\u2019 ;
end.
Figura 11.1: Pseudoco´digo para campo minado.
Podemos imaginar algumas func¸o\u2dces e procedimentos contendo alguns para\u2c6metros
parcialmente definidos, mas ja´ com o comportamento desejado. Por exemplo, vamos
supor a existe\u2c6ncia dos seguites:
CriaCampoMinado (campo): Procedimento que cria um campo minado contendo
dimenso\u2dces 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\u2dco. 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\u2dco abertas na\u2dco sa\u2dco 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\u2c6 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\u2dco va´lidas. Ac¸a\u2dco 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\u2dco que abre a ce´lula (i, j) do campo minado e
retorna false caso a ce´lula contenha uma bomba. Sena\u2dco, retorna true. No
caso da ce´lula conter uma bomba, tambe´m retorna o campo minado com a
informac¸a\u2dco de que todas as ce´lulas do campo sa\u2dco 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\u2dco considera como abertas todas as
227
ce´lulas vizinhas de (i, j). Se uma destas tambe´m contiver zero bombas vizinhas,