Introdução à Programação
Série
Didáctica
CIÊNCIAS APLICADAS
226
Manuel José Cabral dos Santos Reis
António Jorge Gonçalves de Gouveia
Francisco de Sousa Pereira
Universidade de Trás-os-Montes e Alto Douro
Vila Real
Índice
1 – Motivação........................................................................................................................... 11
2 – Breve História dos computadores ...................................................................................... 15
3 – Sistemas de numeração ...................................................................................................... 17
3.1 – Conversão directa entra as bases 2, 8, 16. ................................................................... 21
3.1.1 – Conversão de binário para octal/hexadecimal...................................................... 22
3.1.2 – Conversão de octal/hexadecimal para binário...................................................... 22
4 – Sistemas informáticos ........................................................................................................ 25
4.1 – Classificação segundo gerações de computadores ...................................................... 26
4.2 – Classificação quanto ao tamanho ou à “capacidade” do computador ......................... 27
4.3 – Classificação quanto ao número de utilizadores simultâneos ..................................... 29
4.4 – Principais componentes de um sistema informático ................................................... 31
4.4.1 – A placa principal ou motherboard........................................................................ 31
4.4.2 – O processador....................................................................................................... 32
4.4.3 – Memórias.............................................................................................................. 34
4.4.4 – O barramento ou bus de um sistema informático................................................. 37
4.4.5 – Ligações de periféricos ou dispositivos de I/O .................................................... 38
4.5 – Sistema Operativo ....................................................................................................... 46
5 – Algoritmos.......................................................................................................................... 49
5.1 – Noção de algoritmo ..................................................................................................... 51
5.2 – Dados e tipos de dados ................................................................................................ 52
5.3 – Operadores e operações básicas .................................................................................. 54
5.4 – Variáveis e expressões ................................................................................................ 55
5.5 – Entrada e saída de dados ............................................................................................. 57
5.6 – Funções embutidas ou pré-definidas ........................................................................... 57
6 – Estruturas de decisão.......................................................................................................... 59
6.1 – Selecção de acções alternativas – SE-ENTÃO-SENÃO............................................. 59
6.2 – SE’s encaixados........................................................................................................... 63
6.3 – Estrutura de selecção múltipla..................................................................................... 66
7 – Ciclos.................................................................................................................................. 71
7.1 – Estrutura REPETIR-ENQUANTO ............................................................................. 71
7.2 – Estrutura REPETIR-ATÉ............................................................................................ 74
7.3 – Entrada de dados através de ciclos.............................................................................. 78
7.4 – Ciclos contados ........................................................................................................... 79
8 – Subalgoritmos – funções e procedimentos......................................................................... 85
8.1 – Parâmetros e argumentos ............................................................................................ 85
8.2 – Tipos de passagem de parâmetros............................................................................... 86
8.3 – Funções........................................................................................................................ 87
8.4 – Procedimentos ............................................................................................................. 89
8.5 – Variáveis globais e variáveis locais ............................................................................ 90
8.6 – Subprogramas encaixados ........................................................................................... 92
9 – Vectores e matrizes ............................................................................................................ 95
9.1 – Arrays unidimensionais – Vectores............................................................................. 95
9.1.1 – Tratamento de strings ou cadeias de caracteres como arrays unidimensionais.. 101
9.2 – Arrays bidimensionais ou matrizes ........................................................................... 102
9.3 – Arrays multidimensionais ......................................................................................... 105
iii
10 – Pesquisa e ordenação com vectores ............................................................................... 107
10.1 – Ordenação ou classificação ..................................................................................... 107
10.1.1 – Ordenação por selecção.................................................................................... 107
10.1.2 – Ordenação por borbulhamento ......................................................................... 109
10.2 – Pesquisa................................................................................................................... 111
10.2.1 – Pesquisa linear.................................................................................................. 111
10.2.2 – Pesquisa binária................................................................................................ 112
11 – Registos e arrays de registos.......................................................................................... 115
11.1 – Arrays de registos.................................................................................................... 117
12 – Bibliografia..................................................................................................................... 121
iv
Índice de Figuras
Figura 1 – Exemplos de válvulas. ............................................................................................ 27
Figura 2 – Exemplos de transístores. ....................................................................................... 27
Figura 3 – Microprocessador Intel 4004. ................................................................................. 27
Figura 4 – Exemplos de processadores. ................................................................................... 27
Figura 5 – Computadores de pequeno, médio e grande porte. ................................................. 28
Figura 6 – Computador pessoal tipo secretária (desktop) “Indigo 223”. ................................. 28
Figura 7 – PC portátil. .............................................................................................................. 29
Figura 8 – Servidor de terminais. ............................................................................................. 30
Figura 9 – Rede de computadores. ........................................................................................... 30
Figura 10 – Computador típico. ............................................................................................... 31
Figura 11 – Motherboard típica. .............................................................................................. 31
Figura 12 – Fotografias de alguns processadores..................................................................... 32
Figura 13 – Constituição típica de um CPU e de um sistema informático. ............................. 33
Figura 14 – Memória primária tipo ROM................................................................................ 34
Figura 15 – Memória primária tipo RAM................................................................................ 35
Figura 16 – Memória secundária, auxiliar ou de armazenamento tipo disco rígido. ............... 35
Figura 17 – Organização da memória. ..................................................................................... 36
Figura 18 – Núcleo de memória de ferrite. .............................................................................. 36
Figura 19 – Superfície de um disco rígido de 20 Mbytes. ....................................................... 37
Figura 20 – Superfície de um CD com música dos “Bon Jovi”. .............................................. 37
Figura 21 – Sistema de computador típico. Note-se a presença de três tipos de bus............... 38
Figura 22 – Esquema simplificado do modo de funcionamento de um CRT. ......................... 39
Figura 23 – Exemplo de CRT policromático (cores). .............................................................. 40
Figura 24 – Exemplo de impressora “laser”............................................................................. 41
Figura 25 – Exemplo de impressora “jacto de tinta”. .............................................................. 42
Figura 26 – Exemplo de traçador gráfico tipo tambor. ............................................................ 42
Figura 27 – Exemplo de traçador gráfico tipo mesa. ............................................................... 43
Figura 28 – Exemplo de teclado, rato, painel táctil e lápis óptico. .......................................... 44
Figura 29 – Exemplo de mesa digitalizadora, joystick e trackball........................................... 44
Figura 30 – Exemplo de digitalizador 3D, spaceball e luva instrumentada............................. 45
Figura 31 – Exemplo de placa de som. .................................................................................... 45
Figura 32 – Exemplo de placa de rede. .................................................................................... 46
Figura 33 – Componentes principais de um sistema operativo................................................ 47
Figura 34 – Fases principais na resolução de um problema..................................................... 49
Figura 35 – Fases de desenvolvimento/teste de um algoritmo/programa. ............................... 50
Figura 36 – Tipos de dados. ..................................................................................................... 53
Figura 37 – Diagrama de fluxo da construção SE-ENTÃO-SENÃO. ..................................... 60
Figura 38 – Diagrama de fluxo da construção SE-ENTÃO..................................................... 60
Figura 39 – Diagrama de fluxo para determinação do maior de dois valores.......................... 61
Figura 40 – Diagrama de fluxo da estrutura REPETIR-ENQUANTO. ................................... 72
Figura 41 – Diagrama de fluxo da estrutura REPETIR-ATÉ. ................................................. 75
Figura 42 – Diagrama de fluxo para entrada de dados (lista não vazia). ................................. 79
Figura 43 – Diagrama de fluxo para entrada de dados (lista vazia). ........................................ 79
Figura 44 – Ilustração do processo de ‘passagem de controlo de fluxo ’. ............................... 85
Figura 45 – Interpretação gráfica de vector. ............................................................................ 96
v
Figura 46 – Interpretação geométrica de array bidimensional............................................... 102
vi
Índice de Tabelas
Tabela 1 – Representação dos números de 0 a 16 nas bases 2, 5, 8, 10 e 16. .......................... 18
Tabela 2 – Constituição básica de um sistema informático. .................................................... 25
Tabela 3 – Gerações de computadores..................................................................................... 26
Tabela 4 – Evolução de alguns parâmetros dos microprocessadores da família Intel. ............ 33
Tabela 5 – Tipos de memórias. ................................................................................................ 34
Tabela 6 – Exemplos de funções pré-definidas........................................................................ 58
vii
Índice de Ilustrações
Ilustração 1 – Classificação de computadores por tamanho/capacidade.................................. 28
Ilustração 2 – Classificação dos computadores quanto ao número de utilizadores. ................ 29
ix
1 – Motivação
Estes apontamentos surgem no âmbito da disciplina de Introdução à Programação (IP) do
1º ano, 2º semestre, do curso de Engenharia Electrotécnica da Universidade de Trás-osMontes e Alto Douro. Surgem na sequência da experiência adquirida pelos autores ao longo
destes últimos anos em que leccionaram os conteúdos aqui apresentados. Têm por principal
objectivo servir de base de estudo à referida disciplina. Estão divididos em duas partes, que se
relacionam directamente com a forma como a disciplina se encontra estruturada: nesta parte
(primeira) apresentam-se os conceitos, noções e técnicas para a resolução e implementação de
um dado algoritmo (componente teórica da disciplina); e numa segunda parte apresenta-se
uma lista de exercícios e as respectivas propostas de solução comentadas (componente prática
da disciplina). Esta segunda componente será publicada oportunamente.
Para além desta disciplina, que é a primeira disciplina do curso de Engenharia
Electrotécnica em que os alunos estabelecem contacto com as técnicas de programação de
computadores, o plano actual de estudos do curso contempla as seguintes disciplinas, cujos
assuntos aí tratados directa ou indirectamente se relacionam com os desta:
Algoritmos; 2º ano – 1º semestre;
Estruturas de Dados; 2º ano – 2º semestre;
Arquitectura de Computadores; 3º ano – 1º semestre;
Microprocessadores e Microcomputadores; 3º ano – 2º semestre;
Sistemas de Operação; 3º ano – 2º semestre;
Comunicação de Dados; 4º ano – 1º semestre;
Técnicas Avançadas de Computação; 4º ano – 2º semestre;
Redes de Computadores; 4º ano – 2º semestre;
Processamento Digital do Sinal; 4º ano – 2º semestre;
Telecomunicações; 4º ano – 2º semestre;
Algoritmos e Arquitecturas para PDS; 5º ano – 1º semestre;
Controlo Digital; 5º ano – 1º semestre;
11
Processamento Digital de Imagem; 5º ano – 1º semestre;
Computação Gráfica; 5º ano – 2º semestre;
Robótica; 5º ano – 2º semestre;
Projecto; 5º ano – anual.
As primeiras questões que se podem colocar são as seguintes: porquê utilizar
computadores?; e porquê aprender a programá-los? Obviamente que a resposta a estas duas
questões não é de forma alguma breve ou sucinta. Antes de mais convém ter presente o
âmbito em que elas são formuladas. Convém ainda esclarecer que o principal objectivo destas
questões é alertar o aluno para a necessidade da existência de tais competências (utilizar e
programar o computar). Assim passamos a listar algumas das áreas onde a informática foi
introduzida:
•
Na administração pública;
•
Em actividades empresariais;
•
No sistema educativo;
•
No sistema de saúde;
•
Na comunicação Social;
•
Etcetera.
Da mesma forma, os principais tipos de aplicações informáticas (programas) são:
•
Processamento de texto;
•
Edição electrónica;
•
Folhas de cálculo (e outros tipos de cálculo);
•
Bases de dados;
•
Desenho, Computer Aided Design – CAD;
•
Acesso à Internet e utilização dos seus serviços (browsers, clientes de e-mail, etc.);
•
Modelação e simulação computacional;
•
Inteligência artificial;
•
Etcetera.Resumindo, com o advento do computador e dos sistemas informáticos em
particular, passamos a ter:
•
Um elevado poder de cálculo dos computadores (maior capacidade e velocidade de
processamento);
12
•
Uma melhoria na qualidade da documentação produzida (por exemplo em termos de
CAD, Processamento de texto, Gráficos);
•
Ferramentas específicas para a Engenharia Electrotécnica (o que implica maior
competência e produtividade);
•
Facilidade de comunicação (E-mail, Internet, videoconferência, etc.);
•
Acesso à informação (Multimédia, CD-ROM, DVD, www, etc.).
O programa da disciplina pretende cobrir um conjunto de noções, técnicas e conceitos
que estejam de acordo com o nome e o tipo da disciplina, ou seja, com a introdução à
programação. Por este motivo não abordaremos conceitos como os de reutilização de código,
optimização, entre outros.
Muitas das figuras e tabelas aqui apresentadas não são de forma alguma originais,
resultando na sua grande maioria da digitalização directa de imagens dos livros, cujas
referências se juntam no final, e do resultado de pesquisas efectuadas na Internet.
13
2 – Breve História dos computadores
Tal como se pode depreender do título desta secção, não é nosso objectivo indicar de
forma exaustiva qualquer História dos computadores. É apenas pretendido fazer um
enquadramento histórico e introduzir a noção de que os computadores sofreram e sofrem um
processo de evolução continuado. Indicaremos apenas algumas das datas e factos que
consideramos como marcos na História da evolução dos computadores.
As primeiras ferramentas de cálculo surgiram na Babilónia, cerca de 3000 AC, e são
conhecidos por Ábacos. Em 1622, em Inglaterra, William Oughtred desenvolve a régua de
cálculo. Mais tarde em França (1642), Blaise PASCAL constrói a primeira máquina de
cálculo numérico.
A primeira máquina à qual podemos dar o nome de computador foi desenhada por
Charles Babbage em 1833, designada por Máquina Analítica, e recebe instruções a partir de
cartões perfurados.
O primeiro computador electrónico foi concluído em 1946 na Universidade da
Pensilvânia. Com o nome de ENIAC (Electronic Numerical Integrator and Computer)
possuía 18000 válvulas electrónicas, media 3 x 30 metros e pesava cerca 80 toneladas.
Realizava 5000 adições e 360 multiplicações por segundo.
Em 1975 o MITS desenvolve o primeiro computador pessoal, o Altair. Baseado no
microprocessador 8080 da INTEL, incluía 256 bytes de memória.
A IBM desenvolve o IBM PC em 1981. Possuía 64 Kbyte de memória RAM, uma drive
de floppy disk e um monitor monocromático. O seu sistema operativo era o MS-DOS,
desenvolvido por uma pequena empresa chamada Microsoft.
A Apple anuncia o seu Macintosh em 1984.
Da mesma forma, os microprocessadores sofreram uma forte evolução ao longo das
últimas décadas. O primeiro microprocessador, o 4004, surge em 1971 e foi desenvolvido
pela INTEL. Possuía 2300 transístores, trabalhava a uma frequência de 108 KHz e processava
informação de 4 bits. Em 1997 a INTEL lançou o Pentium II que possuia 7,5 milhões de
transístores e podia funcionar a velocidades de até 450 MHz. Em 2003 a INTEL possui
processadores Pentium 4, que funcionam a frequências superiores a 3 GHz e possuem mais de
15
100 milhões de transístores. Este processador possui um bus de endereços de 36 bits, um bus
de dados de 64 bits, o tamanho dos registos é de 32 bits e dois níveis de memória cache.
O primeiro sistema operativo foi desenvolvido em 1954 por Gene Amdahl sendo
utilizado no IBM 704. Em 1970 Ken Thompson e Dennis Ritchie desenvolvem o UNIX. Em
1981 a Microsoft desenvolve o MS-DOS para o IBM PC e em 1990 apresenta o Windows 3.0.
O ENIAC era programado, modificando ligações eléctricas entre os diversos
componentes! A primeira linguagem de programação foi desenvolvida por John Backus em
1954 para a IBM, sendo denominada de FORTRAN. Em 1964, Tom Kurtz e John Kemeny,
desenvolvem o BASIC (Beginners All-purpose Symbolic Instruction Code). Em 1969,
Nicklaus Wirth, escreve o primeiro compilador de PASCAL.
16
3 – Sistemas de numeração
O processamento de toda a informação num sistema informático é feito na base digital ou
binária; esta base de representação numérica é constituída por dois símbolos apenas: 0 (zero)
e 1 (um).
Em termos eléctricos, geralmente o 0 é representado por um nível de tensão baixo e o 1
por um nível de tensão alto. Todos os dispositivos ou circuitos digitais se regem por esta
regra, desde o processador à memória, passando pelos discos, etcetera.
A unidade mínima de representação é designada por BIT (BInary digiT). Um bit possui
pois o valor 0 ou 1. A um grupo de 8 bits dá-se o nome de byte; 1024 (210) bytes designam um
Kilo byte (Kbyte); 1024 Kbytes designam um Mega byte (Mbyte); 1024 Mbytes designam um
Giga byte (Gbyte); 1024 Gbytes designam um Tera byte (Tbyte); etcetera. Actualmente
existem autores que atribuem à unidade K o valor de 1000 (K = 100) e à unidade Ki o valor
1024 (Ki = 1024).
O homem utiliza o sistema de numeração decimal, base 10, devido ao facto de possuir
dez dedos nas mãos. Isto obriga à conversão de dados Decimal/Binário (à entrada) e
Binário/Decimal (à saída), de forma a tornar viável a utilização de computadores.
Numa base b de um sistema de numeração, define-se o conjunto de b símbolos para
representar cada valor. Por exemplo,
•
A base 10 é composta 0, 1, 2, 3, 4, 5, 6, 7, 8, 9;
•
A base 2 é composta
0, 1;
•
A base 5 é composta
0, 1, 2, 3, 4;
•
A base 16 é composta 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F;
•
A base b é composta
0, 1, ..., (b -1).
A representação de um número na própria base é sempre ‘10’, uma vez que uma base b só é
composta pelos símbolos de 0 a b–1. Por exemplo,
•
2 na base 2 = 10;
•
5 na base 5 = 10;
17
•
10 na base 10 = 10;
•
16 na base 16 = 10.
n
Utilizando um conjunto de n dígitos numa dada base b, podemos ter b valores diferentes que
n
vão desde 0 a b –1. Como exemplos temos,
•
base 10 com 3 dígitos à 0 ... 999 (103 à 1000 valores);
•
base 2 com 8 dígitos à 0 ... 255 (28 à 256 valores);
•
base 3 com 4 dígitos à 0 ... 80 (34 à 81 valores).
Base 2
Base 5
Base 8
Base 10
Base 16
00000
0
0
0
0
00001
1
1
1
1
00010
2
2
2
2
00011
3
3
3
3
00100
4
4
4
4
00101
10
5
5
5
00110
11
6
6
6
00111
12
7
7
7
01000
13
10
8
8
01001
14
11
9
9
01010
20
12
10
A
01011
21
13
11
B
01100
22
14
12
C
01101
23
15
13
D
01110
24
16
14
E
01111
30
17
15
F
10000
31
20
16
10
Tabela 1 – Representação dos números de 0 a 16 nas bases 2, 5, 8, 10 e 16.
A Tabela 1 mostra-nos as representações dos números de 0 a 16 representados nas bases 2, 5,
8, 10 e 16.
18
Na representação de um número numa dada base, os dígitos possuem, para além do seu
valor absoluto, um valor posicional que define o seu peso. Na sua forma mais genérica, um
número N é composto por uma parte inteira e uma parte decimal ou fraccionária:
N = dn-1 dn-2 … d1 d0 , d-1 d-2 … d-p
parte inteira
parte decimal
Uma sucessão de dígitos designa um número igual à soma dos valores posicionados dos
respectivos dígitos:
n-1
Nb = dn-1 x b
n-2
+ dn-2 x b
-p+1
1
0
-1
-2
+ … + d1 x b + d0 x b + d-1 x b + d-2 x b + …
-p
+ d-p x b .
+ d-p+1 x b
Veja-se o caso concreto do número 1998,35 representado na base 10:
3
2
1
0
-1
-2
N10 = 1998,35 = 1 x 10 + 9 x 10 + 9 x 10 + 8 x 10 + 3 x 10 + 5 x 10 .
Na conversão de uma base b para uma base b’ devemos ter em atenção que a aritmética a
usar deve ser a da base destino. Contudo, a base que intervém directamente nos cálculos é a
de origem. Neste processo, multiplica-se o valor absoluto do digito pelo peso que possui na
representação do número, isto é, pela base elevada à posição do digito
Nb = dn-1 dn-2 … d1 d0 , d-1 d-2 … d-p
Nb' = dn-1 x bn-1 + dn-2 x bn-2 + … + d1 x b1 + d0 x b0 + d-1 x b-1 + d-2 x b-2 + …
-p+1
-p
+ d-p x b .
+ d-p+1 x b
Vejamos um exemplo. Suponhamos que possuíamos o número 110,11 representado na base 2
e pretendíamos saber a sua representação equivalente na base 10:
N2 = 110,11 à N10 ?
2
1
0
-1
-2
N10 = 1 x 2 + 1 x 2 + 0 x 2 + 1 x 2 + 1 x 2 = 6,75.
Outro exemplo. Pretende-se saber a representação do número 132 escrito na base 4 na sua
equivalente da base 5:
N4 = 132 à N5 ?
2
1
0
N5 = 1 x 4 + 3 x 4 + 2 x 4 = 31 + 22 + 2 = 103 + 2 = 110.
19
Note-se que 42=1610 e 3 x 4 = 1210. Agora, recorrendo à Tabela 1 para ajuda na representação
dos valores intermédios e atenção que a aritmética utilizada é a da base 5, facilmente se chega
ao resultado apresentado.
A conversão de uma base b para a base 10 é mais apetecível do que qualquer outra, uma
vez que a aritmética a utilizar é a da base 10, isto é, aquela em que estamos habituados a fazer
cálculo desde crianças. Comparem-se os dois exemplos visto acima. Vejamos mais dois
exemplos:
N2 = 1010,011 à N10 ?
3
2
1
0
-1
-2
-3
N10 = 1 x 2 + 0 x 2 + 1 x 2 + 0 x 2 + 0 x 2 + 1 x 2 + 1 x 2 = 10,375.
N16 = ABC à N10 ?
2
1
0
N10 = 10 x 16 + 11 x 16 + 12 x 16 = 2784 (uma vez mais recorremos à Tabela 1
para saber qual o correspondente decimal dos valores A, B e C).
Na conversão da base 10 para uma base b, separa-se a conversão da parte inteira do
número da parte decimal.
Na conversão da parte inteira, divide-se o número e os sucessivos quocientes pela base b,
guardando o resto de cada divisão, até atingir o quociente zero. A representação do número na
nova base é dada pela sequência invertida dos restos. Por exemplo, suponhamos que
pretendemos converter o número 10,375 no seu equivalente da base 2. Para isso começamos
por converter a parte inteira, isto é, o valor 10:
10 2
0
5 2
1
2 2
0
1 2
1
0
A parte inteira possui pois a representação 1010.
Para converter a parte fraccionária, multiplica-se sucessivamente o seu valor, e as partes
fraccionárias resultantes, depois de retiradas as partes inteiras, pela nova base até que a parte
fraccionária seja nula ou se tenha obtido uma “precisão conveniente”. Os sucessivos dígitos
20
inteiros assim obtidos formam a representação da parte fraccionária na nova base.
Solidifiquemos o algoritmo com a continuação da conversão do exemplo anterior (10,375):
0,375 x 2 = 0,75
0,75 x 2
= 1,5
0,5 x 2
= 1,0
isto é, a parte decimal vale 0,011. O resultado final é pois 1010,011.
A conversão da parte fraccionária é muitas vezes infinita, isto é, nunca se atinge zero no
processo das multiplicações sucessivas. Torna-se então necessário estabelecer um critério de
paragem. Este critério está relacionado com a capacidade de numeração ou de aproximação.
Admitindo para um número fraccionário na base b, um erro igual ao peso da posição p menos
significativa do número nessa base, bp, deve verificar-se para a posição menos significativa da
representação da nova base um erro b'p’ ≤ bp. Isto obriga a termos p' ≥ p x ln(b)/ln(b') para que
se mantenha uma aproximação equivalente. Veja-se um exemplo concreto. Suponhamos que
pretendíamos converter o número 0,468 escrito na base 10 para o seu equivalente na base 2.
Para isso devemos calcular p' ≥ 3 x ln(10)/ln(2) = 9,97 o que implica p' = 10 (não existe 0,97
de um dígito). O número 3 na expressão anterior é devido ao facto do número na base 10 estar
escrito com 3 casas decimais, o 10 do primeiro logaritmo neperiano é devido ao facto de
0,468 estar escrito na base 10 e o 2 no segundo logaritmo por ser a base na qual pretendemos
representar este número. Deixando os cálculos ao cuidado do aluno, o resultado final será pois
igual a 0,0111011111 (com a mesma aproximação).
Como conclusão podemos escrever que podemos utilizar a base 10 como intermediária
para converter um número de uma base b para uma base b’ e assim utilizar unicamente a
aritmética da base 10.
3.1 – Conversão directa entra as bases 2, 8, 16.
Repare-se que 23=8 e 24 = 16. É de esperar que exista alguma relação entre estas bases
que nos permita facilitar a conversão directa. O mesmo se poderia esperar de outras bases (por
exemplo as bases 3, 9 e 27). As conversões entre as bases 2, 8, e 16 estão de facto
simplificadas.
21
3.1.1 – Conversão de binário para octal/hexadecimal.
Decompõe-se o número a partir da vírgula, nos dois sentidos, em grupos de três/quatro
dígitos, completando-se com zeros à esquerda e à direita quando necessário. Depois, substituise cada um dos grupos formados pelo respectivo símbolo octal/hexadecimal.
Veja-se o seguinte exemplo. Com o número 11010010,1111 representado na base 2
construímos os grupos 011 010 010 à esquerda da vírgula e os grupos 111 100 à direita da
vírgula que possuem as representações 3, 2, 2, 7 e 4, respectivamente, na base 8 (veja-se a
Tabela 1). O resultado final será pois 322,74. De uma forma visual
N2 = 11010010,1111 à N8 ?
011 010 010 , 111 100
3
2
2 , 7
4
N8 = 322,74.
Dividindo agora o número em grupos de quatro, obtém-se a sua representação na base 16:
N2 = 11010010,1111 à N16 ?
1101 0010 , 1111
D
2 , F
N16 = D2,F.
3.1.2 – Conversão de octal/hexadecimal para binário.
Este é o processo inverso ao descrito no ponto anterior. Assim, substitui-se cada
algarismo octal/hexadecimal pela respectiva representação binária em três/quatro dígitos.
Vejamos os exemplos. Primeiro convertamos o número 346,15 escrito na base 8 ou octal para
a base 2:
N8 = 346,15 à N2 ?
3
4
6 , 1
5
011 100 110 , 001 101
N2 = 011100110,001101 = 11100110,001101.
22
Agora convertamos o número 2BD,C3 escrito na base 16 para a base 2:
N16 = 2BD,C3 à N2 ?
2
B
D , C
3
0010 1011 1101 , 1100 0011
N2 = 001010111101,11000011 = 1010111101,11000011.
23
4 – Sistemas informáticos
Os sistemas informáticos são constituídos por dois tipos de componentes: hardware –
parte física (componentes electrónicos, mecânicos e electromecânicos); e software – parte
lógica (programas). Veja-se a Tabela 2.
No hardware, geralmente distingue-se entre:
•
O computador, que inclui a unidade de processamento central – CPU;
•
Os periféricos, onde se incluem o teclado, o rato, o monitor, a impressora,
etcetera.
No software distingue-se geralmente entre:
•
Software de sistema, ou seja, o próprio sistema operativo;
•
Software de aplicação, onde se incluem os programas de computador, e.g.,
processamento de texto, folhas de cálculo, gestão de bases de dados, desenho,
tratamento de imagens, etcetera.
Software
De aplicação
Processadores de texto; bases de dados; CAD; etc.
De sistema
Sistema operativo
CPU
Hardware
Dispositivos
de saída
Dispositivos
de entrada
Memória
Tabela 2 – Constituição básica de um sistema informático.
Os sistemas informáticos podem classificar-se segundo várias características, sendo as
principais:
•
As sucessivas gerações de computadores;
•
O tamanho ou a “capacidade” do computador;
•
O número de utilizadores com que o sistema pode trabalhar simultaneamente.
25
4.1 – Classificação segundo gerações de computadores
No que se refere à classificação segundo gerações, até à data consideram-se quatro.
Os computadores da primeira geração surgiram por volta de 1945 e funcionavam a
válvulas, com dimensões e consumos gigantescos e reduzida capacidade de cálculo, à luz da
tecnologia actual.
Os da segunda geração surgiram por volta de 1955 e funcionavam com transístores,
possuindo dimensões e consumos mais reduzidos, havendo um aumento da capacidade de
cálculo. É nesta altura que surgem os primeiros sistemas operativos. Tem também início a sua
comercialização em meios empresariais.
A terceira geração surgiu por volta de 1965. Os computadores desta geração funcionavam
com chips – pequenas pastilhas de circuitos integrados (CIs) – e as dimensões e consumos
voltaram a cair, aumentando o poder de cálculo. Esta geração de computadores foi
comercializada em empresas e universidades.
A quarta geração surge por volta de 1970 e os computadores funcionam com
microprocessadores – processadores totalmente incluídos num chip graças às técnicas de Very
Large Scale Integration (VLSI). As suas dimensões são cada vez mais pequenas e os preços
cada vez mais baixos, conduzindo ao aparecimento dos computadores pessoais (Personal
Computers – PCs).
Há quem classifique os computadores actuais como computadores da quinta geração
(multiprocessamento ou processamento em paralelo, capacidade para funcionarem com
sistemas avançados de inteligência artificial – comunicação verbal, entre outras capacidades).
Na Tabela 3 apresenta-se um resumo desta classificação. Nas Figura 1, Figura 2, Figura 3 e
Figura 4 apresentam-se alguns exemplos dos componentes principais de um computador.
Geração
1ª
2ª
3ª
4ª
Período (aproximado)
1945-1955
1955-1965
1965-1970
1970-????
Característica principal
Válvulas
Transístores
Chips ou CIs
Microprocessadores
Tabela 3 – Gerações de computadores.
26
Escala
Milisegundo
Microsegundo
Nanosegundo
Picosegundo
Figura 1 – Exemplos de válvulas.
Figura 2 – Exemplos de transístores.
Figura 3 – Microprocessador Intel 4004.
Figura 4 – Exemplos de processadores.
4.2 – Classificação quanto ao tamanho ou à “capacidade” do computador
Quanto à classificação segundo o tamanho/capacidade, os computadores podem dividirse em grande porte, médio porte e pequeno porte. Os supercomputadores e mainframes
27
enquadram-se no primeiro grupo, os minicomputadores e workstations no segundo, e os
microcomputadores e ultramicrocomputadores no terceiro. Na Ilustração 1 apresenta-se um
resumo desta classificação. Nas Figura 5, Figura 6 e Figura 7 apresentam-se exemplos de
computadores.
Computadores
grande
porte
Supercomputadores
Mainframes
médio
porte
Minicomputadores
Workstations
pequeno
porte
Microcomputadores
Ultramicrocomputadores
Ilustração 1 – Classificação de computadores por tamanho/capacidade.
Figura 5 – Computadores de pequeno, médio e grande porte.
Figura 6 – Computador pessoal tipo secretária (desktop) “Indigo 223”.
28
Figura 7 – PC portátil.
4.3 – Classificação quanto ao número de utilizadores simultâneos
No que se refere ao número de utilizadores, pode considerar-se sistemas monoposto e
sistemas multiposto. Os primeiros podem ainda dividir-se em monoposto–monotarefa e
monoposto–multitarefa. Os segundos podem dividir-se em sistemas multiposto e redes de
computadores. Na Ilustração 2 resume-se esta classificação. Nas Figura 8 e Figura 9
apresentam-se dois exemplos de sistemas deste tipo.
Sistemas
monoposto
Monoposto – monotarefa
Monoposto – multitarefa
Sistemas
multiposto
Sistemas multiposto
Redes de computadores
Computadores
Ilustração 2 – Classificação dos computadores quanto ao número de utilizadores.
29
Figura 8 – Servidor de terminais.
Estações
de trabalho
Impressora
Servidor
Scanner
Estações
de trabalho
Figura 9 – Rede de computadores.
30
4.4 – Principais componentes de um sistema informático
Quando olhamos para dentro de uma caixa de computador do tipo PC, podemos
identificar, como componentes fundamentais, a placa principal ou motherboard, as placas de
expansão, as drives, a fonte de alimentação e os cabos de ligação. Na Figura 10 pode ver-se o
aspecto genérico de um computador pessoal do tipo desktop.
Figura 10 – Computador típico.
4.4.1 – A placa principal ou motherboard
Na motherboard podemos identificar o CPU ou processador, a memória RAM, a
memória ROM, os circuitos ou chips de controlo, os slots de expansão e os vários
barramentos ou buses. Na Figura 11 pode ver-se uma motherboard típica.
Slots de
expansão
BUS
Chips de
controlo
RAM
Local do CPU
Figura 11 – Motherboard típica.
31
4.4.2 – O processador
O processador ou Unidade Central de Processamento (Central Processing Unit – CPU) é
o componente fundamental de um computador. É ele que faz todo o processamento de dados
que lhe chegam através da memória e dos dispositivos de entrada. Os dados resultantes das
operações de processamento são depois reenviados para a memória ou para os periféricos de
saída.
O CPU consiste basicamente num circuito integrado, constituído por quatro unidades
fundamentais: unidade de controlo; unidade de aquisição/descodificação; unidade aritmética e
lógica (ALU); e os registos. Na Figura 12 podem ver-se alguns processadores.
Figura 12 – Fotografias de alguns processadores.
Dito de uma forma muito resumida, a unidade de controlo envia aos outros componentes
sinais de activação e sincronização das operações. Fazendo uma analogia com uma orquestra,
esta unidade funciona como o maestro. Por seu lado, a unidade de aquisição/descodificação é
a responsável pela execução das instruções e consequentemente dos programas. É esta
unidade que indica onde se encontra a próxima instrução e executa a presente. A unidade
aritmética e lógica é a responsável por todos os cálculos ou operações aritméticas (adição,
subtracção, etc.) e lógicas (E, OU, etc.). Por seu lado, os registos são os locais onde são
armazenados temporariamente os dados a processar (abusando ainda mais da linguagem,
funcionam como uma espécie de memórias especiais). Na Figura 13 pode ver-se num
esquema típico, a forma como estas unidades interagem entre si.
32
CPU ou Processador
Memória principal
BUS
Aquisição
Descodificação
Registos
Controlo
ALU
Periféricos
Figura 13 – Constituição típica de um CPU e de um sistema informático.
A Tabela 4 apresenta um quadro resumo da evolução de algumas das características principais
dos microprocessadores da família Intel.
Ano
Processador
N.º Transístores
Relógio (MHz)
Largura do Bus
Largura do Bus
de Endereços
de dados
Registos
Níveis de
Cache
1978 8086
29 mil
4,75
20 bit
16 bit
16 bit
-
1982 80286
134 mil
6-25
24 bit
16 bit
16 bit
-
1985 80386
275 mil
16-40
24 bit
32 bit
32 bit
-
1989 80486
1,2 milhões
25-100
32 bit
32 bit
32 bit
1 nível
1993 Pentium
3,1 milhões
60-233
32 bit
64 bit
32 bit
1 nível
1995 Pentium Pro 5,5 milhões
150-200
32 bit
64 bit
32 bit
2 níveis
1997 Pentium II
7,5 milhões
233-450
36 bit
64 bit
32 bit
2 níveis
1999 Pentium III
15 milhões
450-1000
36 bit
64 bit
32 bit
2 níveis
2001 Pentium 4
100 milhões 1000-3000 36 bit
64 bit
32 bit
2 níveis
Tabela 4 – Evolução de alguns parâmetros dos microprocessadores da família Intel.
33
4.4.3 – Memórias
As memórias podem ser divididas em dois grandes grupos: memórias primárias ou
principais; e memórias secundárias, de armazenamento, ou auxiliares. Por seu lado, as
memórias primárias dividem-se em memórias do tipo Read Only Memory (ROM) ou memória
de simples leitura, e memória do tipo Random Access Memory (RAM) ou memória de leitura
e escrita de acesso aleatório. No que se refere às memórias auxiliares, os principais tipos
actualmente em uso são os discos rígidos, disquetes, bandas magnéticas, CDs e DVDs. Na
Tabela 5 pode ver-se esta classificação de uma forma esquemática. Nas Figura 14, Figura 15 e
Figura 16 podem ver-se algumas fotografias de memórias típicas.
ROM
PROM
ROM
EPROM
Primárias
ou
EEPROM
principais
SRAM
RAM
DRAM
Discos
Memórias
Disquetes
Suportes de
armazenamento
secundário
Bandas magnéticas
CDs
DVDs
Tabela 5 – Tipos de memórias.
Figura 14 – Memória primária tipo ROM.
34
Figura 15 – Memória primária tipo RAM.
Figura 16 – Memória secundária, auxiliar ou de armazenamento tipo disco rígido.
As memórias primárias RAM e ROM de um computador são divididas em pequenas
unidades, todas do mesmo tamanho. Estas unidades são vulgarmente chamadas “palavras”,
tendo cada uma um endereço. Apesar dos seus endereços serem numerados de uma forma
ascendente (do mais baixo para o mais alto, começando em zero) os seus conteúdos podem
ser perfeitamente aleatórios, ou seja, o conteúdo de uma dada célula de memória não tem
qualquer relação com o seu endereço. Na Figura 17 ilustra-se este conceito e na Figura 18
pode ver-se um núcleo de memória de ferrite.
35
Endereço
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Conteúdo
11010001
10101010
11110000
11001100
11010001
10101010
11110000
11001100
11010001
10101010
11110000
11001100
11010001
10101010
11110000
11001100
Figura 17 – Organização da memória.
Figura 18 – Núcleo de memória de ferrite.
As memórias secundárias permitem o armazenamento dos programas e informação que
os utilizadores necessitam de preservar para além dos momentos em que decorrem as
operações de processamento. Devemos distinguir entre dois tipos de dispositivos: os suportes
de armazenamento (discos, disquetes, etc.); e os que fazem circular a informação e que se
designam por drives. Nos dispositivos de armazenamento incluem-se os discos, as disquetes,
as bandas magnéticas, os discos ópticos (CD, DVD), os suportes magneto-ópticos (Discos de
Bernoulli e DVD-RAM ou DVD-RW), etcetera. Nas Figura 19 e Figura 20 mostra-se o
aspecto de duas superfícies de memórias de armazenamento secundário diferentes.
36
Figura 19 – Superfície de um disco rígido de 20 Mbytes.
Figura 20 – Superfície de um CD com música dos “Bon Jovi”.
4.4.4 – O barramento ou bus de um sistema informático
O barramento de sistema ou bus é constituído pelo conjunto de linhas ou ligações
eléctricas que permitem a sinalização e transferência de informação entre os diferentes
elementos constituintes do computador. Os sinais que circulam no bus são de três tipos, pelo
que é comum subdividir-se o bus em bus de dados, bus de endereços e bus de controlo – vejase a Figura 21.
37
BUS
CPU
Bus de endereços
Bus de dados
Bus de controlo
RAM/
ROM
Placas de
Expansão
I/O
Chips de
controlo
Figura 21 – Sistema de computador típico. Note-se a presença de três tipos de bus.
A arquitectura do bus define a maneira como este está concebido de forma a fazer a
interligação entre o CPU e os dispositivos de entrada/saída. Alguns dos tipos de arquitectura
de bus mais conhecidos são:
•
ISA – Industry Standard Architecture;
•
MCA – Micro Channel Architecture;
•
EISA – Extended ISA;
•
VL-BUS – VESA Local BUS;
•
PCI – Peripheral Component Interconnect;
•
PC Card ou PCMCIA – Personal Computer Module Cards International
Association;
•
USB – Universal Serial Bus;
•
AGP – Accelerated Graphics Port.
4.4.5 – Ligações de periféricos ou dispositivos de I/O
O CPU só produz trabalho útil se for capaz de “comunicar” com o exterior (porquê?).
Existe pois a necessidade da existência dos dispositivos de entrada/saída ou Input/Output
38
(I/O). Estes dispositivos ligam-se na sua maioria ao bus através de conectores localizados na
motherboard ou através das placas ou slots de expansão.
Neste grupo enquadra-se a placa de vídeo ou gráfica, que contém conectores para o
monitor, e as placas de utilização mais genérica, como é o caso das chamadas portas ou portos
(ports). Geralmente distingue-se entre portas série e portas paralelo. Esta distinção é devida à
forma como os dados são transmitidos: um bit de cada vez (transmissão série); ou vários bits
em simultâneo (transmissão paralelo).
Geralmente também se faz a distinção entre periféricos de entrada de dados, ou
simplesmente periféricos de entrada, periféricos de saída de dados, ou periféricos de saída, e
periféricos de entrada e saída de dados, ou periféricos de entrada/saída.
Alguns exemplos de dispositivos de saída são o monitor, a impressora e os traçadores
gráficos. Alguns dispositivos de entrada são o teclado o rato e o lápis óptico. As drives de
disquetes, os discos rígidos e os modems constituem exemplos de dispositivos de
entrada/saída. Passaremos agora a descrever de um modo muito resumido o funcionamento de
alguns destes dispositivos.
O monitor é um dispositivo de saída por excelência, que tradicionalmente é um tubo de
raios catódicos (Cathode Ray Tub – CRT). Num CRT, um feixe de electrões é disparado
através de sistemas de focagem e de deflexão sobre pontos específicos de uma superfície de
fósforo, emitindo um ponto luminoso. Veja-se a Figura 22. Na Figura 23 pode ver-se um
monitor típico.
Figura 22 – Esquema simplificado do modo de funcionamento de um CRT.
39
Figura 23 – Exemplo de CRT policromático (cores).
No entanto, este tipo de monitor tem vindo a ser substituído por outros, como por
exemplo:
•
Painel de cristal líquido (LCD) – o cristal líquido é composto por moléculas
cristalinas normalmente configuradas em espiral, fazendo rodar a polarização da
luz em 90º. Na presença de um campo eléctrico as moléculas alinham-se perdendo
este efeito polarizador;
•
Painel de Plasma – matriz de bolhas de néon em que cada uma pode ser activada
através de uma tensão;
•
Dispositivos 3D – baseando-se na característica estereoscópica da visão humana,
fornecem imagens diferentes a cada um dos olhos de forma a dar a ilusão de
tridimensionalidade;
•
Sistemas de projecção – permitem a projecção de imagens em superfícies
(normalmente) de grande dimensão.
As impressoras, vejam-se as Figura 24 e Figura 25, são geralmente classificadas quanto
ao seu modo de funcionamento e são normalmente divididas em quatro grandes grupos:
•
Matricial ou de agulhas – possui a cabeça de impressão com agulhas que actuam
(batem) individualmente sobre uma fita impregnada de tinta;
•
Laser – um feixe laser é direccionado para um tambor polarizando-o. O tambor
passa por toner que adere à parte atingida, sendo posteriormente pressionado
contra a folha de papel;
•
Jacto de tinta – a cabeça de impressão lança gotículas de tinta sobre o papel
(“jacto de tinta”);
40
•
Térmicas – as impressoras térmicas podem funcionar por dois métodos. A
impressão térmica directa e a impressão por transferência térmica. O sistema
térmico directo funciona com a cabeça térmica da impressora a aplicar calor sobre
um suporte (e.g. etiqueta) em papel térmico que tem a característica de escurecer
com o calor. É o mesmo método utilizado nas primeiras máquinas de fax. Este
sistema está limitado à utilização de suportes em papel térmico. Tem a vantagem
de ser mais económico ao nível dos consumíveis (só utiliza etiquetas), mas as
impressoras sofrem maior desgaste nas cabeças térmicas causado pelo contacto
directo com as etiquetas. O sistema de transferência térmica funciona transferindo
tinta do Foil para o suporte utilizado, i.e., o material receptor (e.g. etiqueta). O
Foil é o conjunto do Filme Base e a Tinta. O Filme Base serve de transporte da
Tinta e a sua qualidade fará com que o Foil não se rompa durante o processo de
impressão evitando paragens desnecessárias. Normalmente é de poliéster
transparente. Outra importante característica do Filme Base é a necessidade de ter
uma superfície suficientemente lisa e com baixo coeficiente de atrito para evitar
que a cabeça térmica da Impressora se danifique prematuramente, já que o
desgaste desta peça se deve basicamente aos efeitos abrasivos. No entanto, o
coeficiente de atrito do Foil é inferior ao causado pelas etiquetas em contacto
directo com a cabeça térmica, o que acontece no método impressão térmica
directa. Como regra importante, o Foil deve ser sempre mais largo do que o
material receptor. A Tinta é o ponto culminante do Foil e fabrica-se basicamente
em três formas: em base Cera, numa mistura de Cera/Resina, ou em base Resina.
O Foil é apresentado em bobinas de diferentes larguras e comprimentos para
adaptar-se às características das etiquetas e das impressoras.
Figura 24 – Exemplo de impressora “laser”.
41
Figura 25 – Exemplo de impressora “jacto de tinta”.
Alguns exemplos de traçadores gráficos (plotter) são:
•
Tipo cama – uma caneta desloca-se segundo dois eixos sobre um plano;
•
Tipo tambor – uma caneta desloca-se num eixo e a folha de papel num rolo
(tambor);
•
Tipo mesa – uma caneta desloca-se num eixo e a folha de papel permanece
imóvel na horizontal.
Vejam-se os exemplos das Figura 26 e Figura 27.
Figura 26 – Exemplo de traçador gráfico tipo tambor.
42
Figura 27 – Exemplo de traçador gráfico tipo mesa.
Os dispositivos de entrada por excelência são o teclado e o rato. Contudo existem muitos
outros que são de igual modo extremamente úteis. Na lista seguinte, e nas Figura 28, Figura
29 e Figura 30, apresentam-se alguns dispositivos de entrada de dados:
•
Teclado alfanumérico – é utilizado para a introdução de texto, comandos ou
selecção. Pode possuir conjuntos de teclas adicionais ou botões rotativos;
•
Rato (mouse) – detecta deslocamentos através da rotação da esfera na sua base
(ou de um feixe de luz) devido ao seu deslocamento num plano;
•
Painel táctil (touch panel) – identifica posições no ecrã através do toque do dedo;
•
Caneta ou lápis óptico (ligtht pen) – detecta posições no ecrã através da irradiação
do fósforo quando atingido pelo feixe de electrões;
•
Mesa digitalizadora – selecciona coordenadas 2D numa superfície;
•
Manípulo de controlo (joystick) – detecta deslocamentos através da inclinação do
manípulo;
•
Esfera localizadora (trackball) – detecta deslocamentos através da rotação da
esfera;
•
Scanners – permitem digitalizar imagens (formato raster) através do varrimento
óptico de desenhos ou figuras;
•
Digitalizador 3D – permite a medição de pontos num modelo físico;
43
•
Sensor Polhemos – usa a perturbação de campos magnéticos ortogonais causada
por um solenóide AC na caneta para o cálculo da sua posição e orientação no
espaço;
•
Spaceball – extensómetros medem a força aplicada na esfera segundo os três
ângulos de rotação;
•
Luva instrumentada – um sensor Polhemos indica a posição e orientação e um
sensor de flexão permite identificar a configuração de cada dedo da mão.
Figura 28 – Exemplo de teclado, rato, painel táctil e lápis óptico.
Figura 29 – Exemplo de mesa digitalizadora, joystick e trackball.
44
Figura 30 – Exemplo de digitalizador 3D, spaceball e luva instrumentada.
Os discos rígidos, disquetes e bandas magnéticas constituem o melhor exemplo de
dispositivos de entrada/saída. Contudo, existem outros exemplos, como sejam as placas de
som e de rede:
•
Placa de som – liga-se directamente num slot de expansão e oferece vários tipos
de conectores para o exterior, nomeadamente, mic in, line in, line out, speaker
out, joystick/ MIDI;
•
Placa de rede e modem – possibilitam a interligação de computadores, formandose redes de computadores (LAN, WAN, Internet, etc.).
Na Figura 31 apresenta-se um exemplo de uma placa de som e na Figura 32 um exemplo
de uma placa de rede.
Figura 31 – Exemplo de placa de som.
45
Figura 32 – Exemplo de placa de rede.
4.5 – Sistema Operativo
O sistema operativo (SO) é um dos componentes principais de um sistema informático.
Este cria um ambiente onde os utilizadores podem preparar os seus programas e executá-los
sem se preocuparem com os detalhes de hardware específicos de cada máquina. A
classificação do sistema informático segundo o número de tarefas simultaneamente permitidas
e o número de utilizadores simultâneos é determinado exclusivamente pelo tipo de sistema
operativo que este utiliza.
Entre outras tarefas de menor expressão, o SO faz a gestão do trabalho do processador, a
gestão da memória, a gestão de ficheiros e a gestão de periféricos. Uma das tarefas que os
sistemas operativos têm vindo a incorporar é a possibilidade de troca ou transferência de
informação entre aplicações diferentes. Na Figura 33 podem ver-se os componentes principais
de um sistema operativo típico.
A interface com o utilizador é geralmente de dois tipos: interface de linha de comando –
Command Line Interface (CLI); e interface gráfica – Graphical User Interface (GUI).
Alguns dos sistemas operativos mais divulgados são:
•
Disc Operating System ou simplesmente DOS (MS-DOS, PC-DOS, DR-DOS),
sendo mono–utilizador e mono–tarefa;
•
Unix (Unix SCO, AIX, HP-UX, Linux), sendo multi–utilizador e multi–tarefa;
•
Windows 3.x, 95, 98, 2000, NT, XP, sendo multi-utilizador e multi-tarefa.
46
Utilizador
Utilizador
SISTEMA
OPERATIVO
Editores
HARDWARE
Compiladores
CPU
Sistema
de
ficheiros
Memória
Periférico
Programas
Aplicacionais
Suporte para
comunicação
Loader
Utilizador
Processador de
Texto
Folha de Cálculo
Jogos
Browser
etc.
Figura 33 – Componentes principais de um sistema operativo.
Na organização da informação num SO deve distinguir-se pelo menos três níveis:
•
Drives, discos ou unidades de armazenamento – corresponde ao nível de entrada e
saída de dados ou de armazenamento;
•
Directorias, directórios ou pastas (folders) – correspondente à forma como os
dados se encontram organizados;
•
Ficheiros (files) – em última análise, é o local onde se encontram guardados os
dados.
Por sua vez, podemos dividir os ficheiros em duas classes principais:
•
Ficheiros de programas ou complementares de programas (ficheiros do tipo
executável, driver, etc.);
•
Ficheiros de dados (documentos de texto, imagens, bases de dados, etc.).
47
5 – Algoritmos
Antes de pensarmos em começar a programar um computador, devemos ter presente que
os computadores, feliz ou infelizmente, só fazem exactamente aquilo que mandamos e não
necessariamente o que desejamos que eles façam (pelo menos até à data!).
A programação de computadores pode ser difícil, mas podemos torná-la mais fácil se
dividirmos um problema sistematicamente em partes menos complexas. Esta técnica é
vulgarmente conhecida por “Dividir para conquistar”. Um problema mais ou menos complexo
é primeiramente dividido em problemas de dimensão mais reduzida e de fácil resolução.
Podemos fazer a analogia com um puzzle onde as pequenas peças se encaixam por forma
produzir a solução final (veja-se a Figura 34).
Figura 34 – Fases principais na resolução de um problema.
Na fase de resolução do problema, concentramo-nos apenas em elaborar um algoritmo
para resolver o problema proposto. Só depois é que passamos à fase de implementação do
algoritmo numa linguagem de programação. Tendo um algoritmo suficientemente preciso, a
sua codificação numa linguagem é directa.
Deve aprender-se a programar com uma e não numa linguagem de programação.
Um algoritmo pode ser definido como uma sequência ordenada, e sem ambiguidade, de
passos que levam à solução de um problema. Geralmente, descrevem soluções de problemas
do nosso mundo, afim de serem implementadas utilizando os recursos do mundo
computacional. Como este possui severas limitações em relação ao nosso mundo, exige que
49
sejam impostas algumas regras básicas na forma de solucionar os problemas, para que
possamos utilizar os recursos de hardware e software disponíveis. Pois, os algoritmos,
apesar de servirem para representar a solução de qualquer problema, no caso do
processamento de dados, eles devem seguir as regras básicas de programação para que sejam
compatíveis com as linguagens de programação.
Existem programas chamados de compiladores que traduzem os programas por nós
produzidos (escritos numa linguagem adequada à compreensão humana), para a linguagem
máquina (veja-se a Figura 35).
Programa
fonte
Compilação
Programa
Objecto
Execução
Resultados
Figura 35 – Fases de desenvolvimento/teste de um algoritmo/programa.
Pode definir-se programa fonte como sendo o conjunto de instruções escritas pelo
programador numa linguagem de programação, perceptível pelos humanos e vulgarmente
designada por “linguagem de alto nível” – por exemplo em PASCAL.
Pode também dizer-se que compilar um programa significa traduzi-lo do código fonte
para código objecto, que no fundo representa o código máquina (sequência de 0’s e 1’s).
As linguagens de programação podem ser classificadas em três grandes grupos ou tipos:
procedimentais, sequenciais ou imperativas; declarativas; e orientadas a objectos.
As linguagens tipo procedimentais, sequenciais ou imperativas distinguem-se por uma
sequência de comandos ou instruções fornecidas pelo programador onde o computador
executa mecanicamente uma série de ordens bem determinadas. O computador não tem
conhecimento do problema que está a resolver, sendo da responsabilidade do programador
descrever em pormenor a forma de resolução do problema. O PASCAL, C, Fortran e Basic
são exemplos de linguagens de programação deste tipo.
Por seu lado, nas linguagens de programação declarativas o programador descreve o
problema e uma série de relações entre as entidades, podendo o próprio computador
estabelecer o conjunto de acções para atingir a solução do problema. O programador não
especifica qualquer cálculo. Podem ser feitas perguntas relativas às relações sem ser preciso
explicar como se obtém a resposta. Estas linguagens são muito utilizadas na área da
Inteligência Artificial, constituindo o Prolog um exemplo por excelência.
50
Quanto às linguagens de programação orientadas a objectos podemos dizer que surgem
associadas à evolução da programação estruturada, clara e modular, sendo os seus módulos
independentes. As entidades são objectos, sendo estes compostos por dados e métodos que
operam sobre estes dados. Do conjunto de características destas linguagens destacam-se as
seguintes:
•
Encapsulamento;
•
Robustez;
•
Módulos reutilizáveis;
•
Classes;
•
Herança.
Como exemplos de linguagens de programação deste tipo podemos indicar o C++ e o JAVA.
5.1 – Noção de algoritmo
Um algoritmo deve descrever de forma detalhada e sem qualquer ambiguidade as
diferentes fases para a resolução de um problema. Tal como foi dito no ponto anterior, um
algoritmo é constituído por uma sequência ordenada, e sem ambiguidade, de passos que
levam à solução de um problema.
Nada melhor do que um exemplo para ajudar a clarificar estes conceitos, bem como
ajudar a definir aquilo que deve ser um algoritmo. Suponhamos que pretendemos substituir
uma lâmpada incandescente que se encontra fundida (esta é com certeza uma tarefa já
desempenhada por grande parte de nós). O nosso objectivo é descrever esta tarefa num
conjunto de passos de forma clara, ordenada e sem qualquer ambiguidade, que conduzam à
substituição da referida lâmpada. Podemos pois indicar o seguinte conjunto ordenado de
passos:
1. Colocar uma escada debaixo da lâmpada queimada;
2. Seleccionar uma nova lâmpada para a substituição;
3. Se a potência da lâmpada seleccionada não for igual à da lâmpada queimada,
repetir o processo até encontrar uma que sirva:
a. Descartar a lâmpada seleccionada;
51
b. Seleccionar uma outra lâmpada;
4. Repetir até chegar à lâmpada:
a. Subir um degrau na escada;
5. Repetir até que a lâmpada esteja desapertada do casquilho:
a. Girar a lâmpada no sentido anti-horário;
6. Colocar a nova lâmpada no casquilho;
7. Repetir até que a lâmpada fique apertada:
a. Girar a lâmpada no sentido horário;
8. Repetir até chegar ao solo:
a. Descer um degrau.
9. Guardar a escada.
Note-se que neste algoritmo existem passos que se podem considerar principais e outros
secundários. Isto não quer dizer que uns são mais importantes do que os outros. O que deve
ser realçado é o facto de os secundários só fazerem sentido porque os primários existem. Eles
servem como complemento de detalhe, ou se preferirmos, para melhor especificar o que se
pretende fazer com o passo principal. Repare-se que podem existir vários passos secundários
dentro de um principal. Por seu lado, dentro dos secundários também podem existir outros
sub-passos.
Uma das técnicas mais amplamente utilizada no desenvolvimento de algoritmos,
sobretudo algoritmos respeitantes a programas de grandes dimensões, é “dividir para
conquistar”. A ideia base consistem em dividir o problema global em problemas de menor
dimensão (sub-problemas) que possam, preferencialmente, ser resolvidos de forma autónoma
(isto é, cada um deles pode ser resolvido separadamente dos outros). No final a solução será
resultado do agrupamento dos diferentes sub-algoritmos, resultantes da resolução de cada um
dos sub-problemas.
5.2 – Dados e tipos de dados
Qualquer programa de computador manipula conjuntos de dados com o objectivo de
produzir informação.
52
Estes dados podem ser de vários tipos: numérico; caracter; cadeia de caracteres ou string;
enumerado; lógico; e ponteiro. Por seu lado, os dados do tipo numérico podem ser do tipo real
ou inteiro. Os dados do tipo real ainda se podem representar como decimais ou em vírgula
flutuante. Na Figura 36 pode ver-se um esquema em árvore da distribuição dos tipos de dados.
dados
numérico
real
decimal
caracter
string
enumerado
lógico
ponteiro
inteiro
vírgula-flutuante
Figura 36 – Tipos de dados.
Os dados numéricos do tipo inteiro não possuem parte fraccionária ou decimal, podendo
ser positivos ou negativos. Constituem exemplos de dados deste tipo os números 13, 7, -6,
208, 0 e 502.
Por seu lado, os dados do tipo real possuem uma parte inteira e uma parte fraccionária.
Os números 23.8, 0.02, -10.3, 12.0 e 502.36 são exemplo deste tipo de dados. Os números
representados em vírgula flutuante são incluídos no tipo real. Esta representação é usada para
valores numéricos muito grandes ou muito pequenos. Possuem um termo fraccionário
(mantissa) e um termo em expoente (expoente), geralmente como potência de 10. Os números
0.385x10+8 e 1.385x10-15 estão representados em vírgula flutuante.
Os dados não numéricos incluem todos os outros tipos de dados. Destes dados fazem
parte os do tipo caracter, conjunto de caracteres ou string, lógico, enumerado e ponteiro.
Os dados do tipo caracter são constituídos pelo conjunto padrão de caracteres. Tem-se os
caracteres alfabéticos, letras A, B, C, ..., Z, a, b, c, ..., z; os dígitos 0, 1, ..., 9; e os caracteres
especiais -, #, !, &, =, *, etcetera.
Os dados do tipo string ou cadeias de caracteres são formados por uma sequência de itens
do tipo caracter. Por exemplo ‘Bom dia’ e ‘77+23 =’. O delimitador de uma cadeia de
caracteres usada por nós é o símbolo apóstrofo ou aspa simples.
53
Os dados do tipo lógico ou Booleano (da álgebra de George Boole), só podem tomar dois
valores: falso (F) ou verdadeiro (V).
Não serão estudados os dados do tipo ponteiro.
5.3 – Operadores e operações básicas
Antes de podermos efectuar operações é conveniente definir os tipos de operadores com
que iremos trabalhar. Os operadores podem ser divididos em três grandes grupos: aritméticos;
lógicos; e relacionais.
No grupo de operadores aritméticos incluem-se os seguintes:
•
()
Parêntesis
•
+, –
Sinal
•
+
Adição
•
–
Subtracção
•
*
Multiplicação
•
/
Divisão.
A expressão (2+X)*Y+0.7*Z constitui um exemplo de utilização dos operadores
aritméticos. As regras de prioridade de aplicação destes operadores são as utilizadas na
análise matemática e serão clarificados no próximo ponto.
Os operadores relacionais são formados por:
•
≤
Menor ou igual
•
<
Menor
•
≥
Maior ou igual
•
>
Maior
•
=
Igual
•
≠
Diferente.
A expressão x ≥ 10 constitui um exemplo de utilização dos operadores relacionais.
54
Os operadores lógicos que iremos ver são constituídos pela conjunção ‘E’, disjunção
‘OU’, ‘OU EXCLUSIVO’ e pela negação ‘NEGAÇÃO’. A expressão (x = 10) E (y > 0)
constitui um exemplo de utilização dos três tipos de operadores.
5.4 – Variáveis e expressões
A noção mais importante na definição de um algoritmo é a de variável. Esta noção é
muito semelhante à de variável utilizada na análise matemática. Contudo, existem certas
particularidades que de uma forma geral estão relacionadas com a capacidade de
representação, e esta por seu lado está fortemente ligada à linguagem de implementação
utilizada. Por estes motivos não entraremos em grandes detalhes nem definições, optando por
clarificar os conceitos com recurso a exemplos.
Contudo, não podemos deixar de dar uma definição, ainda que superficial do que é uma
variável. Uma variável é uma entidade que possui um valor, sendo reconhecida no programa
por um nome (identificador). Pode receber diferentes valores ao longo de um algoritmo ou
programa, mas num determinado instante só guarda um valor. O nome de uma variável deve
começar obrigatoriamente por uma letra. Os restantes caracteres podem ser letras ou dígitos,
não sendo permitidos espaços. Por motivos de pormenor de implementação, aconselhamos a
não utilização de qualquer acentuação na atribuição de nomes (identificadores) às variáveis.
Por outro lado, uma constante é uma entidade que armazena um valor definido numa
expressão literal de um determinado tipo. Este valor não pode ser alterado por qualquer
declaração ao longo do algoritmo ou programa. Uma constante também é representada por um
identificador, obedecendo a sua construção (o seu nome) às mesmas regras das variáveis. A
constante matemática número irracional π (de valor aproximado 3.1415) constitui um
exemplo de definição de constante (num algoritmo ou programa usa-se geralmente o
identificador ‘PI’ para representar esta constante).
A operação de atribuição tem por objectivo colocar um dado valor numa variável, isto é,
a partir daquele ponto, e até que uma operação idêntica aconteça, essa variável passa a
guardar aquele valor. Na sua forma geral, esta operação possui a sintaxe:
variável ß expressão.
Note-se que esta operação é destrutiva, isto é, perde-se o valor que a variável guardava
anteriormente. Por exemplo, suponhamos um algoritmo com as seguintes instruções:
55
Aß3
A ß A*2
Com a primeira operação de atribuição a variável A passa a guardar o valor 3. Ao executar a
segunda operação o valor 3 é perdido e passa a guardar o valor 6 (correspondente a
multiplicar o valor anteriormente guardado 3 pela constante 2).
Note-se que numa operação de atribuição só é alterado o valor da variável do lado
esquerdo da atribuição. Os valores das variáveis que possam existir do lado direito mantêm-se
inalteráveis (caso não existam do lado esquerdo).
Uma expressão resulta de uma combinação de variáveis, constantes e operadores. Por
exemplo:
c ß a/b
area ß base*altura/2
Para ajudar a clarificar os conceitos até agora apresentados e as regras de prioridade dos
operadores aritméticos, vejam-se os seguintes exemplos:
1. A ß 3+6*2
2. A ß -5-6*5/6
3. A ß 8+7*3+4*5
4. A ß (3+6)*2
Tendo presente que a multiplicação e a divisão tem prioridade sobre a adição e a subtracção e
que a utilização de parêntesis introduz prioridade máxima, os resultados de cada uma das
expressões anteriores é:
1. 15
2. -10
3. 49
4. 18.
56
5.5 – Entrada e saída de dados
Tal como já anteriormente notado, os computadores só produzem trabalho útil se lhe
podermos fornecer dados e se ele for capaz de nos devolver o resultado das operações
efectuadas sobre os dados. Existem instruções específicas para este efeito.
A instrução LER(lista de entrada) tem por objectivo a introdução de dados pelo teclado,
isto é, o operador pode fornecer um conjunto de dados ao computador (programa) via teclado.
Podem ser indicados vários valores a ser introduzidos numa única instrução do tipo LER,
separados por vírgula, ou apenas um valor. Por exemplo:
LER(raio)
deve ser introduzido pelo teclado o valor para a variável raio.
LER(A, B, C)
devem ser introduzidos pelo teclado os valores para as variáveis A, B
e C.
Por outro lado, quando se pretende apresentar os resultados ao operador, existe a
instrução ESCREVER(lista de saída). Esta instrução apresenta no écran o conjunto de dados
constantes na lista. Por exemplo:
ESCREVER(A, B, C)
apresenta no écran os valores das variáveis A, B e C.
ESCREVER('3+4=', C)
apresenta no écran a frase 3+4= e o valor da variável C.
5.6 – Funções embutidas ou pré-definidas
Existem funções previamente programadas, e que geralmente se designam por embutidas
ou pré-definidas, que são particularmente úteis para cálculo aritmético. Na Tabela 6
apresentamos algumas dessas funções. Desta tabela consta também o tipo de dado que a
função aceita (inteiro ou real) e o valor devolvido (o resultado do cálculo e o seu tipo de
dados associado – real ou inteiro).
57
Nome da
função
ABS(x)
SQRT(x)
SQR(x)
TRUNC(x)
ROUND(x)
LOG(x)
LOG10(x)
EXP(x)
SIN(x)
COS(x)
Tipo de dado que aceita
x: uma expressão real ou inteira
x: uma expressão real ou inteira
(deve ser ≥ 0)
x: uma expressão real ou inteira
x: uma expressão real ou inteira
x: uma expressão real ou inteira
x: uma expressão real ou inteira
x: uma expressão real ou inteira
x: uma expressão real ou inteira
x: uma expressão real ou inteira
x: uma expressão real ou inteira
Valor devolvido
Valor absoluto: o resultado é |x|, mesmo tipo que x
Raiz quadrada: Resultado é
x , tipo real
O valor do quadrado de x, ou seja, x2
Valor truncado: o resultado é o maior inteiro T tal que
|T| ≤ |x|
Valor arredondado: o resultado é o maior inteiro T tal que
|T| ≤ |x+0.5|
Logaritmo base e: o resultado é o logaritmo neperiano ou
natural de x, tipo real
Logaritmo base 10: o resultado é o logaritmo base 10, de x,
tipo real
x
Exponencial: o resultado é e , tipo real
Seno: o resultado é o seno de x (radianos), tipo real
Coseno: o resultado é o coseno de x (radianos), tipo real
Tabela 6 – Exemplos de funções pré-definidas.
58
6 – Estruturas de decisão
Com as ferramentas até ao momento apresentadas já somos capazes de produzir
algoritmos simples. Estes algoritmos seguem sensivelmente um modelo padrão:
1. Entrada de dados
2. Cálculos
3. Apresentação de resultados.
Vamos agora apresentar dois poderosos conceitos de programação, os quais requerem o
poder de decisão e através dos quais podemos alterar o fluxo linear de um programa pelo uso
de estruturas de controlo.
As estruturas a estudar neste ponto permitem seleccionar uma acção de um conjunto de
alternativas especificadas. No próximo ponto estudaremos estruturas que permitem repetir
uma série de acções, que vulgarmente denominadas de repetitivas. Ambas fazem parte das
estruturas de decisão e controlo.
6.1 – Selecção de acções alternativas – SE-ENTÃO-SENÃO
A construção algorítmica SE-ENTÃO-SENÃO permite-nos seleccionar entre duas acções
alternativas, permitindo a execução de partes distintas do algoritmo. O formato desta
instrução é o seguinte:
SE condição ENTÃO
alternativa verdadeira
SENÃO
alternativa falsa
FIM SE
Nesta construção, a parte do algoritmo “alternativa verdadeira” será executada caso a
condição “condição” se verifique, isto é, caso esta condição seja verdadeira. Caso contrário (a
condição não se verifica) é executada a parte do algoritmo correspondente à “alternativa
falsa”. Esta construção possui a interpretação gráfica apresentada na Figura 37, que
corresponde ao diagrama de fluxo ou simplesmente fluxograma.
59
Entrada
Verdadeira
Falsa
Avaliar
condição
Processar alternativa
verdadeira
Processar alternativa
falsa
Saída
Figura 37 – Diagrama de fluxo da construção SE-ENTÃO-SENÃO.
Esta construção possui uma forma simplificada em que a alternativa falsa é vazia (não
existe). Esta versão da instrução possui a forma SE-ENTÃO, devendo ser utilizada sempre
que desejarmos fazer algo apenas quando a condição for verdadeira. Na Figura 38 pode ser
visto o diagrama de fluxo correspondente.
Entrada
Verdadeira
Avaliar
condição
Falsa
Processar alternativa
verdadeira
Saída
Figura 38 – Diagrama de fluxo da construção SE-ENTÃO.
Veja-se um exemplo de aplicação da estrutura SE-ENTÃO-SENÃO. Suponhamos que
pretendemos determinar qual de dois números introduzidos via teclado é o maior, escrevendoo no écran. Não nos vamos preocupar com o tipo de número, isto é, não interessa se os
números são inteiros ou reais. Na Figura 39 apresenta-se o diagrama de fluxo correspondente
à parte fundamental do algoritmo. As variáveis A e B representam os dois números.
60
Entrada
Verdadeira
Falsa
A>B?
Escrever (B)
Escrever (A)
Saída
Figura 39 – Diagrama de fluxo para determinação do maior de dois valores.
Em linguagem algorítmica, este segmento escreve-se
SE A > B ENTÃO
ESCREVER(A)
SENÃO
ESCREVER(B)
FIM SE
Em PASCAL escreve-se
IF A > B THEN
WRITE(A)
ELSE
WRITE(B)
NOTA: a linguagem de programação PASCAL não distingue entre maiúsculas e minúsculas.
Pode-se escrever o programa utilizando qualquer combinação destes dois tipos de letras. Por
exemplo, AREA, Area, aREA, etc., em PASCAL serão considerados o mesmo identificador.
Contudo, existem linguagens que fazem esta distinção, como é o caso do C. Nos exemplos
que se apresentam ao longo destes apontamentos é pois possível encontrar estas situações.
Vejamos um exemplo completo. Pretende-se determinar se um dado aluno foi ou não
aprovado a uma disciplina. Para isso é necessário introduzir via teclado a respectiva
classificação, apresentando-se depois o resultado no écran. Se o aluno ficou aprovado, deve
61
ser apresentada a nota final arredondada à unidade. Se o aluno reprovou apenas deve ser
apresentado no écran este facto. No algoritmo seguinte apresenta-se uma solução para o
problema:
ALGORITMO Classificação
VARIÁVEIS nota DO TIPO REAL
1. [Ler a nota do aluno]
ESCREVER('Classificação no teste: ')
LER(nota)
2. [Classificar o aluno]
SE nota ≥ 9.5 ENTÃO
ESCREVER('Aprovado com ', ROUND(nota), ' valores.')
SENÃO
ESCREVER('Reprovado')
FIM SE
3. FIM DO ALGORITMO
Ao algoritmo é atribuído um nome que deve procurar clarificar a sua finalidade, ou seja, que
resuma o seu objectivo principal. Repare-se que a seguir à declaração ‘ALGORITMO
classificação’ surge a zona de declaração de variáveis. Neste caso, a variável ‘nota’ serve para
guardar a classificação introduzida pelo teclado. Esta variável deve ser do tipo real uma vez
que a classificação do aluno pode conter parte decimal. Note-se que antes de se ler o valor da
classificação do aluno apresenta-se uma mensagem informativa para que o operador saiba o
que está a acontecer. A função pré-definida ROUND é responsável por efectuar o
arredondamento à unidade na classificação final (veja-se a Tabela 6). A correspondente
codificação em PASCAL é a seguinte:
Program Classificacao;
Var nota : Real;
Begin
{Ler a nota do aluno}
62
Write('Classificação no teste: ');
Read(nota);
{Classificar o aluno}
If nota >= 9.5 then
Writeln('Aprovado com ', Round(nota), ' valores.')
Else
Writeln('Reprovado');
End.
Nesta codificação repare-se em particular que o símbolo ‘≥’ é substituído por ‘>=’, os
comentários são introduzidos entre chavetas e no aparecimento de um ponto–e–vírgula a
separar cada instrução. Note-se ainda que o final do programa é marcado com a palavra ‘end’
seguida de ponto–final. Antes da palavra ‘else’ não é introduzido nenhum ponto-e-vírgula
porque a instrução ‘if-then-else’ só acaba no fim do ‘else’. Não deveríamos ter colocado um
ponto–e–vírgula no final desta construção, uma vez que a instrução que se segue é um ‘end’.
Contudo, este tipo de falha tem por consequência a introdução da instrução máquina NOP (no
operation), que corresponde a não haver qualquer operação por parte do processador. Neste
caso o objectivo da sua utilização é ajudar a clarificar a forma como se define a estrutura ‘ifthen-else’.
6.2 – SE’s encaixados
É possível incluir dentro de uma estrutura do tipo SE-ENTÃO-SENÃO outra estrutura do
mesmo tipo. Este tipo de inclusão é vulgarmente conhecido pela denominação de “encaixe”.
Expliquemos o formato com recurso a um exemplo:
SE c1 ENTÃO
s1
SENÃO
SE c2 ENTÃO
s2
SENÃO
63
s3
FIM SE
FIM SE
Repare-se que ‘s3’ só será executada (ou atingida) caso as condições ‘c1’ e ‘c2’ sejam falsas
(porquê?). Paralelamente à utilização de estruturas SE-ENTÃO-SENÃO encaixadas, é
também possível utilizar a conjunção (E) e a disjunção (OU) de condições. Isto aumenta a
flexibilidade de escrita, permitindo reduzir o número de estruturas do tipo SE-ENTÃOSENÃO e simplificar a escrita de algoritmos. No algoritmo seguinte ilustra-se a aplicação de
estruturas SE-ENTÃO-SENÃO encaixadas.
Numa Operação Stop típica no IP4, quando uma viatura circular a uma velocidade
superior a 90 Km/h deve ser mandada parar. A infracção é considerada grave se o excesso de
velocidade for inferior ou igual a 30 Km/h e muito grave em caso contrário. O algoritmo
seguinte apresenta uma solução para este problema.
ALGORITMO Operação stop IP4
VARIÁVEIS matricula DO TIPO STRING
velocidade, excesso DO TIPO REAL
1. [Definir limite de velocidade]
CONSTANTE LIMITE = 90
2. [Ler a matricula do automóvel]
ESCREVER('Matricula: ')
LER(matricula)
3. [Ler a velocidade do automóvel]
ESCREVER('Velocidade: ')
LER(velocidade)
4. [Multar o veículo em caso de excesso de velocidade]
SE velocidade > LIMITE ENTÃO
ESCREVER('Fazer parar o automóvel ', matricula)
excesso ß velocidade-LIMITE
64
ESCREVER('Excesso de velocidade de ',excesso,' Km/h.')
SE excesso ≤ 30 ENTÃO
ESCREVER('Passar multa grave.')
SENÃO
ESCREVER('Passar multa muito grave.')
FIM SE
FIM SE
5. FIM DO ALGORITMO
Note-se que antes de poder decidir se a viatura transita ou não em excesso de velocidade é
necessário conhecer a sua matrícula e a velocidade respectiva. A uma viatura só se passa uma
multa muito grave se antes de mais transitar em excesso de velocidade (daí o teste para
determinar se a multa é muito grave ser feito apenas quando já se sabe que a viatura circula
em excesso de velocidade). Repare-se ainda que caso a viatura circule dentro dos limites de
velocidade estipulados pela lei, nenhuma acção deve ser desenvolvida. A correspondente
codificação em PASCAL é a que se segue:
program Operacao_stop_IP4;
const LIMITE=90;
var
velocidade, excesso : Real;
matricula: string;
begin
{Ler a matricula do automóvel}
write('Matricula: ');
readln(matricula);
{Ler a velocidade do automóvel}
write('Velocidade: ');
readln(velocidade);
{Multar o veículo em caso de excesso de velocidade}
65
if velocidade > LIMITE then
begin
writeln('Fazer FIM DO ALGORITMO o automóvel ', matricula);
excesso := velocidade-LIMITE;
writeln('Excesso de velocidade de ',excesso,' Km/h.');
If excesso <= 30 then
writeln('Passar multa grave.')
else
writeln('Passar multa muito grave.');
end
end.
Nesta codificação repare-se na utilização da construção ‘begin-end’ dentro da estrutura ‘ifthen’. Esta estrutura possibilita executar um conjunto de instruções numa situação em que
aparentemente só era possível executar apenas uma. Esta construção é geralmente designada
por “bloco de código”.
6.3 – Estrutura de selecção múltipla
Quando temos muitas construções do tipo SE-ENTÃO-SENÃO encaixadas o algoritmo
torna-se confuso. A estrutura CASO permite fazer uma selecção quando temos várias
alternativas. O formato desta estrutura é o seguinte:
CASO (expressão) POSSUA VALOR
valor v1 : Lista de declarações
valor v2 : Lista de declarações
valor vn : Lista de declarações
valor i1 até valor i2 : Lista de
declarações
valor s1, valor s2 , .., valor sn : Lista de declarações
defeito: Lista de declarações
66
FIM CASO
Suponhamos que pretendíamos determinar se um dado caracter introduzido via teclado
corresponde a uma letra ou a um dígito. Uma solução em PASCAL é
case opcao of
‘A’..’Z’, ‘a’..’z’: writeln(‘Letra’);
‘0’..’9’: writeln(‘Digito’);
else writeln(‘Caracter especial’)
end
Note-se a existência de um ‘else’ fazendo lembrar precisamente a estrutura ‘if-then-else’.
No exemplo que se segue pretende-se simular o funcionamento de uma calculadora com
as operações de adição, subtracção, multiplicação e divisão. Em primeiro lugar deve ser
indicado o primeiro operando, seguido da operação e terminando com o segundo operando.
No final devem ser apresentados o primeiro operando, a operação realizada, o segundo
operando e o resultado. Caso a operação indicada não conste da lista de operações
implementadas deve ser apresentada uma mensagem de erro esclarecedora. O seguinte
algoritmo apresenta uma solução para este problema.
ALGORITMO Calculadora
VARIÁVEIS op1, op2 DO TIPO REAL
operacao DO TIPO CARACTER
1. [Ler o valor do primeiro operando]
ESCREVER('1º Operando: ')
LER(op1)
2. [Seleccionar a operação a realizar]
ESCREVER('Adição(+), Subtracção(-), Multiplicação(*) e Divisão(/)')
LER(operacao)
3. [Ler o valor do segundo operando]
ESCREVER('2º Operando: ')
67
LER(op2)
4. [Escrever o resultado da operação seleccionada]
CASO (operacao) POSSUA VALOR
'+': ESCREVER(op1,'+',op2,'=',op1+op2)
'-': ESCREVER(op1,'-',op2,'=',op1-op2)
'*': ESCREVER(op1,'*',op2,'=',op1*op2)
'/': ESCREVER(op1,'/',op2,'=',op1/op2)
DEFEITO: ESCREVER('Operação ilegal')
FIM CASO
5. FIM DO ALGORITMO
Note-se que as variáveis ‘op1’ e ‘op2’ guardam os valores dos operandos, sendo estas do
tipo real (porque os valores a introduzir podem ser deste tipo). A variável ‘operacao’ é do tipo
caracter, uma vez que se pretende guardar o valor de um dos símbolos ‘+’, ‘-’, ‘*’, ‘/’. A
codificação em PASCAL é a seguinte:
program calculadora;
var op1, op2 : real;
operacao : char;
begin
{Ler o valor do primeiro operando}
write('1º Operando: ');
readln(op1);
{Seleccionar a operação a realizar}
writeln('Adição(+),Subtracção(-),Multiplicação(*) e Divisão(/)');
readln(operação);
{Ler o valor do segundo operando}
write('2º Operando: ');
68
readln(op2);
{Escrever o resultado da operação seleccionada}
case operacao of
'+' : writeln(op1,'+',op2,'=',op1+op2);
'-' : writeln(op1,'-',op2,'=',op1-op2);
'*' : writeln(op1,'*',op2,'=',op1*op2);
'/' : writeln(op1,'/',op2,'=',op1/op2);
else writeln(‘Operação ilegal’)
end
end.
O que acontece quando o segundo operando for nulo e a operação escolhida a divisão? Como
exercício sugerimos a alteração do algoritmo de forma a evitar este problema.
A diferença principal entre a instrução WRITE e a instrução WRITELN reside no facto
da última mudar de linha após ter escrito no écran. A instrução READLN faz um reset ao
buffer de entrada antes de ler do teclado, enquanto que a instrução READ não faz. Na prática,
sempre que pretendermos ler vários valores consecutivos via teclado devemos usar a instrução
READLN.
69
7 – Ciclos
Neste ponto abordaremos as estruturas de decisão repetitivas, isto é, estruturas que
dependendo da verificação ou não de uma dada condição executam de forma repetitiva um
conjunto de instruções. Dada a sua arquitectura, os computadores são particularmente
adequados a aplicações nas quais uma operação ou uma série de operações devem ser
repetidas várias vezes.
Existem dois tipos de estruturas deste tipo. As estruturas que repetem um conjunto de
operações (ou instruções) um número fixo e bem determinado de vezes – ciclos
incondicionais – e as estruturas cujo número de vezes que repetem as operações dependendo
da verificação de uma condição – ciclos condicionais.
7.1 – Estrutura REPETIR-ENQUANTO
A estrutura REPETIR-ENQUANTO (while-do) é uma estrutura repetitiva condicional. O
seu formato é o seguinte:
REPETIR ENQUANTO condição
Lista de declarações
FIM REPETIR
Note-se que a ‘lista de declarações’ só é executada se a condição for verdadeira. Este tipo de
estrutura deve ser usada sempre que exista a possibilidade de a condição não se verificar logo
à partida. Uma aplicação típica é o das listas de dados que podem ser vazias. A ‘lista de
declarações’ deve conter instruções que possam modificar a condição (sob pena de se entrar
num ciclo infinito). Na Figura 40 pode ver-se o diagrama de fluxo correspondente.
71
Entrada
Avaliar a
Condição de
Ciclo
Falsa
Verdadeira
Processar informação
interior ao ciclo
Saída
Figura 40 – Diagrama de fluxo da estrutura REPETIR-ENQUANTO.
Suponha-se que se pretende ler uma série de valores via teclado e somá-los. Esta lista
termina com a introdução do valor – 1, podendo esta série de valores ser vazia, isto é, o
primeiro elemento a ser introduzido pode ser o valor – 1. No algoritmo seguinte apresenta-se
uma solução para o problema:
soma ß 0
LER(x);
REPETIR ENQUANTO x ≠ –1
soma ß soma + x
LER(x)
FIM REPETIR
A variável ‘x’ serve para guardar o valor introduzido pelo teclado. Note-se a utilização da
variável ‘soma’ para acumular o resultado total. Antes de se poder adicionar algo a esta
variável, torna-se necessário garantir que o seu conteúdo é nulo. Isto é feito através da
utilização da instrução ‘somaß0’. Este é um princípio muito utilizado e designado por
inicialização de variáveis. Repare-se ainda que o valor ‘-1’ não é incluído na soma final
(total). A seguir apresenta-se a codificação em PASCAL correspondente:
soma := 0;
read(x);
while x <> –1 do
72
begin
soma := soma + x;
read(x)
end;
Note-se uma vez mais a utilização do bloco de código (instruções begin-end) dentro da
estrutura while-do (REPETIR-ENQUANTO) com o objectivo de tornar possível o executar de
um conjunto de instruções onde se esperava apenas uma.
No algoritmo seguinte, apresenta-se uma solução para o cálculo do factorial de um
número. A variável ‘numero’ guarda o número do qual se pretende calcular o factorial, a
variável ‘factor’ serve para contar desde 2 até ao número introduzido (controlando-se desta
forma a saída do ciclo), e a variável ‘resultado’ guarda o resultado final.
ALGORITMO Factorial
VARIÁVEIS numero, factor, resultado DO TIPO INTEIRO
1. [Ler numero para o qual deve ser calculado o factorial]
ESCREVER('Numero: ')
LER(numero)
2. [Calcular o factorial: n!=1*2*...*n]
resultado ß 1
factor ß 2
REPETIR ENQUANTO factor ≤ numero
resultado ß resultado * factor
factor ß factor + 1
FIM REPETIR
3. [Escrever o resultado]
ESCREVER(numero, '! = ',resultado)
4. FIM DO ALGORITMO
A codificação em PASCAL correspondente é:
73
program Factorial;
var resultado, numero, factor : integer;
begin
{Ler numero para o qual deve ser calculado o factorial}
write('Numero: ');
read(numero);
{Calcular o factorial: n!=1*2*...*n}
resultado := 1;
factor := 2;
while factor <= numero do
begin
resultado := resultado * factor;
factor := factor + 1
end;
{Escrever o resultado}
writeln(numero, '! = ',resultado)
end.
Neste momento impõe-se uma nota acerca da capacidade de representação das variáveis
do tipo ‘integer’ em PASCAL numa máquina com sistema operativo Windows. As variáveis
deste tipo são capazes de representar números inteiros na gama de valores compreendidos
entre –32768 a +32767. Como é sabido o factorial de 8 é 40320, excedendo a capacidade de
representação deste tipo de variável. Se pretendermos calcular o factorial de um número
superior a 7 devemos pois usar outro tipo de variável, por exemplo long int (consulte-se o
manual da distribuição do PASCAL).
7.2 – Estrutura REPETIR-ATÉ
A outra estrutura repetitiva condicional que vamos estudar é a REPETIR-ATÉ (repeatuntil), que possui a seguinte estrutura:
74
REPETIR
Lista de declarações
ATÉ condição
Note-se que a ‘lista de declarações’ é executada pelo menos uma vez, independentemente da
condição ser verdadeira ou falsa. Uma aplicação típica é o das listas de dados não vazias.
Uma vez mais, a ‘lista de declarações ’ deve conter instruções que possam modificar a
condição (sob pena de se entrar num ciclo infinito). Repare-se que a lista de declarações será
executada até que a condição seja verificada, isto é, quando a condição se verificar o ciclo
termina. Na Figura 41 pode verse o diagrama de fluxo correspondente.
Entrada
Processar informação
interior ao ciclo
Avaliar a
Condição de
Ciclo
Verdadeira
Falsa
Saída
Figura 41 – Diagrama de fluxo da estrutura REPETIR-ATÉ.
Ilustremos a utilização desta estrutura recorrendo ao exemplo anteriormente apresentado:
calcular a soma de um conjunto de números introduzidos pelo teclado e terminada pela
introdução do número –1. Desta vez a lista de números introduzidos não pode ser vazia, isto
é, o primeiro elemento não pode ser o número –1. O algoritmo seguinte apresenta a
componente principal de uma solução para o problema:
soma ß 0
REPETIR
LER(x)
soma ß soma + x
ATÉ x = –1
75
Note-se a negação da condição de paragem do ciclo (na estrutura REPETIR-ENQUANTO era
x ≠ –1 e agora é x = –1). A seguir apresenta-se a respectiva codificação em PASCAL:
soma := 0;
repeat
read(x);
soma := soma + x,
until x = –1
Repare-se que neste caso não é necessário utilizar as instruções begin-end para criar um bloco
de código. Verifique-se ainda que o valor ‘-1’ é somado ao resultado final. Como alteraria o
algoritmo de forma a não ser incluído?
É possível transformar uma estrutura do tipo REPETIR-ENQUANTO numa estrutura do
tipo REPETIR-ATÉ (fazendo com que a condição de controlo se verifique à primeira vez,
utiliando uma inicialização conveniente desta variável). O contrário é impossível.
O algoritmo seguinte ilustra uma vez mais a utilização desta estrutura através de uma
implementação do jogo da adivinha de um número entre 1 e 100.
ALGORITMO Adivinha
VARIÁVEIS n, numero, x DO TIPO INTEIRO
1. [Gerar um número aleatório entre 1 e 100]
numero ß GeraNumeroAleatorio(100)
2. [Ler numero do utilizador até adivinhar]
ESCREVER('Adivinhe um numero entre 1 e 100:')
nß1
REPETIR
ESCREVER(n, ': ')
LER(x)
SE x > numero ENTÃO
ESCREVER('Errou: Numero muito grande.')
76
SENÃO
SE x < numero ENTÃO
ESCREVER('Errou: Numero muito pequeno.')
SENÃO
ESCREVER('Acertou no número ',numero, ‘ em ',n, ' tentativas.')
FIM SE
FIM SE
nßn+1
ATÉ x = numero
3. FIM DO ALGORITMO
As variáveis ‘n’, ‘numero’ e ‘x’ servem para guardar o número de tentativas, o número a
adivinhar e o valor da tentativa actual, respectivamente. Repare-se que o processo aleatório de
escolha do número entre 1 e 100 é automático. Isto é devido ao facto de na maioria das
linguagens de programação existirem instruções que o permitem fazer de uma forma simples
e eficiente. Como se pode ver no código seguinte, em PASCAL, estas instruções são
‘randomize’ para inicialização do sistema gerador, e ‘random’ que retorna um número
aleatório entre 0 o número apresentado entre parêntesis.
program Adivinha;
var numero, x, n: integer;
begin
{Gerar um número aleatório entre 1 e 100}
randomize;
numero := random(100)+1;
{Ler numero do utilizador até adivinhar}
writeln('Adivinhe um numero entre 1 e 100:');
n := 1;
repeat
77
write(n, ': ');
readln(x);
if x > numero then
writeln('Errou: Numero muito grande.')
else
if x < numero then
writeln('Errou: Numero muito pequeno.')
else
writeln('Acertou no numero ',numero, ' em ',n, 'tentativas.');
n := n + 1;
until x = numero
end.
7.3 – Entrada de dados através de ciclos
Como foi visto nos exemplos anteriores, os ciclos constituem um meio por excelência
para a entrada condicional de dados. Na disciplina apenas abordaremos a entrada de dados via
teclado, mas os princípios aqui apresentados são válidos para a entrada de dados através de
ficheiros ou outros dispositivos de entrada. Tal como já foi dito anteriormente, as listas de
dados podem ser ou não garantidamente não vazias. Dependendo da situação, usaremos
algoritmos baseados na estrutura REPETIR-ENQUANTO (as listas podem ser vazias) ou na
estrutura REPETIR-ATÉ (listas de dados não vazias). Os diagramas de fluxo apresentados na
Figura 42 e na Figura 43 mostram-nos os principais algoritmos.
78
Entrada
Inicializar a variável de
controlo para o primeiro
elemento da lista
Não
O valor actual da
variável de
controlo de ciclo
é maior do que o
valor final
estabelecido?
Processar as instruções
interiores ao ciclo
Sim
Afectar a variável de controlo
de ciclo com o próximo
elemento da lista
Figura 42 – Diagrama de fluxo para entrada de dados (lista não vazia).
Entrada
Inicializar a variável de
controlo para o primeiro
elemento da lista
O valor actual da
variável de
controlo de ciclo
é maior do que o
valor final
estabelecido?
Afectar a variável de controlo
de ciclo com o próximo
elemento da lista
Sim
Processar as instruções
interiores ao ciclo
Não
Figura 43 – Diagrama de fluxo para entrada de dados (lista vazia).
7.4 – Ciclos contados
A última estrutura repetitiva que vamos abordar é a REPETIR-PARA. Neste tipo de
estrutura o conjunto de instruções/operações é repetido um número fixo de vezes, número este
79
estabelecido à entrada no ciclo. Contrariamente ao que acontecia para as estruturas REPETIRENQUANTO e REPETIR-ATÉ, aqui não é testada nenhuma condição a fim de determinar se
o conjunto de operações interiores ao ciclo é ou não efectuado.
Para as estruturas REPETIR-ENQUANTO e REPETIR-ATÉ as instruções no intervalo
são repetidos tantas vezes quantas a condição expressa for verdadeira ou falsa. Esta condição
pode ser a avaliação de um valor que é lido dentro do ciclo (neste caso estamos na presença
de ciclos condicionais controlados por entrada). A condição pode também ser uma
composição de condições, utilizando os operadores negação, conjunção e disjunção.
Por seu lado, nos ciclos contados as instruções no intervalo são repetidas um número de
vezes bem determinado, dado pela expressão (|valor_inicial – valor_final | div y) + 1, onde y
representa o valor a somar ou a descontar em cada repetição do ciclo. Estes ciclos possuem o
seguinte formato
REPETIR PARA indice ß valor_inicial ATÉ valor_final COM PASSO y
lista_declarações
FIM REPETIR
Repare-se que é atribuído à variável ‘indice’ um valor inicial valor_inicial através de uma
operação de atribuição. A este valor será adicionado o valor de y até ser atingido o valor final
valor_final. O conjunto de operações constantes da lista de declarações será executado um
número de vezes fixo, determinado pelos valores valor_inicial, valor_final e y. Repare-se
ainda que y pode ser um valor negativo. Sempre que o passo assuma o valor 1 pode ser
omitida a sua declaração, isto é, se não se disser nada a variável y assume o valor 1. A
variável de controlo de ciclo ‘indice’ pode ser usada em expressões dentro da lista de
declarações, mas o seu valor não deve ser alterado, uma vez que é esta variável quem
determina a paragem ou continuação da repetição do ciclo. Em PASCAL esta estrutura pode
assumir duas formas:
FOR indice := valor_inicial TO valor_final DO
ou
FOR indice := valor_inicial DOWNTO valor_final DO
No primeiro caso a variável de controlo de ciclo ‘indice’ será incrementada de uma unidade
por cada vez que o ciclo se repete (o valor de y é sempre 1). Neste caso o valor valor_inicial é
80
menor que o valor valor_final. No segundo caso a variável de controlo de ciclo ‘indice’ será
decrementada de uma unidade por cada vez que o ciclo se repete (o valor de y é sempre –1).
Neste caso o valor valor_inicial é maior que o valor valor_final.
Pode-se desenhar um algoritmo para o cálculo do factorial de um número N baseado
nesta estrutura. A parte principal do algoritmo será
fact ß 1;
REPETIR PARA i ß 1 ATÉ N
fact ß i*fact
FIM REPETIR
e em PASCAL
fact:=1;
for i:=1 to N do
fact:=i*fact;
O algoritmo seguinte apresenta a tabuada (de 1 a 10) de um número introduzido pelo
teclado. Neste algoritmo a variável ‘numero’ guarda o valor introduzido pelo teclado, isto é, o
número do qual se pretende determinar a tabuada. A variável ‘i’ é usada como variável de
controlo de ciclo na estrutura REPETIR-PARA.
ALGORITMO Tabuada
VARIÁVEIS numero, i DO TIPO INTEIRO
1. [Ler numero da tabuada]
ESCREVER('Qual o número para o qual quer calcular a tabuada? ')
LER(numero)
2. [Calcular a tabuada de 1 a 10 para o numero lido]
ESCREVER('Tabuada do ', numero)
REPETIR PARA i ß 1 ATÉ 10
ESCREVER(numero,' * ',i,' = ', numero * i)
FIM REPETIR
81
3. FIM DO ALGORITMO
A sua codificação em PASCAL é
program tabuada;
var numero, i : integer;
begin
{Ler numero da tabuada}
write('Qual o número para o qual quer calcular a tabuada? ');
readln(numero);
{Calcular a tabuada de 1 a 10 para o numero lido}
writeln('Tabuada do ', numero);
for i:=1 to 10 do
writeln(numero,' * ',i,' = ', numero * i)
end.
Assim como era possível ter uma construção SE-ENTÃO-SENÃO dentro de outra
estrutura SE-ENTÃO-SENÃO, também é possível ter um ciclo no interior de outro ciclo. A
construção interna deve ser completamente “encaixada” na construção externa. O seguinte
algoritmo ilustra este conceito, determinando as tabuadas dos números de 1 a 10. Neste
algoritmo, a variável ‘i’ determina o número para o qual se está a calcular a tabuada.
ALGORITMO Tabela da tabuada
VARIÁVEIS i, j do tipo inteiro
1. [Cria 1ª linha da tabela]
REPETIR PARA j ß 1 ATÉ 10
ESCREVER(j, ‘
’)
FIM REPETIR
2. [Cria as seguintes 10 linhas da tabela]
REPETIR PARA i ß 1 ATÉ 10
ESCREVER(i, ‘
’)
82
REPETIR PARA j ß 1 ATÉ 10
ESCREVER(i*j , ‘
’)
FIM REPETIR
FIM REPETIR
3. FIM DO ALGORITMO
A codificação em PASCAL é
program tabela_da_tabuada;
uses crt;
var i, j : integer;
begin
clrscr;
for j:=1 to 10 do
write(j :4);
for i:=1 to 10 do
begin
writeln;
write(i :4);
for j:=1 to 10 do
begin
write(i*j :4)
end
end
end.
Neste momento convém esclarecer algumas situações particulares respeitantes à
codificação. A instrução ‘uses crt’ é utilizada para indicar ao compilador de PASCAL que
iremos utilizar funções que estão de algum modo relacionadas com o écran (Cathode Ray Tub
83
– CRT, veja-se a secção 4.4.5). Iremos utilizar a instrução ‘clrscr’ (limpar o écran). Note-se
ainda que a utilização da instrução ‘writeln’ sem qualquer argumento (sozinha) tem por
objectivo ‘saltar’ uma linha no écran. Nas instruções ‘write’ surge o argumento ‘:4’, por
exemplo ‘write(i*j :4)’. Isto indica ao compilador que deve usar no mínimo o espaço
correspondente a 4 caracteres para a parte inteira do número, quando escrever o resultado no
écran, mesmo que não seja necessário. Também é possível indicar um argumento deste tipo
referente à parte decimal do número, no caso de números do tipo real (por exemplo
‘write(x:4:2)’, correspondendo a utilizar 4 casas inteiras e 2 decimais). Estas técnicas são
usadas para dar um aspecto mais ordenado à forma como os dados são apresentados no écran
– neste exemplo a tabuada deve aparecer com o seu aspecto tradicional de tabela.
84
8 – Subalgoritmos – funções e procedimentos
Tal como já foi notado anteriormente, um problema complexo é mais fácil de resolver se
o dividirmos em pequenos sub-problemas. Os sub-algoritmos ou subprogramas destinam-se
principalmente a:
•
Permitir a criação de rotinas ou partes de código que podem ser usadas mais do
que uma vez no programa;
•
Estruturar melhor o programa;
•
Escrever determinadas porções de código de uma forma mais autónoma;
•
Construir programas de leitura, compreensão e correcção mais fáceis.
A utilização de subprogramas afecta o controlo de fluxo num algoritmo. Quando se dá a
chamada a um subprograma, a sequência de operações do programa passa para o subprograma
em questão até que este termine. Em seguida, a sequência de operações é retomada no ponto
logo a seguir onde essa chamada foi feita. A Figura 44 ilustra este processo.
Programa
Principal
•
•
•
Controlo transferido para a função sqrt
Função sqrt
Instruções
definindo a
função
Controlo devolvido ao programa principal
Val ← sqrt(x) + sqr(x)
•
•
•
Controlo devolvido ao programa principal
Função sqr
Instruções
definindo a
função
Controlo transferido para a função sqr
Figura 44 – Ilustração do processo de ‘passagem de controlo de fluxo ’.
8.1 – Parâmetros e argumentos
Em muitos casos, os subprogramas aceitam parâmetros – elementos que permitem passar
dados ou valores do programa ao subprograma e, eventualmente, também no sentido contrário
– o que lhes confere uma grande flexibilidade de utilização em situações diferenciadas.
85
Esta necessidade já foi observada quando vimos as funções pré-definidas. Como vimos,
estas funções já se encontram definidas e implementadas (e.g., sin, cos, abs, sqrt, sqr). São
utilizadas directamente em expressões como se fossem variáveis regulares. Por exemplo:
valor ß sin(angulo) + cos(angulo).
É da responsabilidade do programador fornecer o(s) argumento(s) (angulo, no exemplo
acima), sobre os quais a função opera para o cálculo do resultado de saída. No seguinte
excerto de algoritmo, as variáveis x e y são usadas como argumentos (de entrada) para a
função com nome ‘sqrt’ (que serve para calcular a raiz quadrada):
xß3
yß5
res1 ß sqrt(x) [determina a raiz quadrada de 3]
res2 ß sqrt(y) [determina a raiz quadrada de 5].
Neste momento convém fazer a distinção entre parâmetro e argumento. Os parâmetros
são identificadores inseridos no cabeçalho de definição dos subprogramas e são usados para
passar dados do programa principal para o subprograma e/ou vice versa. Podem ser usados
nas instruções operativas dos subprogramas. Tal como acontece com as variáveis, cada
parâmetro tem um tipo de dados associado a si. Geralmente, um subprograma recebe uma
lista de parâmetros, podendo esta lista ser nula.
Os argumentos são valores passados aos subprogramas em correspondência com os
parâmetros. Na altura em que é feita a chamada ao subprograma, é tida em consideração a
ordem dos argumentos, bem como o tipo de dados a que pertencem. Os argumentos utilizados
nas chamadas dos subprogramas podem ser valores directos, variáveis ou expressões, desde
que os valores sejam compatíveis no tipo de dado com os parâmetros correspondentes.
8.2 – Tipos de passagem de parâmetros
Existem dois métodos de associação entre argumentos e parâmetros:
•
Por cópia de valor (parâmetros de entrada);
•
Por referência (parâmetros de entrada/saída).
No primeiro caso, sempre que são feitas alterações nos parâmetros, dentro do subprograma,
essas alterações não resultam em mudanças nos argumentos correspondentes, isto porque os
86
parâmetros não estão ligados aos próprios argumentos (é feita uma cópia dos valores). No
segundo caso, as alterações efectuadas nos parâmetros, dentro do subprograma, reflectem-se
nos respectivos argumentos. É passada a própria variável (mais concretamente o seu endereço
de memória). Na codificação PASCAL utiliza-se a palavra-chave VAR para identificar este
tipo de parâmetros.
8.3 – Funções
Para além de utilizar as funções pré-definidas o programador pode definir as suas
próprias funções. Neste ponto veremos como se define uma função.
Em linguagem algorítmica, uma função define-se da seguinte forma:
FUNÇÃO nome (parâmetro1, parâmetro2, …, parâmetron)
TIPO DOS PARÂMETROS
VARIÁVEIS LOCAIS
Conjunto de instruções
RETORNAR(valor_de_saída)
O único valor que a função retorna é dado como uma expressão entre parêntesis a seguir à
palavra-chave RETORNAR. RETORNAR indica o ponto em que o controlo regressa ao
algoritmo principal, onde o valor devolvido pela função é então utilizado como parte da
expressão na qual a função se insere.
Vejamos um exemplo para melhor clarificar estes conceitos. Vamos supor que queremos
construir uma função para calcular g(x,y)=x2+y2.
ALGORITMO teste da função gdexy
FUNÇÃO gdexy(x, y)
PARÂMETROS DE ENTRADA x, y DO TIPO REAL
VARIÁVEIS LOCAIS res DO TIPO REAL
res ß sqr(x) + sqr(y)
RETORNAR (res)
87
VARIÁVEIS a, b, res DO TIPO REAL
aß5
bß3
res ß gdexy(a,b)
ESCREVER(res)
res ß gdexy(a * b+3 , 2)
ESCREVER(res)
FIM DO ALGORITMO
A função gdexy(x,y) possui dois parâmetros de entrada e para cada avaliação da função é
necessário o mesmo número de argumentos. É estabelecida uma correspondência entre os
parâmetros e os argumentos fornecidos à função. Quando fazemos res ß gdexy(a,b), a e b
são os argumentos. Ao parâmetro x corresponde o argumento a e ao parâmetro y corresponde
o argumento b. A ordem é crucial; gdexy(a,b) tem um resultado diferente de gdexy(b,a). A
codificação em PASCAL é:
program testa_func_gdexy;
function gdexy(x, y:real):real;
var res:real;
begin
res := sqr(x) + sqr(y);
gdexy := res
end;
var a, b, res:real;
begin
a := 5;
b := 3;
res := gdexy(a,b);
write(res);
88
res := gdexy(a * b+3 , 2);
write(res)
end.
Note-se que o valor calculado pela função é retornado afectando directamente o
identificador (nome) da função, ou seja, fazendo ‘gdexy := res’.
8.4 – Procedimentos
Embora o comportamento de uma função e de um procedimento seja similar no que diz
respeito à alteração do fluxo, da correspondência argumento/parâmetro e no conceito de
variáveis locais e variáveis globais, existem contudo duas diferenças fundamentais:
•
Um procedimento é chamado por meio do comando chamar;
•
Não existe retorno de um único valor como no caso da função. Qualquer valor a ser
retornado por um procedimento é devolvido através da lista de parâmetros. Podemos
retornar o número de parâmetros que desejarmos.
Os procedimentos definem-se da seguinte forma:
PROCEDIMENTO nome (parâmetro1, parâmetro2, …, parâmetron)
TIPO DOS PARÂMETROS DE ENTRADA
TIPO DOS PARÂMETROS DE ENTRADA/SAÍDA
VARIÁVEIS LOCAIS
Conjunto de instruções
RETORNAR
Ilustremos a utilização dos procedimentos. Pretende-se desenvolver um procedimento
que execute a divisão de dois valores inteiros e devolva como resultados o quociente e o resto
(da divisão inteira). Note-se que os parâmetros ‘dividendo’ e ‘divisor’ são passados por cópia
de valor, enquanto que os parâmetros ‘quociente’ e ‘resto’ são passados por referência
(porquê ?).
ALGORITMO testa procedimento divide
PROCEDIMENTO divide(dividendo, divisor, quociente, resto)
89
PARÂMETROS DE ENTRADA dividendo, divisor DO TIPO INTEIRO
PARÂMETROS DE ENTRADA/SAÍDA quociente, resto DO TIPO INTEIRO
quociente ß dividendo DIV divisor
resto ß dividendo MOD divisor
RETORNAR
VARIÁVEIS a, b, c, d DO TIPO INTEIRO
aß5
bß3
CHAMAR divide(a, b, c, d)
ESCREVER(c, d) [o que é que escreve no écran?]
CHAMAR divide(a*b , 2, c, d)
ESCREVER(c, d) [o que é que escreve no écran?]
FIM DE ALGORITMO
8.5 – Variáveis globais e variáveis locais
Quando uma variável é declarada na parte declarativa do programa principal, diz-se que é
uma variável global, ou que tem um alcance ou raio de acção global. Iisto quer dizer que é
reconhecida em todo o programa, não só na parte operativa do programa principal, mas
também dentro de qualquer subprograma.
Quando uma variável é declarada na parte declarativa de um subprograma então diz-se
que se trata de uma variável local ou que tem um raio de acção local. Isto implica que a
variável só é reconhecida dentro desse mesmo subprograma em que foi declarada.
Ilustremos estes conceitos recorrendo a um programa em PASCAL:
90
program testa_procedimento_divide(input,output);
uses crt;
procedure divisao(x,y:integer;var z,k:integer);
var b:integer; {variável local}
begin
b:=3;
a:=b+2;
z:=x div y;
k:=x mod y
parte operativa
Sub-programa
parte declarativa
{x, y passagem por copia de valor – z, k passagem por referência }
parte declarativa
var a:integer; {variável global}
end;
var dividendo,divisor,quociente,resto:integer; {variáveis locais}
clrscr;
parte operativa
dividendo:=8;
divisor:=3;
call divisao(dividendo,divisor,quociente,resto);{chamada do procedimento}
Programa principal
begin
writeln(quociente,resto);
repeat until keypressed {espera que uma tecla seja pressionada}
end.
Como se pode concluir do exemplo anterior, num algoritmo ou programa não se pode
dizer que existe uma parte declarativa e uma parte operativa, uma vez que nos subprogramas
também existem as duas partes. As variáveis ‘dividendo’, ‘divisor’, ‘quociente’ e ‘resto’ são
conhecidas apenas no programa principal (variáveis locais). A variável ‘b’ é conhecida apenas
no procedimento (variável local), enquanto que a variável ‘a’ é conhecida em todo o programa
(variável global).
91
8.6 – Subprogramas encaixados
Em certos casos, normalmente em programas com certa extensão e/ou complexidade, o
estilo de programação estruturada leva a incluir subprogramas dentro de outros subprogramas.
Tal como acontece com as variáveis locais, estes subprogramas só são “conhecidos” dentro
dos subprogramas onde são definidos.
O exemplo seguinte ilustra esta situação. Dada a margem de lucro e o custo de um artigo,
determinar o seu preço de venda ao público sabendo que a taxa de IVA a aplicar é de 19%.
ALGORITMO Etiquetagem
CONSTANTE IVA=19
VARIÁVEIS lucro, quantia DO TIPO REAL
FUNÇÃO pvp(custo)
PARÂMETROS DE ENTRADA custo DO TIPO REAL
RETORNA pvp DO TIPO REAL
VARIÁVEIS quantia DO TIPO REAL
FUNÇÃO pcIVA(preco)
PARÂMETROS DE ENTRADA preco DO TIPO REAL
RETORNA pcIVA DO TIPO REAL
VARIÁVEIS imposto DO TIPO REAL
imposto ß preco*IVA/100 [Cálculo do valor do IVA]
pcIVA ß preco+imposto [Calcular o P.V.P.]
RETORNA(pcIVA)
[Calcular o preço acrescido do lucro]
quantia ß custo*(100+lucro)/100
[Calcular o P.V.P.]
pvp ß pcIVA(quantia)
RETORNA(pvp)
[Ler lucro associado a cada produto]
92
ESCREVER('Percentagem de lucro (%): ')
LER(lucro)
[Ler custo dos artigos e escrever o seu p.v.p. até este ser nulo]
REPETIR
ESCREVER('Custo do artigo: ')
LER(quantia)
SE (quantia > 0) ENTÃO
ESCREVER('P.V.P. = ', pvp(quantia))
FIM DE SE
ATÉ quantia=0
FIM DO ALGORITMO
A codificação em PASCAL é:
program etiquetagem;
uses crt;
const IVA=19;
var lucro, quantia : real;
function pvp(custo: real): real;
var quantia: real;
function pcIVA(preco : real): real;
var imposto : real;
begin {Calcular o valor do IVA }
imposto:=preco*IVA/100; {Calcular o P.V.P.}
pcIVA:=preco+imposto;
end;
begin {Calcular o preco acrescido do lucro}
quantia:=custo*(100+lucro)/100;
93
{Calcular o P.V.P.}
pvp:=pcIVA(quantia)
end;
begin
{Ler lucro associado a cada produto}
write('Percentagem de lucro (%): ');
readln(lucro);
{Ler custo dos artigos e escrever o seu p.v.p. até ler custo nulo}
repeat
write('Custo do artigo: ');
readln(quantia);
if (quantia > 0) then
writeln('P.V.P. = ', pvp(quantia));
until quantia=0;
repeat until keypressed {espera que uma tecla seja pressionada}
end.
94
9 – Vectores e matrizes
Até ao momento estudámos dados simples ou não estruturados. Como já foi visto, os
dados simples ou não estruturados, dividem-se em:
•
Ordinais;
•
Inteiros;
•
Caracteres;
•
Lógicos;
•
Reais.
Vimos que as variáveis ou dados simples permitem guardar apenas um valor (de cada
vez). Como iremos ver, os dados estruturados permitem-nos uma maior flexibilidade de
programação. Os dados estruturados englobam:
•
Arrays (vectores e matrizes);
•
Registos ou records.
Iremos começar por estudar os dados estruturados do tipo array. Um array agrupa numa
mesma variável um conjunto de valores do mesmo tipo. Uma variável deste tipo é designada
por um identificador, mas cada elemento tem um ou mais índices associados.
Os arrays podem ser:
•
Unidimensionais, designando-se vulgarmente por vectores, os quais possuem um
único índice;
•
Multidimensionais, designando-se vulgarmente por matrizes, os quais possuem
um número de índices igual ao número de dimensões da matriz.
9.1 – Arrays unidimensionais – Vectores
É comum pensar-se num array do ponto de vista gráfico, associando-o à representação
feita pela álgebra linear de vector ou matriz, consoante o caso. Na Figura 45 pode ver-se a
interpretação gráfica associada ao vector.
95
A3 45
A4 13
A5 32
Vector coluna
A1 10
A2 12
10
A1
Vector linha
12 45 13 32
A2 A3 A4 A5
Figura 45 – Interpretação gráfica de vector.
A sintaxe algorítmica usada para definir um vector é a seguinte:
VARIÁVEIS
nome[número de elementos do vector] DO TIPO VECTOR DE tipo
Tal como anteriormente, nome designa o identificador pelo qual o vector será conhecido.
Depois do nome, e entre parêntesis rectos, devemos indicar o número de elementos do vector.
Finalmente devemos indicar que esta variável é do tipo vector e o tipo de dados de cada
elemento, isto é, cada elemento do vector é do tipo tipo. Vejamos alguns exemplos:
•
v[10] DO TIPO VECTOR DE REAIS, define um vector chamado v com 10
elementos do tipo real;
•
u[6] DO TIPO VECTOR DE CARACTERES, define um vector chamado u com
6 elementos do tipo caracter.
Em PASCAL as definições devem ser feitas da seguinte forma:
VAR nome : ARRAY[intervalos dos índices] OF tipo
Os exemplos anteriores definem-se como:
•
v: array[1..10] of real
•
u: array[1..6] of char.
Usando notação algorítmica, o acesso a um elemento particular de um vector é feito da
seguinte forma:
•
v[3] ß 4
•
u[2] ß ‘c’
•
a ß v[10]
96
•
ESCREVER(u[2])
•
Para i = 3, usando v[i] acedemos ao terceiro elemento do vector v.
Vejamos um exemplo concreto de aplicação de vectores. Suponhamos que a empresa
K3K pretende manipular os dados relativos às despesas em cada um dos 12 meses do ano. A
estrutura de dados deve ser definida da seguinte forma:
•
VARIÁVEIS
despesas[12]
DO
TIPO
VECTOR
DE
REAIS
(notação
algorítmica);
•
Var despesas: array[1..12] of real (PASCAL).
A introdução ou leitura dos valores é feita da seguinte forma:
(em notação algorítmica)
REPETIR PARA i ß 1 ATÉ 12
LER(despesas[i])
FIM REPETIR
(em PASCAL)
for i:=1 to 12 do
read(despesas[i]);
A apresentação no écran de todos os valores:
(em notação algorítmica)
REPETIR PARA i ß 1 ATÉ 12
ESCREVER(despesas[i])
FIM REPETIR
(em PASCAL)
for i:=1 to 12 do
writeln(despesas[i]);
O algoritmo seguinte, lê as despesas do ano e calcula a despesa média. Na segunda parte do
algoritmo, verifica-se para cada mês se as despesas foram superiores ou inferiores à média.
97
ALGORITMO despesa_media
VARIÁVEIS despesas[12] DO TIPO VECTOR DE REAIS
i DO TIPO INTEIRO
total_ano, media_ano DO TIPO REAL
total_ano ß 0
REPETIR PARA i ß 1 ATÉ 12
LER(despesas[i])
total_ano ß total_ano + despesas[i]
FIM REPETIR
media_ano ß total_ano/12
REPETIR PARA i ß 1 ATÉ 12
SE despesas[i] > media_ano ENTÃO
ESCREVER(’Despesas acima da média')
SENÃO
ESCREVER(’Despesas abaixo da média')
FIM SE
FIM REPETIR
FIM ALGORITMO
A função seguinte devolve as despesas para o mês i:
FUNÇÃO consulta(despesas, i)
PARÂMETROS DE ENTRADA:
despesas DO TIPO VECTOR DE REAIS
i DO TIPO INTEIRO
RETORNAR(despesas[i])
A seguinte função devolve o total das despesas para os n primeiros meses:
FUNÇÃO soma_n(despesas,n)
98
PARÂMETROS DE ENTRADA:
despesas DO TIPO VECTOR DE REAIS
n DO TIPO INTEIRO
VARIÁVEIS:
soma DO TIPO REAL
i DO TIPO INTEIRO
soma ß 0
REPETIR PARA i ß 1 ATÉ n
soma ß soma + despesas[i]
FIM REPETIR
RETORNAR(soma)
Este procedimento insere na posição i do vector despesas o valor x.
PROCEDIMENTO insere(despesas, i, x)
PARÂMETROS DE ENTRADA:
i DO TIPO INTEIRO
x DO TIPO REAL
PARÂMETROS DE ENTRADA SAÍDA:
despesas DO TIPO VECTOR DE REAIS
despesas[i] ß x
RETORNAR
O procedimento seguinte recebe o vector com as despesas e devolve o mês em que houve
maiores despesas e o respectivo valor.
PROCEDIMENTO maior_gasto(despesas, mes, valor)
PARÂMETRO DE ENTRADA:
despesas DO TIPO VECTOR DE REAIS
PARÂMETRO DE ENTRADA SAÍDA:
99
mês DO TIPO STRING
valor DO TIPO REAL
VARIÁVEIS:
i, max DO TIPO INTEIRO
max ß 1
valor ß despesas[1]
REPETIR PARA i ß 2 ATÉ 12
SE despesas[i] > valor ENTÃO
valor ß despesas[i]
max ß i
FIM SE
FIM REPETIR
CASO max POSSUA VALOR
1: mes ß 'Janeiro'
2: mes ß 'Fevereiro'
3: mes ß 'Março'
4: mes ß 'Abril'
5: mes ß 'Maio'
6: mes ß 'Junho'
7: mes ß 'Julho'
8: mes ß 'Agosto'
9: mes ß 'Setembro'
10: mes ß 'Outubro'
11: mes ß 'Novembro'
12: mes ß 'Dezembro'
FIM CASO
100
RETORNAR
Como exercício, sugere-se o desenvolvimento de um algoritmo ou programa que
implemente as funcionalidades implícitas no menu seguinte:
1 – Introduzir despesas (12 meses)
2 – Introduzir despesa para o mês i
3 – Consultar despesa total
4 – Consultar despesas do mês i
5 – Despesa méida
6 – Maior despesa
0 – Sair (terminar) do programa.
9.1.1 – Tratamento de strings ou cadeias de caracteres como arrays unidimensionais
Um dado do tipo string que tenha um determinado número de caracteres pode ser tratado
como um array unidimensional (vector) de elementos do tipo caracter ou char.
Por exemplo, o seguinte programa, codificado em PASCAL, lê uma palavra constituída
por seis caracteres e conta o número de vogais dessa palavra.
program vogal;
uses crt;
var
palavra : string[6];
i,conta:integer;
begin
clrscr;
writeln('Insira a palavra: ');
readln(palavra);
conta:=0;
for i:=1 to 6 do
if palavra[i] in ['a','e','i','o','u'] then
101
conta:=conta+1;
writeln(‘O número de vogais na palavra ’, palavra, ‘ é ’, conta);
repeat until keypressed
end.
Repare-se atentamente na expressão ‘palavra[i] in ['a','e','i','o','u']’. Esta expressão constitui a
parte central do programa, pois ela permite avaliar de uma forma semi-automática, quais os
caracteres que pertencem ao conjunto das vogais. Se não fosse possível utilizar esta
construção em PASCAL poderíamos usar algo semelhante:
If ((palavra[i]=‘a’) or (palavra[i]=‘e’) or (palavra[i]=‘i’) or
(palavra[i]=‘o’) or (palavra[i]=‘u’)) then
conta:=conta+1;
9.2 – Arrays bidimensionais ou matrizes
É possível definir um array de arrays, o que equivale a falar em arrays
multidimensionais. Se considerarmos um array bidimensional (matriz), podemos facilmente
representá-la como uma tabela ou quadro de duas entradas, em que se atribui um índice às
colunas e outro índice às linhas, à imagem do que é sugerido pela álgebra (veja-se a Figura
46).
A11
10
A12
13
linha 2
A21
22
A22
33
linha 3
A31
91
A32
23
linha 1
A linha, coluna ≡ A[linha, coluna]
coluna 1 coluna 2
Figura 46 – Interpretação geométrica de array bidimensional.
A sintaxe algorítmica para definição de uma matriz é a seguinte:
VARIÁVEIS nome[número de linhas, número de colunas] DO TIPO MATRIZ DE tipo
102
Note-se a existência de dois índices: o primeiro associado ao número da linha da matriz; e o
segundo ao número da coluna. Uma vez mais aconselhamos a observação da Figura 46.
Vejamos alguns exemplos de definições de matrizes:
•
v[3,4] DO TIPO MATRIZ DE REAIS, define uma matriz com três linhas e quatro
colunas, com elementos do tipo real (totalizando doze elementos);
•
u[6,6] DO TIPO MATRIZ DE CARACTERES, define uma matriz de seis linhas
e seis colunas, com elementos do tipo caracter (totalizando trinta e seis
elementos).
Em PASCAL as matrizes definem-se da seguinte forma:
VAR nome : ARRAY[número de linhas, número de colunas] OF tipo
Os exemplos anteriores definem-se da seguinte forma:
•
v : array[1..3,1..4] of real;
•
u : array[1..6,1..6] of char.
Numa estrutura deste tipo, os dados podem ser carregados utilizando ciclos encaixados. Em
notação algorítmica
REPETIR PARA i ß 1 ATÉ numero_de_linhas
REPETIR PARA j ß 1 ATÉ numero_de_colunas
LER(a[i, j])
FIM REPETIR
FIM REPETIR
A variável i é usada para índice das linhas e a variável j é usada para índice das colunas. Em
PASCAL isto é equivalente a termos
for i:=1 to numero_de_linhas do
for j:=1 to numero_de_colunas do
read(a[i,j]);
Desenvolvendo o exemplo da empresa K3K, suponhamos que além de guardar as
despesas dos meses também se desejava guardar as receitas obtidas em cada um dos doze
meses do ano. Neste caso a informação podia ser guardada numa matriz bidimensional, de
103
nome ‘despesas’, com as dimensões de 12 linhas (meses) por 2 colunas (despesas e receitas).
Alternativamente podia-se definir ‘despesas’ como possuindo 2 linhas (correspondentes às
receitas) e 12 colunas (correspondentes aos meses). A estrutura de dados é declarada da
seguinte forma (assume-se que a primeira coluna corresponde às despesas e a segunda às
receitas):
(linguagem algorítmica)
VARIÁVEIS despesas[12,2] DO TIPO MATRIZ DE REAIS
(em PASCAL)
VAR despesas : ARRAY[1..12,1..2] OF REAL
A atribuição de um valor é feita da seguinte maneira:
(linguagem algorítmica)
despesas[3,1] ß 5000
(em PASCAL)
despesas[3,1] := 5000
A apresentação no écran de todos os valores é feita da seguinte forma
(linguagem algorítmica)
REPETIR PARA i ß 1 ATÉ 12
REPETIR PARA j ß 1 ATÉ 2
ESCREVER(despesas[i,j])
FIM DE REPETIR
FIM DE REPETIR
(em PASCAL)
for i:=1 to 12 do
for j:=1 to 2 do
writln(despesas[i,j]);
Por seu lado, a leitura de todos os valores é feita utilizando
(linguagem algorítmica)
104
REPETIR PARA i ß 1 ATÉ 12
REPETIR PARA j ß 1 ATÉ 2
LER(despesas[i,j])
FIM DE REPETIR
FIM DE REPETIR
(em PASCAL)
for i:=1 to 12 do
for j:=1 to 2 do
read(despesas[i,j])
A função abaixo calcula as despesas ao longo de um ano
FUNÇÃO gasto(despesas)
PARÂMETROS DE ENTRADA:
despesas DO TIPO MATRIZ DE REAIS
VARIÁVEIS i DO TIPO INTEIRO
total DO TIPO REAL
total ß 0
REPETIR PARA i ß 1 ATÉ 12
total ß total +despesas[i,1]
RETORNAR(total)
9.3 – Arrays multidimensionais
Existem aplicações onde se pode utilizar estruturas tridimensionais, que são
representadas por conjuntos de três índices. Por exemplo, na análise de sequências de imagens
pode ser usada uma estrutura deste tipo, onde ao primeiro índice se associa o número da
imagem na sequência, ao segundo, o número da linha naquela imagem e ao terceiro, o número
da coluna naquela imagem.
105
Embora seja possível ter conjuntos com mais de três índices, é difícil ilustrá-los com
exemplos reais, sendo apenas utilizados em aplicações muito específicas.
106
10 – Pesquisa e ordenação com vectores
Pesquisar um vector consiste basicamente em percorrer os seus elementos a fim de
localizar um item desejado.
Ordenar ou classificar um vector é a operação de arranjar os seus elementos numa ordem
sequencial, utilizando um critério de seriação.
Existem vários métodos de pesquisa e ordenação. Dadas as características introdutórias
que revestem esta disciplina, iremos abordar apenas dois métodos de ordenação: ordenação
por selecção (selection sort); e ordenação por borbulhamento (bobble sort).
10.1 – Ordenação ou classificação
Tal como já foi dito, vamos estudar a classificação pelos métodos de:
•
Selecção (selection sort);
•
Borbulhamento (bobble sort).
Nestes métodos assume-se que lidamos com vectores de N elementos e pretendemos
ordená-los por ordem ascendente. Os princípios usados serão os mesmos se pretendermos
ordenar o vector por ordem descendente.
10.1.1 – Ordenação por selecção
O algoritmo de ordenação/classificação por selecção consiste nos seguintes passos:
1. Partindo do primeiro elemento do vector faz-se uma pesquisa para localizar o
elemento com menor valor;
2. Este elemento é permutado com o primeiro elemento do vector (esta troca coloca o
elemento com o menor valor na primeira posição do vector);
3. Executa-se uma pesquisa para o segundo menor valor; isto é feito pelo exame dos
valores de cada elemento a partir da segunda posição;
4. O elemento encontrado é permutado com o situado na segunda posição do vector;
5. Repetem-se os passos de pesquisa do n-ésimo menor elemento (correspondente ao
ponto 3.) e permuta deste elemento com o elemento na n-ésima posição no vector
107
(correspondente ao ponto 4.) até que todos os elementos tenham sido colocados
por ordem ascendente.
Se o vector possui N elementos são necessárias N – 1 passagens para o ordenar (a última
passagem não é necessária).
O seguinte algoritmo ordena um vector V de N elementos por ordem ascendente
utilizando este método.
VARIÁVEIS indice_min, passagem, l DO TIPO INTEIRO
1. [Executa N-1 passagens]
REPETIR PARA passagem ß 1 ATÉ N-1
2. [Inicializa o índice do mínimo]
indice_min ß passagem
3.[Executa uma passagem e obtém o índice do elemento com menor valor]
REPETIR PARA l ß passagem+1 ATÉ N
SE V[l] < V[indice_min] ENTÃO
indice_min ß l
FIM SE
FIM REPETIR
SE indice_min ≠ passagem ENTÃO
troca(V[passagem],V[indice_min])
FIM SE
FIM REPETIR
FIM ALGORITMO
A variável ‘passagem’ indica ou guarda o número da passagem actual, isto é, quantos
elementos do vector já se encontram ordenados. A variável ‘indice_min’ guarda a posição no
vector onde se encontra o elemento mais pequeno. A variável ‘l’ é usada para percorrer o
vector desde a posição indicada por ‘passagem’ até ao penúltimo elemento do vector (no final
de N – 1 passagens, o último elemento do vector será por certo o maior). Note-se ainda que só
108
é necessário efectuar a troca dos elementos do vector se por acaso o elemento actual não for o
mais pequeno.
10.1.2 – Ordenação por borbulhamento
Ao contrário do que acontece com o método de classificação por selecção, em que
primeiro se encontra o elemento com menor valor e só depois se efectua a troca, neste caso
dois elementos são trocados imediatamente após a descoberta de que eles estão fora de ordem.
São requeridas, no máximo, N – 1 passagens. O funcionamento do método é o seguinte:
1. Durante a primeira passagem, V[1] e V[2] são comparados e se estão fora de
ordem, são permutados;
2. Isto é repetido para os pares de elementos (V[2];V[3]), (V[3];V[4]), (...),
(V[i];V[i+1]). O método leva os elementos com maior valor a “borbulharem” para
o fim do vector. Após a primeira passagem, o elemento com maior valor ocupará
a posição N.
3. Em cada passagem sucessiva, os elementos com os valores imediatamente mais
baixos serão colocados nas posições N – 1, N – 2, N–3, ..., 3, 2, 1.
4. É feita uma verificação para ver se houve alguma troca de valores durante cada
passagem. Se não houve trocas durante a passagem, o vector encontra-se
classificado, não sendo necessárias mais passagens.
O algoritmo seguinte implementa este método.
VARIÁVEIS flag DO TIPO LÓGICO
i,j DO TIPO INTEIRO
iß1
flag ß verdade
REPETIR ENQUANTO (i ≤ N-1) E (flag=verdade)
flag ß falso
REPETIR PARA j ß 1 ATÉ N – i
SE V[j+1]<V[j] ENTÃO
troca(V[i],V[j])
109
flag ß verdade
FIM SE
FIM REPETIR
i ß i+1
FIM REPETIR
FIM ALGORITMO
A variável ‘flag’ é usada como marca para detectar se houve trocas ou não (daí o colocar-se
esta marca a verdadeiro quando existem trocas). Por outro lado, não havendo trocas o vector
encontra-se ordenado, permitindo a sua finalização. A condição de saída do ciclo REPETIRENQUANTO pode ser relaxada (simplificada), passando de ‘(i ≤ N-1) E (flag=verdade)’
simplesmente para ‘flag=verdade’ (porquê?). Alternativamente pode usar-se o seguinte
algoritmo, deixando a sua explicação como exercício:
VARIÁVEIS flag DO TIPO LÓGICO
i,j DO TIPO INTEIRO
iß1
REPETIR
flag ß falso
REPETIR PARA j ß 1 ATÉ N – i
SE V[j+1]<V[j] ENTÃO
troca(V[i],V[j])
flag ß verdade
FIM SE
FIM REPETIR
i ß i+1
ATÉ flag=falso
FIM ALGORITMO
110
Antes de passarmos ao ponto seguinte convém deixar ficar uma nota acerca da função
‘troca(a,b)’ utilizada nestes três últimos algoritmos. Esta função, tal como o seu nome sugere,
tem por objectivo trocar os conteúdos das variáveis a e b. Para isso torna-se necessária a
utilização de uma variável intermédia auxiliar, que guarde temporariamente um dos valores.
O código principal terá o seginte aspecto:
aux ß a
aßb
b ß aux
Nos exemplos vistos até ao momento, o vector ‘V’ possui dados não estruturados ou simples.
Isto que dizer que em cada elemento do vector apenas é guardado um tipo de dado. Como
iremos ver mais adiante (secção 0), se o tipo de dados for estruturado, num único elemento do
vector são guardados vários tipos de dados. Nesta situação, deve-se ‘trocar’ não só os dados
pelos quais estamos a efectuar a ordenação, mas também todos os outros que estão associados
aos elementos em causa do vector. Quando a linguagem de implementação é o PASCAL esta
observação tende a passar despercebida. Contudo, em linguagens como o C pode ser a causa
de várias horas de pesquisa ‘à procura do erro!’.
10.2 – Pesquisa
Embora existam várias técnicas amplamente usadas para pesquisar um elemento num
vector (verificar a existência ou não de um dado elemento), pelos motivos anteriormente
apresentados, estudaremos apenas duas técnicas:
•
Pesquisa linear;
•
Pesquisa binária.
10.2.1 – Pesquisa linear
A pesquisa linear envolve a verificação sequencial de cada elemento do vector até que o
elemento desejado seja encontrado.
Dado um vector V, ordenado ou não, com N elementos (N ≥ 1) o algoritmo seguinte
procura no vector um elemento particular cujo valor é x.
VARIÁVEIS
flag DO TIPO LÓGICO
111
i DO TIPO INTEIRO
iß1
flag ß falso
REPETIR ENQUANTO (i ≤ N) E (flag=falso)
SE V[i]=x ENTÃO
flag ß verdade
FIM SE
i ß i+1
FIM REPETIR
SE flag = verdade ENTÃO
ESCREVER('Valor encontrado na posição', i-1)
SENÃO
ESCREVER('Valor não encontrado')
FIM SE
FIM ALGORITMO
Caso o elemento seja encontrado a marca ‘flag’ é colocada a verdadeiro, permanecendo a
falso caso o elemento não exista no vector. Note-se que com uma ligeira modificação do
algoritmo, a pesquisa pode ser iniciada do último para o primeiro elemento do vector.
10.2.2 – Pesquisa binária
Vamos assumir que os N elementos do vector estão armazenados por ordem ascendente.
Um raciocínio idêntico é aplicável se o vector estiver ordenado por ordem descendente. O
algoritmo é o seguinte:
1. O meio do vector pode ser calculado e o seu valor é examinado.
2. Se o valor for mais alto, então o elemento do meio da primeira metade é
examinado, passando esta metade do intervalo a ser considerada como vector de
partida;
112
3. Se o valor for mais baixo então o elemento do meio da segunda metade é tentado,
passando esta metade do intervalo a ser considerada como vector de partida;
4. Repete-se desde 1. até que o valor desejado seja encontrado ou o intervalo de
pesquisa seja vazio.
Dado um vector V de N elementos ordenado por ordem crescente, o algoritmo seguinte
implementa o processo anterior para a pesquisa de um dado elemento x. As variáveis ‘alto’ e
‘baixo’ servem para indicar o intervalo de pesquisa (o primeiro e o último elemento do
intervalo). A variável ‘medio’ é usada para guardar a posição média do intervalo (o elemento
do meio do intervalo baixo-alto). A variável ‘flag’, quando no estado verdadeiro, assinala o
facto de se ter encontrado o elemento pretendido.
VARIÁVEIS
flag DO TIPO LÓGICO
alto, medio, baixo DO TIPO INTEIRO
baixo ß 1
alto ß N
flag ß falso
REPETIR ENQUANTO (baixo < alto) E (flag=falso)
medio ß (alto-baixo)/2
SE x < V[medio] ENTÃO
alto ß medio -1
SENÃO
SE x > V[medio] ENTÃO
Baixoß medio+1
SENÃO
flag ß verdade
FIM SE
FIM SE
FIM REPETIR
113
SE (baixo=alto) E (x=v[baixo]) ENTÃO
flag = verdade
medio = baixo
FIM SE
SE flag=verdade ENTÃO
ESCREVER('pesquisa bem sucedida na posição', medio)
SENÃO
ESCREVER('pesquisa mal sucedida.')
FIM SE
FIM ALGORITMO
Repare-se na existência da estrutura ‘SE (baixo=alto) E (x=v[baixo]) ENTÃO’. Esta
declaração é usada para indicar esta posição como solução no caso limite dos extremos do
intervalo se tocarem e este valor corresponder ao valor procurado. Repare-se que pode
relaxar-se a condição desta estrutura simplesmente para ‘SE x=v[baixo] ENTÃO’, uma vez
que o extremo esquerdo do intervalo pode corresponder ao local onde se encontra o valor
pretendido. Este caso só é verificado quando o extremo direito coincide com o esquerdo.
Neste caso o ponto médio do intervalo é baixo-alto=0 (daí a necessidade de ser tratado de
forma independente, i.e., fora do ciclo ‘REPETIR-ENQUANTO’.
114
11 – Registos e arrays de registos
Até agora discutimos a utilização de estruturas de dados simples ou elementares como:
•
caracter;
•
inteiro;
•
real;
•
lógico;
•
string.
Vimos também a utilização de arrays de elementos deste tipo. A característica
fundamental de um array reside no facto dos seus elementos serem todos do mesmo tipo.
Já vimos ao longo dos exemplos que foram apresentados, que um dos passos mais
importantes na resolução de um problema é a forma de estruturar convenientemente os dados
envolvidos. Por exemplo, no armazenamento de dados referentes a um estudante devemos ser
capazes de guardar:
•
O nome, sendo este do tipo string;
•
O número, sendo este do tipo inteiro;
•
O endereço, sendo este do tipo string;
•
O ano de matrícula, sendo este do tipo inteiro;
•
Etcetera.
Até ao momento não estudámos nenhum tipo de dado que seja capaz de armazenar desde
strings, até números inteiros, reais, etcetera. Necessitamos pois de uma estrutura nova capaz
de albergar dados que não sejam todos do mesmo tipo, isto é, dados não homogéneos. As
estruturas de dados do tipo REGISTO ou ESTRUTURA servem este propósito.
Vejamos um exemplo concreto. Suponhamos que pretendemos elaborar um conjunto de
programas que sejam capazes de lidar com números complexos. Como sabemos, os números
deste tipo possuem uma parte real e uma parte imaginária. Poderíamos pensar em utilizar duas
variáveis do tipo real, designando uma de ‘parte_real’ e outra de ‘parte_imaginaria’, por
exemplo. Seguindo esta linha de raciocínio, se por ventura pretendêssemos usar vectores (ou
115
matrizes) de números complexos, teríamos que definir um vector (ou uma matriz) de nome
‘parte_real’ e um outro (ou uma outra) de nome ‘parte_complexa’. A utilização de um registo
que albergue duas variáveis (campos) do tipo real, uma com nome ‘parte_real’ e outra com o
nome ‘parte_imaginaria’, facilitará grandemente a programação e a estruturação dos dados do
programa. As variáveis do registo são designadas de campos. Vejamos pois como é que
poderíamos definir um registo deste tipo, utilizando notação algorítmica:
complexo DO TIPO REGISTO
CAMPOS DO REGISTO
ParteReal DO TIPO REAL
ParteImaginaria DO TIPO REAL
FIM DE REGISTO
Em PASCAL define-se da seguinte forma:
TYPE
complexo = RECORD
ParteReal : REAL;
ParteImaginaria : REAL
END;
O acesso aos diferentes campos de um REGISTO faz-se da seguinte forma (tanto em
linguagem algorítmica como em PASCAL): nome_da_variavel.nome_do_campo. Se
definirmos A como sendo do tipo Complexo, podemos fazer:
(notação algorítmica)
VARIÁVEIS A DO TIPO complexo
A.ParteReal ß 2.3
ESCREVER(A.ParteImaginaria)
(em PASCAL)
VAR A : complexo;
A.ParteReal := 2.3
116
WRITE(A.ParteImaginaria)
Claro está que podemos definir funções/procedimentos que utilizem REGISTOS
previamente definidos. O procedimento que se segue soma dois números complexos.
(notação algorítmica)
PROCEDIMENTO AdicaoComplexa(A, B, C)
PARÂMETROS DE ENTRADA
A, B DO TIPO complexo [valores a adicionar]
PARÂMETROS DE ENTRADA E SAÍDA
C DO TIPO complexo [resultado da adição]
[Cálculo do resultado]
C.ParteReal ß A.ParteReal+B.ParteReal
C.ParteImaginaria ß A.ParteImaginaria+B.ParteImaginaria
RETORNA
(em PASCAL)
PROCEDURE AdicaoComplexa(
A, B : complexo; {valores a adicionar}
VAR C : complexo {resultado da adição}
);
BEGIN
{Cálculo do resultado}
C.ParteReal := A.ParteReal+B.ParteReal;
C.ParteImaginaria := A.ParteImaginaria+B.ParteImaginaria
END;
11.1 – Arrays de registos
Os arrays de registos definem-se da seguinte forma:
117
•
nome_do_vector[N] DO TIPO VECTOR DE nome_do_registo
•
nome_da_matriz[N, M] DO TIPO MATRIZ DE nome_do_registo
Como exemplo vejamos a definição e utilização de um vector com vinte elementos do
tipo complexo:
(notação algorítmica)
x[20] DO TIPO VECTOR DO TIPO complexo [Declaração]
x[2].ParteReal ß -3.56 [Acesso a um elemento]
Escrever(x[1].ParteImaginaria) [Acesso a um elemento]
(em PASCAL)
x : ARRAY[1..20] OF complexo; {Declaração}
x[2].ParteReal := -3.56; {Acesso a um elemento}
WRITE(x[1].ParteImaginaria); {Acesso a um elemento}
Finalizemos este estudo com o exemplo da estruturação e preenchimento de dados
referentes a um empregado da empresa K3K.
(notação algorítmica)
RegistoNome DO TIPO REGISTO
CAMPOS DO REGISTO
proprio DO TIPO string
apelido DO TIPO string
FIM DO REGISTO
RegistoMorada DO TIPO REGISTO
CAMPOS DO REGISTO
rua DO TIPO string
cidade DO TIPO string
provincia DO TIPO string
FIM DO REGISTO
118
RegistoEmpregado DO TIPO REGISTO
CAMPOS DO REGISTO
nome DO TIPO RegistoNome
morada DO TIPO RegistoMorada
salario DO TIPO real
sexo DO TIPO caracter
FIM DO REGISTO
VARIÁVEIS empregado[20] DO TIPO VECTOR DE RegistoEmpregado;
Para introduzir o nome próprio, via teclado, do i-ésimo empregado faz-se
LER(emrpegado[i].nome.proprio);
Para apresentar no écran alguns dados correspondentes ao i-ésimo empregado faz-se
ESCREVER(‘O empregado ’, empregado[i].nome.apelido, ‘ tem um salário de ’,
empregado[i].salario, ‘ Euro.’);
(em PASCAL)
type
RegistoNome = record
proprio : string[30] ;
apelido : string[30]
end;
RegistoMorada = record
rua : string[30];
cidade : string[30];
provincia : string[30]
end;
RegistoEmpregado = record
nome : RegistoNome;
119
morada : RegistoMorada;
salario : real;
sexo : char
end;
var empregado : array[1..20] of RegistoEmpregado;
Para introduzir o nome próprio, via teclado, do i-ésimo empregado faz-se
read(emrpegado[i].nome.proprio);
Para apresentar no écran alguns dados correspondentes ao i-ésimo empregado faz-se
writeln(‘O empregado ’, empregado[i].nome.apelido, ‘ tem um salário de ’,
empregado[i].salario:6:2, ‘ Euro.’);
Deixa-se como exercício final o desenvolvimento de um algoritmo que produza uma
listagem ordenada por ordem alfabética dos nomes próprios dos empregados. Desta listagem
deve ainda constar, para além do nome próprio, o apelido e o salário. Também deve ser
tentada a incorporação das funcionalidades pretendidas com o exercício acerca da empresa
K3K, secção 9.1.
120
12 – Bibliografia
Com esta secção não pretendemos de forma alguma indicar uma lista de referências
bibliográficas completa e exaustiva. Pretende-se sim indicar alguns textos que sirvam de
complemento ou pormenorização aos assuntos aqui introduzidos. Indicam-se referências para
os diferentes conteúdos aqui introduzidos, nomeadamente, evolução dos computadores,
sistemas de numeração, sistemas informáticos e respectivas classificações, noções de sistemas
operativos, noção de algoritmo e respectiva evolução dos algoritmos e da algoritmia, noções
de programação de computadores com recurso a diferentes linguagens de programação e
notações algorítmicas, etcetera.
Esperamos que esta lista seja de alguma forma útil e sirva de “ponto de entrada no mundo
dos computadores”.
Azul, Artur Auguto; Introdução às tecnologias de informação; Bloco I; Porto Editora; 2000.
Chabert, Jean-Luc (ed.); A History of algorithms: from the pebble to the microchip; SpringerVerlag; 1999.
Harel, David; Algorithmics: the spirit of computing; Addison-Wesley Publishing Company;
1987.
Monteiro, Mário A.; Introdução à organização de computadores; 2ª edição; Livros Técnicos
e Científicos (LTC) – Editora S.A. – Rio de Janeiro; 1995.
Peatman, John B.; Microcomputer-based design; International Student Edition; McGraw-Hill
International Book Company; 1981.
Tremblay, Jean-Paul; e DeDourek, John M.; e Bunt, Richard B.; Introduction to computer
science: an algorithmic approach; Pascal Edition; McGraw-Hill International Editions; 1989.
Didacta – Enciclopédia temática ilustrada; ISBN 972-8332-00-9; Madrid, Espanha; Edición
2000.
121