apostila

Algoritmos e Estruturas de Dados I
Marcos Castilho Fabiano Silva Daniel Weingaertner
Versa\u2dco 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\u2dco-Uso
Na\u2dco-Comercial-Vedada a Criac¸a\u2dco 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\u2dco-Uso Na\u2dco-Comercial-
Vedada a Criac¸a\u2dco 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\u2dco.
Suma´rio
1 Introduc¸a\u2dco 7
2 Sobre problemas e soluc¸o\u2dces 9
2.1 Contando o nu´mero de presentes em um evento . . . . . . . . . . . . . 9
2.2 Trocando os quatro pneus . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Conclusa\u2dco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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´\u131cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4 O modelo do computador 21
4.1 Histo´rico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 Princ´\u131pios do modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2.1 Enderec¸os versus conteu´dos . . . . . . . . . . . . . . . . . . . . 22
4.2.2 O reperto´rio de instruc¸o\u2dces . . . . . . . . . . . . . . . . . . . . . 23
4.2.3 O ciclo de execuc¸a\u2dco de instruc¸o\u2dces . . . . . . . . . . . . . . . . . 25
4.2.4 Exemplo de execuc¸a\u2dco de um programa . . . . . . . . . . . . . . 25
4.3 Humanos versus computadores . . . . . . . . . . . . . . . . . . . . . . . 26
4.3.1 Abstrac¸a\u2dco dos enderec¸os . . . . . . . . . . . . . . . . . . . . . . 27
4.3.2 Abstrac¸a\u2dco dos co´digos das instruc¸o\u2dces . . . . . . . . . . . . . . . 28
4.3.3 Abstrac¸a\u2dco do reperto´rio de instruc¸o\u2dces . . . . . . . . . . . . . . . 29
4.3.4 Abstrac¸a\u2dco dos enderec¸os de memo´ria (varia´veis) . . . . . . . . . 30
4.4 Abstrac¸a\u2dco das instruc¸o\u2dces (linguagem) . . . . . . . . . . . . . . . . . . . 31
4.5 Conclusa\u2dco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.6 Exerc´\u131cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5 Conceitos elementares 37
5.1 Algoritmos e linguagens de programac¸a\u2dco . . . . . . . . . . . . . . . . . 37
5.2 Ca´lculo de ra´\u131zes de uma equac¸a\u2dco do segundo grau . . . . . . . . . . . 38
5.3 Imprimir a soma de dois nu´meros dados . . . . . . . . . . . . . . . . . 39
5.4 Imprimindo seque\u2c6ncias 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\u2c6ndice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.10 Exerc´\u131cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6 Te´cnicas elementares 55
6.1 Atribuic¸o\u2dces dentro de repetic¸o\u2dces . . . . . . . . . . . . . . . . . . . . . . 55
6.1.1 Somando nu´meros . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.2 Desvios condicionais aninhados . . . . . . . . . . . . . . . . . . . . . . 57
6.2.1 O menor de tre\u2c6s . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6.3 Desvios condicionais dentro de repetic¸o\u2dces . . . . . . . . . . . . . . . . . 58
6.3.1 Imprimir apenas nu´meros positivos . . . . . . . . . . . . . . . . 58
6.3.2 Somando pares e \u131´mpares . . . . . . . . . . . . . . . . . . . . . . 61
6.3.3 Convertendo para bina´rio . . . . . . . . . . . . . . . . . . . . . 62
6.3.4 Menor de 3, segunda versa\u2dco . . . . . . . . . . . . . . . . . . . . 64
6.4 Repetic¸o\u2dces dentro de condic¸o\u2dces . . . . . . . . . . . . . . . . . . . . . . 65
6.4.1 Calculo do MDC . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.5 Repetic¸o\u2dces aninhadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.5.1 Tabuada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.5.2 Fatorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.6 Exerc´\u131cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
7 Aplicac¸o\u2dces 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´\u131cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
8 Refinamentos sucessivos 91
8.1 Primos entre si . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
8.2 Amigos quadra´ticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
8.3 Pal´\u131ndromos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
8.4 Inverter um nu´mero de tre\u2c6s d´\u131gitos . . . . . . . . . . . . . . . . . . . . 99
8.5 Ca´lculo do MDC pela definic¸a\u2dco . . . . . . . . . . . . . . . . . . . . . . 101
8.6 Exerc´\u131cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
9 Func¸o\u2dces e procedimentos 107
9.1 Motivac¸a\u2dco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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\u2dces 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\u2dces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
9.2.5 Para\u2c6metros por valor . . . . . . . . . . . . . . . . . . . . . . . . 112
9.2.6 Para\u2c6metros por refere\u2c6ncia . . . . . . . . . . . . . . . . . . . . . 113
9.2.7 Procedimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
9.2.8 Varia´veis locais . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
9.3 Alguns exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
9.3.1 Calculando d´\u131gito verificador . . . . . . . . . . . . . . . . . . . . 116
9.4 Ca´lculo do MDC pela definic¸a\u2dco . . . . . . . . . . . . . . . . . . . . . . 119
9.4.1 Calculando ra´\u131zes de equac¸o\u2dces do segundo grau . . . . . . . . . 121
9.5 Exerc´\u131cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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\u2dco em vetores . . . . . . . . . . . . . . . . . . . . . . . 148
10.1.5 Outros algoritmos com vetores . . . . . . . . . . . . . . . . . . . 152
10.1.6 Exerc´\u131cios . . . . . . . . .