Pré-visualização50 páginas
. . . . . . . . . . . . . . . . . . . . . 163 10.2 Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 10.2.1 Matrizes em Pascal . . . . . . . . . . . . . . . . . . . . . . . . . 179 10.2.2 Exemplos elementares . . . . . . . . . . . . . . . . . . . . . . . 180 10.2.3 Procurando elementos em matrizes . . . . . . . . . . . . . . . . 186 10.2.4 Inserindo uma coluna em uma matriz . . . . . . . . . . . . . . . 188 10.2.5 Aplicac¸o\u2dces de matrizes em imagens . . . . . . . . . . . . . . . . 190 10.2.6 Exerc´\u131cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 10.3 Registros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 10.3.1 Introduc¸a\u2dco aos registros . . . . . . . . . . . . . . . . . . . . . . 209 10.3.2 Vetores de registros . . . . . . . . . . . . . . . . . . . . . . . . . 210 10.3.3 Registros com vetores . . . . . . . . . . . . . . . . . . . . . . . . 212 10.3.4 Observac¸o\u2dces importantes . . . . . . . . . . . . . . . . . . . . . . 213 10.3.5 Exerc´\u131cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 11 Desenvolvendo programas de maior porte 225 11.0.1 Campo minado . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 11.1 Exerc´\u131cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 12 Tipos abstratos de dados 241 12.1 Tipo Conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 12.2 Tipo Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 12.2.1 Exerc´\u131cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 6 SUMA´RIO Cap´\u131tulo 1 Introduc¸a\u2dco Este material conte´m notas de aulas da disciplina CI055 \u2013 Algoritmos e Estruturas de Dados I, ministrada para os curso de Bacharelado em Cie\u2c6ncia da Computac¸a\u2dco (BCC), Matema´tica Industrial (MatInd) e para o Bacharelado em Informa´tica Biome´dica (BIB) da Universidade Federal do Parana´. Esta disciplina e´ ministrada no primeiro semestre (para os calouros) e e´ a primeira das quatro que cobrem o conteu´do ba´sico de algoritmos sem o qual um curso de computac¸a\u2dco na\u2dco faz sentido. As disciplinas subsequentes sa\u2dco: \u2022 Algoritmos e Estruturas de Dados II; \u2022 Algoritmos e Estruturas de Dados III; e \u2022 Algoritmos e Teoria dos Grafos. A orientac¸a\u2dco da Coordenac¸a\u2dco dos cursos e´ que este deve ter um conteu´do forte em conceitos de algoritmos no qual a implementac¸a\u2dco final em uma linguagem de pro- gramac¸a\u2dco e´ vista apenas como um mecanismo facilitador ao aprendizado dos conceitos teo´ricos. O texto esta´ dividido em duas partes bem definidas, a primeira entre os cap´\u131tulos 2 e 9, conte´m os princ´\u131pios ba´sicos da construc¸a\u2dco de algoritmos elementares, incluindo a parte de subprogramas, com especial atenc¸a\u2dco a questo\u2dces tais como passagem de para\u2c6metros e varia´veis locais e globais. A noc¸a\u2dco de modularidade e´ bastante explorada. A segunda parte, a partir do cap´\u131tulo 10, conte´m princ´\u131pios de estruturas de dados ba´sicas, onde se introduz a noc¸a\u2dco de vetores unidimensionais, a primeira das estruturas de dados. Nesta estrutura, praticamos a elaborac¸a\u2dco de algoritmos modulares e ja´ na\u2dco escrevemos um co´digo inteiro, mas sim um conjunto de func¸o\u2dces e procedimentos que, em uma abordagem por refinamentos sucessivos (top down), sa\u2dco constru´\u131dos passo a passo. Alguns algoritmos importantes sa\u2dco estudados em suas verso\u2dces ba´sicas: busca e ordenac¸a\u2dco de vetores. Noc¸o\u2dces de complexidade de algoritmos sa\u2dco mencionadas, ainda que de modo informal, pois isto e´ conteu´do de per´\u131odos mais avanc¸ados. Contudo, e´ importante ao aprendiz ter noc¸a\u2dco clara da diferenc¸a de custo entre diferentes algorit- mos. 7 8 CAPI´TULO 1. INTRODUC¸A\u2dcO As u´ltimas estruturas de dados relevantes para o primeiro per´\u131odo sa\u2dco as matrizes e o conceito de registro. Havendo tempo, tambe´m se discute estruturas um pouco mais sofisticadas, misturando-se vetores, registros e matrizes. Finalmente se oferece um desafio aos alunos. O objetivo e´ o de mostrar uma aplicac¸a\u2dco interessante dos conceitos que eles ja´ dominam. Normalmente trabalha-se em sala de aula o desenvolvimento de um programa que tem sido a construc¸a\u2dco de um jogo simples que pode ser implementado em uma estrutura de matriz, eventualmente com registros. A ideia e´ que eles possam fazer um programa mais extenso para treinarem a construc¸a\u2dco de programas modulares. Este material constitui o u´ltimo cap´\u131tulo deste material. O estudante na\u2dco deve iniciar uma parte sem antes ter compreendido o conteu´do das anteriores. Tambe´m na\u2dco deve iniciar um novo cap´\u131tulo sem ter compreendido os anteriores. Sobre a linguagem, o estudante e´ encorajado a buscar apoio na literatura e nos guias de refere\u2c6ncia dispon´\u131veis para o compilador escolhido (Free Pascal), incluindo um guia de refere\u2c6ncia ba´sico que foi escrito pelos monitores da disciplina no ano de 2009. A leitura destas notas de aula na\u2dco isenta o estudante de buscar literatura comple- mentar, sempre bem-vinda. Em particular, uma o´tima histo´ria da computac¸a\u2dco pode ser encontrada em [Tre83]. Alguns excelentes textos introduto´rios em algoritmos esta\u2dco em [Car82], [Sal98], [Med05] e [Wir78]. Para mais detalhes de programac¸a\u2dco em Pascal o leitor pode consultar [Far99] e tambe´m os guias de refere\u2c6ncia da linguagem [Gui]. Finalmente, embora talvez de dif´\u131cil compreensa\u2dco para um iniciante, recomendamos pelo menos folhear o material em [Knu68]. Cap´\u131tulo 2 Sobre problemas e soluc¸o\u2dces Vamos iniciar nosso estudo com uma breve discussa\u2dco sobre problemas e soluc¸o\u2dces. O objetivo e´ deixar claro desde o in´\u131cio que: \u2022 na\u2dco existe, em geral, uma u´nica soluc¸a\u2dco para o mesmo problema; \u2022 algumas soluc¸o\u2dces sa\u2dco melhores do que outras, sob algum crite´rio; \u2022 alguns problemas sa\u2dco casos particulares de outros similares; \u2022 as vezes, e´ melhor resolver o problema mais gene´rico, assim, resolve-se uma classe de problemas, e na\u2dco apenas um. Sera\u2dco apresentados dois problemas reais e para cada um deles segue uma discussa\u2dco sobre a existe\u2c6ncia de diversas soluc¸o\u2dces para um dado problema. A e\u2c6nfase sera´ dada nas diferenc¸as entre as soluc¸o\u2dces e tambe´m na discussa\u2dco sobre ate´ que ponto deve-se ficar satisfeito com a primeira soluc¸a\u2dco obtida ou se ela pode ser generalizada para problemas similares. 2.1 Contando o nu´mero de presentes em um evento No primeiro dia letivo do primeiro semestre de 2009, um dos autores deste material colocou o seguinte problema aos novos alunos: quer´\u131amos saber quantos estudantes estavam presentes na sala de aula naquele momento. A sala tinha capacidade aproxi- mada de 100 lugares e a naquele momento estava razoavelmente cheia. Os estudantes discutiram va´rias possibilidades. Apresentamos todas elas a seguir. Primeira soluc¸a\u2dco A primeira soluc¸a\u2dco parecia ta\u2dco o´bvia que levou algum tempo ate´ algum aluno verbali- zar: o professor conta os alunos um por um, tomando o cuidado de na\u2dco contar algue´m duas vezes e tambe´m de na\u2dco esquecer de contar algue´m. Quais sa\u2dco as vantagens deste me´todo? Trata-se de uma soluc¸a\u2dco simples, fa´cil de executar e produz o resultado correto. E´ uma soluc¸a\u2dco perfeita para salas de aula com 9 10 CAPI´TULO 2. SOBRE PROBLEMAS E SOLUC¸O\u2dcES poucos alunos, digamos, 20 ou 30. Outro aspecto considerado foi o fato de que este me´todo na\u2dco exige nenhum conhecimento pre´vio de quem vai executar a operac¸a\u2dco, a na\u2dco ser saber contar. Tambe´m na\u2dco exige nenhum equipamento adicional. Quais as desvantagens? Se o nu´mero de alunos na sala for grande, o tempo ne- cessa´rio para o te´rmino da operac¸a\u2dco pode ser insatisfato´rio. Para piorar, quanto maior o nu´mero, maior a chance de aparecerem erros na contagem. Foi discutida a adequac¸a\u2dco desta soluc¸a\u2dco para se contar os presentes em um com\u131´cio ou manifestac¸a\u2dco popular numa prac¸a pu´blica. Concluiu-se pela