apostila

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,