apostila

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 . . . . . . . . .