. . . . . . . . . . . . . . . . . . . . . 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˜es de matrizes em imagens . . . . . . . . . . . . . . . . 190 10.2.6 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 10.3 Registros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 10.3.1 Introduc¸a˜o aos registros . . . . . . . . . . . . . . . . . . . . . . 209 10.3.2 Vetores de registros . . . . . . . . . . . . . . . . . . . . . . . . . 210 10.3.3 Registros com vetores . . . . . . . . . . . . . . . . . . . . . . . . 212 10.3.4 Observac¸o˜es importantes . . . . . . . . . . . . . . . . . . . . . . 213 10.3.5 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 11 Desenvolvendo programas de maior porte 225 11.0.1 Campo minado . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 11.1 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 12 Tipos abstratos de dados 241 12.1 Tipo Conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 12.2 Tipo Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 12.2.1 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 6 SUMA´RIO Cap´ıtulo 1 Introduc¸a˜o Este material conte´m notas de aulas da disciplina CI055 – Algoritmos e Estruturas de Dados I, ministrada para os curso de Bacharelado em Cieˆncia da Computac¸a˜o (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˜o na˜o faz sentido. As disciplinas subsequentes sa˜o: • Algoritmos e Estruturas de Dados II; • Algoritmos e Estruturas de Dados III; e • Algoritmos e Teoria dos Grafos. A orientac¸a˜o da Coordenac¸a˜o dos cursos e´ que este deve ter um conteu´do forte em conceitos de algoritmos no qual a implementac¸a˜o final em uma linguagem de pro- gramac¸a˜o 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´ıtulos 2 e 9, conte´m os princ´ıpios ba´sicos da construc¸a˜o de algoritmos elementares, incluindo a parte de subprogramas, com especial atenc¸a˜o a questo˜es tais como passagem de paraˆmetros e varia´veis locais e globais. A noc¸a˜o de modularidade e´ bastante explorada. A segunda parte, a partir do cap´ıtulo 10, conte´m princ´ıpios de estruturas de dados ba´sicas, onde se introduz a noc¸a˜o de vetores unidimensionais, a primeira das estruturas de dados. Nesta estrutura, praticamos a elaborac¸a˜o de algoritmos modulares e ja´ na˜o escrevemos um co´digo inteiro, mas sim um conjunto de func¸o˜es e procedimentos que, em uma abordagem por refinamentos sucessivos (top down), sa˜o constru´ıdos passo a passo. Alguns algoritmos importantes sa˜o estudados em suas verso˜es ba´sicas: busca e ordenac¸a˜o de vetores. Noc¸o˜es de complexidade de algoritmos sa˜o mencionadas, ainda que de modo informal, pois isto e´ conteu´do de per´ıodos mais avanc¸ados. Contudo, e´ importante ao aprendiz ter noc¸a˜o clara da diferenc¸a de custo entre diferentes algorit- mos. 7 8 CAPI´TULO 1. INTRODUC¸A˜O As u´ltimas estruturas de dados relevantes para o primeiro per´ıodo sa˜o 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˜o 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˜o 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˜o de programas modulares. Este material constitui o u´ltimo cap´ıtulo deste material. O estudante na˜o deve iniciar uma parte sem antes ter compreendido o conteu´do das anteriores. Tambe´m na˜o deve iniciar um novo cap´ıtulo sem ter compreendido os anteriores. Sobre a linguagem, o estudante e´ encorajado a buscar apoio na literatura e nos guias de refereˆncia dispon´ıveis para o compilador escolhido (Free Pascal), incluindo um guia de refereˆncia ba´sico que foi escrito pelos monitores da disciplina no ano de 2009. A leitura destas notas de aula na˜o isenta o estudante de buscar literatura comple- mentar, sempre bem-vinda. Em particular, uma o´tima histo´ria da computac¸a˜o pode ser encontrada em [Tre83]. Alguns excelentes textos introduto´rios em algoritmos esta˜o em [Car82], [Sal98], [Med05] e [Wir78]. Para mais detalhes de programac¸a˜o em Pascal o leitor pode consultar [Far99] e tambe´m os guias de refereˆncia da linguagem [Gui]. Finalmente, embora talvez de dif´ıcil compreensa˜o para um iniciante, recomendamos pelo menos folhear o material em [Knu68]. Cap´ıtulo 2 Sobre problemas e soluc¸o˜es Vamos iniciar nosso estudo com uma breve discussa˜o sobre problemas e soluc¸o˜es. O objetivo e´ deixar claro desde o in´ıcio que: • na˜o existe, em geral, uma u´nica soluc¸a˜o para o mesmo problema; • algumas soluc¸o˜es sa˜o melhores do que outras, sob algum crite´rio; • alguns problemas sa˜o casos particulares de outros similares; • as vezes, e´ melhor resolver o problema mais gene´rico, assim, resolve-se uma classe de problemas, e na˜o apenas um. Sera˜o apresentados dois problemas reais e para cada um deles segue uma discussa˜o sobre a existeˆncia de diversas soluc¸o˜es para um dado problema. A eˆnfase sera´ dada nas diferenc¸as entre as soluc¸o˜es e tambe´m na discussa˜o sobre ate´ que ponto deve-se ficar satisfeito com a primeira soluc¸a˜o 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´ıamos 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˜o A primeira soluc¸a˜o parecia ta˜o o´bvia que levou algum tempo ate´ algum aluno verbali- zar: o professor conta os alunos um por um, tomando o cuidado de na˜o contar algue´m duas vezes e tambe´m de na˜o esquecer de contar algue´m. Quais sa˜o as vantagens deste me´todo? Trata-se de uma soluc¸a˜o simples, fa´cil de executar e produz o resultado correto. E´ uma soluc¸a˜o perfeita para salas de aula com 9 10 CAPI´TULO 2. SOBRE PROBLEMAS E SOLUC¸O˜ES poucos alunos, digamos, 20 ou 30. Outro aspecto considerado foi o fato de que este me´todo na˜o exige nenhum conhecimento pre´vio de quem vai executar a operac¸a˜o, a na˜o ser saber contar. Tambe´m na˜o 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˜o pode ser insatisfato´rio. Para piorar, quanto maior o nu´mero, maior a chance de aparecerem erros na contagem. Foi discutida a adequac¸a˜o desta soluc¸a˜o para se contar os presentes em um comı´cio ou manifestac¸a˜o popular numa prac¸a pu´blica. Concluiu-se pela