apostila
Pré-visualização50 páginas
Algoritmos e Estruturas de Dados I Marcos Castilho Fabiano Silva Daniel Weingaertner Versa˜o 0.7 Maio de 2011 2 Algoritmos e Estruturas de Dados I - Notas de Aula esta´ licen- ciado segundo a licenc¸a da Creative Commons Atribuic¸a˜o-Uso Na˜o-Comercial-Vedada a Criac¸a˜o de Obras Derivadas 2.5 Bra- sil License.http://creativecommons.org/licenses/by-nc-nd/ 2.5/br/ Algoritmos e Estruturas de Dados I - Notas de Aula is licen- sed under a Creative Commons Atribuic¸a˜o-Uso Na˜o-Comercial- Vedada a Criac¸a˜o de Obras Derivadas 2.5 Brasil License.http: //creativecommons.org/licenses/by-nc-nd/2.5/br/ AVISO: Este texto ainda esta´ em construc¸a˜o. Suma´rio 1 Introduc¸a˜o 7 2 Sobre problemas e soluc¸o˜es 9 2.1 Contando o nu´mero de presentes em um evento . . . . . . . . . . . . . 9 2.2 Trocando os quatro pneus . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Conclusa˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3 Sobre algoritmos e programas 15 3.1 O que e´ um algoritmo? . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 O que e´ um programa? . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4 O modelo do computador 21 4.1 Histo´rico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 Princ´ıpios do modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2.1 Enderec¸os versus conteu´dos . . . . . . . . . . . . . . . . . . . . 22 4.2.2 O reperto´rio de instruc¸o˜es . . . . . . . . . . . . . . . . . . . . . 23 4.2.3 O ciclo de execuc¸a˜o de instruc¸o˜es . . . . . . . . . . . . . . . . . 25 4.2.4 Exemplo de execuc¸a˜o de um programa . . . . . . . . . . . . . . 25 4.3 Humanos versus computadores . . . . . . . . . . . . . . . . . . . . . . . 26 4.3.1 Abstrac¸a˜o dos enderec¸os . . . . . . . . . . . . . . . . . . . . . . 27 4.3.2 Abstrac¸a˜o dos co´digos das instruc¸o˜es . . . . . . . . . . . . . . . 28 4.3.3 Abstrac¸a˜o do reperto´rio de instruc¸o˜es . . . . . . . . . . . . . . . 29 4.3.4 Abstrac¸a˜o dos enderec¸os de memo´ria (varia´veis) . . . . . . . . . 30 4.4 Abstrac¸a˜o das instruc¸o˜es (linguagem) . . . . . . . . . . . . . . . . . . . 31 4.5 Conclusa˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.6 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5 Conceitos elementares 37 5.1 Algoritmos e linguagens de programac¸a˜o . . . . . . . . . . . . . . . . . 37 5.2 Ca´lculo de ra´ızes de uma equac¸a˜o do segundo grau . . . . . . . . . . . 38 5.3 Imprimir a soma de dois nu´meros dados . . . . . . . . . . . . . . . . . 39 5.4 Imprimindo sequeˆncias de nu´meros na tela . . . . . . . . . . . . . . . . 40 5.5 Imprimir os quadrados de uma faixa de nu´meros . . . . . . . . . . . . . 44 5.6 Imprimindo a soma de va´rios pares de nu´meros . . . . . . . . . . . . . 44 3 4 SUMA´RIO 5.7 Testar se um nu´mero lido e´ positivo . . . . . . . . . . . . . . . . . . . . 45 5.8 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.9 Apeˆndice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.10 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 6 Te´cnicas elementares 55 6.1 Atribuic¸o˜es dentro de repetic¸o˜es . . . . . . . . . . . . . . . . . . . . . . 55 6.1.1 Somando nu´meros . . . . . . . . . . . . . . . . . . . . . . . . . 55 6.2 Desvios condicionais aninhados . . . . . . . . . . . . . . . . . . . . . . 57 6.2.1 O menor de treˆs . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 6.3 Desvios condicionais dentro de repetic¸o˜es . . . . . . . . . . . . . . . . . 58 6.3.1 Imprimir apenas nu´meros positivos . . . . . . . . . . . . . . . . 58 6.3.2 Somando pares e ı´mpares . . . . . . . . . . . . . . . . . . . . . . 61 6.3.3 Convertendo para bina´rio . . . . . . . . . . . . . . . . . . . . . 62 6.3.4 Menor de 3, segunda versa˜o . . . . . . . . . . . . . . . . . . . . 64 6.4 Repetic¸o˜es dentro de condic¸o˜es . . . . . . . . . . . . . . . . . . . . . . 65 6.4.1 Calculo do MDC . . . . . . . . . . . . . . . . . . . . . . . . . . 65 6.5 Repetic¸o˜es aninhadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.5.1 Tabuada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.5.2 Fatorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 6.6 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 7 Aplicac¸o˜es das te´cnicas elementares 75 7.1 Nu´meros de Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 7.2 Maior segmento crescente . . . . . . . . . . . . . . . . . . . . . . . . . 77 7.3 Se´ries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 7.3.1 Nu´mero neperiano . . . . . . . . . . . . . . . . . . . . . . . . . 79 7.3.2 Ca´lculo do seno . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 7.4 Nu´meros primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 7.5 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 8 Refinamentos sucessivos 91 8.1 Primos entre si . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 8.2 Amigos quadra´ticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 8.3 Pal´ındromos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 8.4 Inverter um nu´mero de treˆs d´ıgitos . . . . . . . . . . . . . . . . . . . . 99 8.5 Ca´lculo do MDC pela definic¸a˜o . . . . . . . . . . . . . . . . . . . . . . 101 8.6 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 9 Func¸o˜es e procedimentos 107 9.1 Motivac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 9.1.1 Modularidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 9.1.2 Reaproveitamento de co´digo . . . . . . . . . . . . . . . . . . . . 108 9.1.3 Legibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 9.1.4 Comenta´rio adicional . . . . . . . . . . . . . . . . . . . . . . . . 109 9.2 Noc¸o˜es fundamentais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 SUMA´RIO 5 9.2.1 Exemplo ba´sico . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 9.2.2 O programa principal . . . . . . . . . . . . . . . . . . . . . . . . 109 9.2.3 Varia´veis globais . . . . . . . . . . . . . . . . . . . . . . . . . . 110 9.2.4 Func¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 9.2.5 Paraˆmetros por valor . . . . . . . . . . . . . . . . . . . . . . . . 112 9.2.6 Paraˆmetros por refereˆncia . . . . . . . . . . . . . . . . . . . . . 113 9.2.7 Procedimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 9.2.8 Varia´veis locais . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 9.3 Alguns exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 9.3.1 Calculando d´ıgito verificador . . . . . . . . . . . . . . . . . . . . 116 9.4 Ca´lculo do MDC pela definic¸a˜o . . . . . . . . . . . . . . . . . . . . . . 119 9.4.1 Calculando ra´ızes de equac¸o˜es do segundo grau . . . . . . . . . 121 9.5 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 10 Estruturas de dados 125 10.1 Vetores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 10.1.1 Primeiros problemas com vetores . . . . . . . . . . . . . . . . . 128 10.1.2 Soma e produto escalar de vetores . . . . . . . . . . . . . . . . . 136 10.1.3 Busca em vetores . . . . . . . . . . . . . . . . . . . . . . . . . . 138 10.1.4 Ordenac¸a˜o em vetores . . . . . . . . . . . . . . . . . . . . . . . 148 10.1.5 Outros algoritmos com vetores . . . . . . . . . . . . . . . . . . . 152 10.1.6 Exerc´ıcios . . . . . . . . .