apostila
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,