Algoritmos IFET
139 pág.

Algoritmos IFET


DisciplinaEngenharia Mecatrônica89 materiais1.261 seguidores
Pré-visualização27 páginas
Bidimensionais . . . . . . . . . . . . . . . . . . . . 91
5.2.1 Percorrimento de Matriz em C . . . . . . . . . . . . . . . . . . . . . 92
5.2.2 Inicializac¸a\u2dco de Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.2.3 Atribuic¸a\u2dco de Valor aos Elementos de uma Matriz . . . . . . . . . . 93
6 Cadeias de Caracteres 97
6.1 Cadeias de Caracteres em C . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.2 Entrada de cadeias de caracteres . . . . . . . . . . . . . . . . . . . . . . . . 100
6.3 Conversa\u2dco de Cadeias de Caracteres em Tipos Nume´ricos . . . . . . . . . . 104
6.4 Func¸o\u2dces de C para Cadeias de Caracteres . . . . . . . . . . . . . . . . . . . 106
6.4.1 Co´pia de Cadeias de Caracteres . . . . . . . . . . . . . . . . . . . . . 107
6.4.2 Tamanho de Cadeias de Caracteres . . . . . . . . . . . . . . . . . . . 108
6.4.3 Concatenac¸a\u2dco de Cadeias de Caracteres . . . . . . . . . . . . . . . . 109
6.4.4 Comparac¸a\u2dco de Cadeias de Caracteres . . . . . . . . . . . . . . . . . 110
6.4.5 Pesquisa em uma Cadeia de Caracteres . . . . . . . . . . . . . . . . 111
6.5 Vetor de Cadeias de Caracteres . . . . . . . . . . . . . . . . . . . . . . . . . 113
SUMA´RIO v
7 Func¸o\u2dces 117
7.1 Modularizac¸a\u2dco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
7.2 Argumentos de Entrada e Tipos de Retorno . . . . . . . . . . . . . . . . . . 120
7.3 Func¸o\u2dces e Estruturas Homoge\u2c6neas . . . . . . . . . . . . . . . . . . . . . . . 123
7.4 Func¸o\u2dces e Cadeias de Caracteres . . . . . . . . . . . . . . . . . . . . . . . . 126
7.5 Tipos Especiais de Varia´veis . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
7.5.1 Varia´veis Globais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
7.5.2 Varia´veis Esta´ticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
7.6 Recursividade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
7.7 Bibliotecas de Func¸o\u2dces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
vi SUMA´RIO
Prefa´cio
Notas de aula da disciplina Algoritmos ministrada aos alunos do curso de Engenharia
Mecatro\u2c6nica do IFET Sudeste MG campus Juiz de Fora.
1
2 SUMA´RIO
Cap´\u131tulo 1
Introduc¸a\u2dco aos Algoritmos
Na\u2dco se pode criar experie\u2c6ncia. E´ preciso passar por ela. \u2013 Albert Einstein
1.1 Introduc¸a\u2dco a` Organizac¸a\u2dco de Computadores
1.1.1 Modelo de von Neumann
O modelo lo´gico de computador proposto por von Neumann pode ser descrito pela Fi-
gura 1.1.
Figura 1.1: Modelo de Arquitetura de von Neumann
\u2022 Unidade de controle: a unidade de controle controla o funcionamento da uni-
dade lo´gica e aritme´tica e da memo´ria. Ale´m disso, ela distribui e organiza tarefas,
3
4 CAPI´TULO 1. INTRODUC¸A\u2dcO AOS ALGORITMOS
transfere informac¸o\u2dces da entrada para a memo´ria e da memo´ria para a sa´\u131da.
\u2022 Memo´ria: a memo´ria e´ o dispositivo de armazenamento de informac¸a\u2dco do compu-
tador. Nela sa\u2dco armazenados tanto as instruc¸o\u2dces de um programa quanto os dados
necessa´rios para a sua execuc¸a\u2dco. A memo´ria e´ dividida em espac¸os com enderec¸os.
\u2022 Unidades de entrada e sa´\u131da: a unidade de entrada traduz informac¸a\u2dco (por
exemplo, letras, nu´meros, imagens, marcas magne´ticas) de uma variedade de dispo-
sitivos de entrada em impulsos ele´tricos que a CPU entenda. A unidade de sa´\u131da
traduz os dados processados, enviados pela CPU em forma de impulsos ele´tricos, em
palavras ou nu´meros, que sa\u2dco impressos por impressoras ou mostrados em monitores
de v´\u131deo.
1.1.2 Bases de Numerac¸a\u2dco
Por questo\u2dces de Engenharia (confiabilidade, menor consumo de energia, menor dissipac¸a\u2dco
de calor), os computadores utilizam a base nume´rica bina´ria (d´\u131gitos 0 e 1) em lugar da
base nume´rica decimal (d´\u131gitos 0 e 9).
Outras bases nume´ricas tambe´m utilizadas em Cie\u2c6ncia da Computac¸a\u2dco sa\u2dco a octal
(d´\u131gitos 0 a 7) e hexadecimal (d´\u131gitos 0 a 9 e A a F). Isso se deve a` fa´cil conversa\u2dco entre a
base bina´ria e as bases octal e hexadecimal associado a` uma representac¸a\u2dco mais concisa e
intelig´\u131vel (Figura 1.2).
Cada 4 d´\u131gitos em um nu´mero na representac¸a\u2dco bina´ria corresponde a um nu´mero
na representac¸a\u2dco hexadecimal. Por exemplo, (101111001101)2 = (BCD)16 e (13A)16 =
(000100111010)2.
Analogamente, cada 3 d´\u131gitos bina´rios correspondem a um d´\u131gito octal. Por exemplo,
(101111001101)2 = (5715)8. Em decimal, 5× 83 + 7× 82 + 1× 81 + 5× 80 = (3021)10.
1.1.3 Bit
Bit (simplificac¸a\u2dco para d´\u131gito bina´rio, BInary digiT em ingle\u2c6s) e´ a menor unidade de
informac¸a\u2dco que pode ser codificada e manipulada em um computador digital. Um bit tem
um u´nico valor, 0 ou 1, ou verdadeiro ou falso, ou neste contexto, quaisquer dois valores
mutuamente exclusivos.
Fisicamente, o valor de um bit e´ armazenado como uma carga ele´trica acima ou
abaixo de um n´\u131vel padra\u2dco em um u´nico capacitor dentro de um dispositivo de memo´ria.
Mas, bits podem ser representados fisicamente por va´rios meios: luz (em fibras o´ticas),
ondas eletromagne´ticas (rede wireless), polarizac¸a\u2dco magne´tica (discos r´\u131gidos).
1.1. INTRODUC¸A\u2dcO A` ORGANIZAC¸A\u2dcO DE COMPUTADORES 5
Figura 1.2: Bases de Numerac¸a\u2dco utilizadas em Computac¸a\u2dco
1.1.4 Byte
Denomina-se byte (contrac¸a\u2dco de BinarY term) a` unidade ba´sica de tratamento de in-
formac¸a\u2dco em computadores digitais. Por padronizac¸a\u2dco de mercado, 1 byte equivale a 8
bits cont´\u131guos. A primeira codificac¸a\u2dco de 1 byte = 8 bits deveu-se a` empresa IBM em
1960 com a criac¸a\u2dco da tabela ASCII.
Como cada bit pode conter 2 valores bina´rios diferentes, 1 byte (8 bits) pode re-
presentar 256 valores nume´ricos distintos na base 2. A Tabela 1.1 apresenta os valores
m\u131´nimo e ma´ximo que podem ser armazenados em 1 byte.
Tabela 1.1: Valores m\u131´nimo e ma´ximo em 1 byte
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
1× 27 + 1× 26 + 1× 25 + 1× 24 + 1× 23 + 1× 22 + 1× 21 + 1× 20 = 255
Cada byte pode armazenar um caractere (letra, nu´mero ou s´\u131mbolo), de acordo com
alguma tabela de codificac¸a\u2dco.
6 CAPI´TULO 1. INTRODUC¸A\u2dcO AOS ALGORITMOS
1.1.5 Codificac¸a\u2dco ASCII
ASCII (acro\u2c6nimo para American Standard Code for Information Interchange, que em
portugue\u2c6s significa \u201cCo´digo Padra\u2dco Americano para o Interca\u2c6mbio de Informac¸a\u2dco\u201d) e´
uma codificac¸a\u2dco de caracteres de oito bits criado pela IBM. Originalmente ASCII usava
apenas 7 bits (capaz de representar 128 caracteres) mas posteriormente estendeu-se para 8
bits para suportar os caracteres acentuados usados em diversos idiomas como o portugue\u2c6s.
A Figura 1.3 apresenta a codificac¸a\u2dco ASCII para os principais caracteres imprim\u131´veis
dos idiomas ocidentais.
1.1.6 Grandezas Derivadas do Byte
Uma vez que os computadores utilizam aritme´tica bina´ria (base 2), os valores nume´ricos
sa\u2dco expressos em pote\u2c6ncias de dois e na\u2dco em pote\u2c6ncias de dez, embora sejam usados os
mesmos nomes para os mu´ltiplos.
Assim, 1 quilobyte (KB) equivale a 210 bytes = 1.024 bytes, 1 megabyte (MB) equi-
vale a 220 bytes = 1.048.576 bytes e 1 gigabyte (GB) equivale a 230 bytes = 1.073.741.824
bytes.
1.1.7 Palavra
Uma palavra (word) e´ um valor fixo para um determinado processador. Assim, um Pen-
tium possui uma palavra de 32 bits. Isso significa que 1 palavra de 32 bits sa\u2dco processados
por vez nesse processador e indica a sua capacidade de processamento.
1.2 Memo´ria
Memo´ria e´ o componente de um computador cuja func¸a\u2dco e´ armazenar informac¸o\u2dces a serem
manipuladas pelo sistema. A Figura 1.4 apresenta uma analogia entre uma memo´ria de
computador e um arquivo de fichas em uma empresa.
Na realidade, existem diversos tipos de memo´ria em um computador:
\u2022 Memo´ria principal: (memo´ria RAM Random Access Memory Memo´ria de Aceso
Rando\u2c6mico).
\u2022 Memo´ria cache: constru´\u131da com tecnologia RAM, inserida entre a UCP e a
memo´ria principal.
\u2022 Registradores: dispositivos de armazenamento existentes no interior dos processa-
dores, com o objetivo de conter os dados, instruc¸o\u2dces e enderec¸os de memo´ria RAM
a serem processados pela UCP.
1.2. MEMO´RIA 7