Upload
vanbao
View
224
Download
0
Embed Size (px)
Citation preview
1
Algoritmos e Programação-A
Prof. Dr. Alceu de Souza Britto Jr
(UEPG/PUCPR)
Material cedido por:
Prof. Dr. Edson E. Scalabrin.
PUCPR
2
Por que construir algoritmos?
• Construir algoritmos é a atividade fundamental em programação de computadores.
• Algoritmo é:– “É uma sequência de passos que visam atingir um objetivo
bem-definido.”– É um conjunto comandos, que executados em uma sequência bem-
definida, realizam um objetivo.
• Comando é:– É uma instrução que resulta na execução de uma operação.
3
Aptidões I
• Conceituar e empregar:– variáveis;– constantes;– operadores aritméticos;– fórmulas matemáticas;– operadores lógicos;
4
Tipos Primitivos
• Inteiro é:– toda e qualquer informação numérica que pertence ao conjunto dos
números inteiros relativos (negativa, nula ou positiva).• Real é:
– toda e qualquer informação numérica que pertence ao conjunto dos números reais (negativa, nula ou positiva).
• Caractere é:– toda e qualquer informação composta por um conjunto de caractere
alfanuméricos (0..9) e/ou especiais (por exemplo, # $ % & ? - < ! @).• Lógico é:
– toda e qualquer informação que pode apenas assumir duas situações ou estados (por exemplo, aberta ou fechada, acesa ou apagada, verdadeiro ou falso).
5
Constante e Variável• Constante é:
– Toda e qualquer informação que não sofre nenhuma variação no decorrer do tempo (por exemplo, “PI = 3,14”).
• Variável é:– Toda e qualquer informação que oferece a possibilidade de ser
alterada em algum instante no decorrer do tempo (por exemplo, cotação do dólar, índice da bolsa).
• As regras para a formação de identificadores de variável/constantesão:– devem começar por um caractere alfabético;– podem ser seguidos por mais caracteres alfabéticos e/ou numéricos;– não é permitido o uso de caracteres especiais;
– Ex: identificadores válidos: PI, X, Y, X9, MEDIAidentificadores inválidos: X$, Y-Z, 9X, P&D
6
Declaração de Variável
• Cada informação guardada na memória do computador recebe um identificador e um tipo.
• Como na memória do computador podem haver inúmeras informações, então precisa-se diferenciar os locais aonde tais informações são guardadas por meio de identificadores diferentes.
Exemplos:
– inteiro: IDADE;– caractere: NOME, SOBRENOME, ENDERECO;– real: PESO, COTACAODODOLAR;– lógico: RESPOSTA, INTERRUPTOR;
7
Exercícios de Fixação1. Assinale os identificadores válidos:
– (a) (X) (b) U2 (c) AH! (d) “ALUNO”– (e) #55 (f) KM/L (g) KQML (h) JAVA– (i) AB*C (j) O&O (l) P|O| (m) H2O
2. Supondo que as variáveis NB, NA, NMAT, SX sejam utilizadas para armazenar ou guardar a nota do aluno, o nome do aluno, o número da matrícula e o sexo, declare-as corretamente.
3. Encontre os erros da seguinte declaração de variáveis:– inteiro: ENDERECO, NFILHOS;– caractere: IDADE, X;– real: REAIS, APTO, C, PESO, OUT;– lógico: LÂMPADA, C;
8
Expressões e OperadoresAritméticos
Expressão aritmética é:– Toda e qualquer expressão cujos operadores são aritméticos e cujos
operandos são constantes e/ou variáveis do tipo numérico (inteiro e/oureal).
Operador Aritmético é:– Todo e qualquer símbolo que representa uma operação básica da
matemática.– a saber: + (adição) - (subtração)
* (multiplicação) / (divisão)** (potenciação) // (radiciação)
– operadores não-convencionais: mod (resto da divisão)div (quociente da divisão inteira)
9
Exemplos: Expressões e Operadores Aritméticos
Exemplos: 2 + 2XPTO / 5X ** 2X – 33 ** 23 // X2 * NOTA3 // 9
Exemplos: 15 div 7 resulta 215 mod 7 resulta 127 div 5 resulta 527 mod 5 resulta 2
10
Funções MatemáticasFunção Descriçãosen(x) fornece o valor do seno de x.cos(x) fornece o valor do cosseno de x.tg(x) fornece o valor do tangente de x.arctg(x) fornece o valor do arco cuja tangente é x.arccos(x) fornece o valor do arco cujo cosseno é x.arcsen(x) fornece o valor do arco cujo seno é x.abs(x) fornece o valor absoluto (módulo) de x.int(x) fornece a parte inteira de um número fracionário x.frac(x) fornece a parte fracionária x. ard(x) transforma, por arredondamento, um número fracionário x
em inteiro.sinal(x) fornece o valor -1, +1 ou zero conforme o valor de x seja
negativo, positivo ou nulo.rnd(x) valor randômico a x.
onde x pode ser um número,uma variável, uma
expressão aritmética ou também outra função matemática.
11
Exemplos: Funções Matemáticas
Constantes Numéricas:
– int(34.886) resulta 34– frac(34.886) resulta 886– ard(34.886) resulta 35– ard(34.386) resulta 34– abs(-27) resulta 27
– sinal(-44) resulta -1
Variáveis:
– abs(X - 5)
– int(Y / 7)
– frac(3 // K)– abs(int(Y / 7))
12
Resolução de Expressões Aritméticas
Prioridade:– as operações e
funções matemáticas guardam entre si uma hierarquia.
parênteses mais internosfunções matemáticas** //* / div mod+ -
Nota:– para operações de mesma prioridade, segue-se a ordem
especificada, isto é, primeiro resolve-se os operadores mais àesquerda e depois os mais à direita da tabela e, para alterar a prioridade da tabela, utiliza-se parênteses mais internos.
13
Exemplos: Resolução de Expressões Aritméticas
c) 3 ** 2 – 4 / 2 + abs(5 – 3 * 5) / 23 ** 2 – 4 / 2 + abs(5 – 15 ) / 23 ** 2 – 4 / 2 + abs(-10) / 23 ** 2 – 4 / 2 + 10 / 29 – 4 / 2 + 10 / 29 – 2 + 5 = 12
a) 5 + 9 + 7 + 8 / 45 + 9 + 7 + 2 = 23
b) 1 – 4 * 3 / 6 – 2 ** 31 – 4 * 3 / 6 – 81 – 12 / 6 – 8 1 – 2 – 8 = -9
14
Exercícios de Fixação
Supondo A, B e C variáveis de tipo inteiro, com valores iguais a 5, 10 e -8, e uma variável real D, com valor de 1,5, quais os resultados das expressões abaixo?
a) 2 * A mod 3 – Cb) 2 // (2 * abs( C )) div 4c) (frac( A / B) + sinal( C )) ** 3d) ard(abs( C / 2 + D)) – int ( A / 2 )e) 3 + (3 // (C + 16)) * ((3 mod D + 0,5) * 2)f) (A + B) div A * ard(sinal( C ) + D) – int(D * 2)
15
Expressões e OperadoresLógicos/Relacionais
Expressão lógica é:– Toda e qualquer expressão cujos:
• operadores são lógicos e/ou relacionais e • operandos são relações e/ou variáveis e/ou constantes do tipo
lógico.
Operador Relacional é:– Todo e qualquer símbolo que representa uma operação básica de
comparação.– a saber: = (igual a) <> (diferente de)
> (maior que) >= (maior igual a)< (menor que) <= (menor igual a)
– utilizado para realizar comparações entre dois valores de mesmo tipo primitivo. Tais valores são representados por constantes, variáveis ou expressões aritméticas.
16
(cont.)
Operador Lógico é:– Todo e qualquer símbolo que representa um conectivo
básico para a formação de novas proposições a partir de outras já conhecidas
– a saber:e (conjunção)ou (disjunção não-exclusiva)xou (disjunção exclusiva)não (negação)
17
Exemplos: Expressões e Operadores Relacionais
d) 2 + 8 mod 7 >= 3 * 6 – 15 2 + 1 >= 18 – 15
3 >= 3V
a) 2 * 4 = 24 / 38 = 8
V
b)15 mod 4 < 19 mod 63 < 1
F
c) 3 * 5 div 4 <= 3 **2 / 0.515 div 4 <= 9 / 0.5
3 <= 18V
18
Tabela Verdade
Definição:É o conjunto de todas as possibilidades combinatórias entre os valores de diversas variáveis lógicas, as quais se encontram em apenas duas situações, e um conjunto de operadores lógicos.
A B A e B
F
F
V
V
F
V
F
V
F
F
F
V
A B A ou B
F
F
V
V
F
V
F
V
F
V
V
V
A B A xou B
F
F
V
V
F
V
F
V
F
V
V
F
A não A
F
V
V
F
Exemplos:
19
Exemplos:Expressões Lógicas
d) falso ou 20 div 18 / 3 <> 18 / 3 div 20F ou 20 div 6 <> 6 div 20
F ou 3 <> 0F ou V
V
f) não verdadeiro xou 3**2/3 < 15 – 35 mod 7F xou 9 /3 < 15 – 0
F xou 3 < 15F xou V
V
a) 2 < 5 e 15 / 3 = 5V e 5 = 5
V e VV
b) 2 < 5 ou 15 / 3 = 5V ou 5 = 5
V ou VV
c) 2 < 5 xou 15 / 3 = 5V xou 5 = 5
V xou VF
20
Resolução de Expressões Lógicas
Prioridade:– Entre operadores
lógicos
– Entre todos os operadores:
nãoe ouxou
parênteses mais internosfunções matemáticasoperadores aritméticosoperadores relacionaisoperadores lógicos
21
Exercícios de Fixação
Determine os resultados obtidos na avaliação das expressões lógicas seguintes, sabendo que A, B, C, D e E contém respectivamente 2, 7, 3.5, “noite” e “frio” e que existe uma variável lógica L cujo valor é falso:
a) B = A * C e L ou verdadeirob) “dia” = D xou “frio” <> “clima”c) L e B div A >= C ou não A <= Cd) 3 // 7 ** 2 = 14 / A xou (B – 3 <= C + 0.5)e) não L ou verdadeiro e sinal( C ) >= A div Af) abs(B + ( -2 )) = ard(((2 * C) ** 2) / 10
22
Aptidões II
• Conceituar, representar e aplicar – atribuição de um valor a uma variável;– entrada de dados;– saída de dados; e– bloco de comandos;
23
Comando de Atribuição
Definição:– É uma instrução que permite que um valor seja fornecido a certa variável.
Símbolo: ←
Exemplo:
lógico: A, B;inteiro: X;A ← verdadeiro;X ← 8 + 13 div 5;B ← 5 = 3;
Estes comandos atribuem às variáveis A, X e B os valores fornecidos à direita do símbolo de atribuição.
Nota:• O tipo do dado deve ser compatível com o tipo da variável.
24
Exercícios de FixaçãoEncontre os erros dos seguintes comandos de atribuição:
a) lógico: A;b) real: B, C;c) inteiro: D;
d) A ← B = C;e) D ← B;f) C + 1 ← B + C;g) B ← 10 + 2 // 9 – int(15 / (abs(-4 div 2))) <= (5 ** (sinal( -1 ));h) C e B ← 3.5;
25
Comandos de Entrada e Saída
Entrada de dados:– É importante construir algoritmos que permitam ao usuário fornecer
qualquer tipo de valor as variáveis que serão utilizados pelo computador para produzir o resultado desejado.
Exemplos: leia ( X );
leia ( A, XPTO, NOTA );
Saída de dados:– É importante construir algoritmos que permitam ao usuário recuperar
o resultado de um processamento. Exemplos: escreva ( Y );
escreva ( B, XPTO, MEDIA );escreva ( “Bom Dia ”, NOME );escreva ( “Você pesa ”, X * 2, “ quilos”);
26
Blocos
Definição:É um conjunto de ações com um objetivo bem-definido.
Nota: – Pode-se então dizer que
um algoritmo é COMO UM BLOCO.
– Um bloco serve também para definir os limites nos quais as variáveis declaradas em seu interior são conhecidas.
Exemplo:
início {início do bloco (algoritmo)}||| {declaração de variáveis}|| {seqüência de ações / comandos}||fim; {fim do bloco (algortimo)}.
27
Exercíciosinício:
[...]inteiro: X, Y;real: Z;leia ( X );escreva (X, “ao cubo = ”, X ** 3);leia ( Y );escreva ( X + Y );Z ← X / Y;escreva ( Z );Z ← int( Z );escreva( Z );Z ← Z + 1;Z ← ( Y + Z ) mod 2;escreva( X );
[ ...]fim;
1. Utilizando o trecho de algoritmo ao lado, explique o que estáacontecendo em cada linha e qual é o resultado de cada ação executada.
2. Cite e discorra sobre três exemplos de seu dia-a-dia nos quais você encontra explicitados: Entrada, Processamento e Saída.
3. Faça uma analogia de Entrada, Processamento e Saída de dados com o que acontece quando você lê e sintetiza um livro e quando você dialoga com outra pessoa.
28
Aptidões III
• Compreender e aplicar estruturas:– de controle seqüencial;– de controle de seleção simples*, composta e de múltipla
escolha;– de controle de repetição.
* desvios condicionais
29
Estrutura de Controle
Como são construídos os algoritmos?– Eles são construídos por meio da combinação de uma ou mais
estruturas básicas de controle. – Tais estruturas são dos seguintes tipos:
• Seqüencial;
• Seleção simples, composta e de múltipla escolha; e• Repetição.
30
Estrutura Seqüencial
Definição:– É conjunto de ações primitivas que
são executadas numa seqüência linear de cima para baixo e da esquerda para a direita.
início: {começo do algoritmo}
{declaração de variáveis}comando a;comando b;comando c; comando d;comando e;
.
.
.comando n;
fim. {algoritmo}
Nota:Todas as ações devem ser seguidas por um ponto-e-vírgula (;) que objetiva separar uma ação de outra e auxiliar a organização seqüencial das ações.
31
Exemplo: Construa um algoritmo que calcule a média aritmética entre quatro notas quaisquer fornecidas pelo usuário.
Passo 1: dados de entrada: quatro notas bimestrais (N1, N2, N3, N4);Passo 2: dados de saída: média aritmética anual (MA);Passo 3: O que devemos fazer para transformar quatro notas bimestrais
numa média anual?
Resposta: utilizar média aritmética.O que é média aritmética?
É a soma dos elementos divididos pela quantidade deles. Em nosso caso particular: (N1+N2+N3+N4)/4;
Passo 4: Construção do algoritmo:início {começo do algoritmo}
real: N1, N2, N3, N4, MA; {declaração de variáveis}leia(N1, N2, N3, N4); {entrada de dados}
MA ← (N1 + N2 + N3 + N4)/4; {processamento}
escreva( MA ); {saída de dados}fim. {término do algoritmo}
32
Exemplo: Construa um algoritmo que calcule a quantidade de latas de tinta necessárias e o custo para pintar tanques cilíndricos de combustível, onde são fornecidos a altura e o raio desses cilindros. Sabendo que:
a) A lata de tinta custa R$ 50,00;b) Cada lata contém 5 litros;c) Cada litro de tinta pinta 3 metros quadrados.
Passo 1: dados de entrada: altura (H) e raio (R);Passo 2: dados de saída: custo (C) e quantidade (QTDE);Passo 3: Utilizando planejamento reverso, sabemos que:
– custo é dado por quantidade de latas * R$ 50,00;– quantidade de latas é data por quantidade total de litros / 5;– quantidade total de litros é dada por área do cilindro / 3;– área do cilindro é dada por área da base + área lateral;– área da base é (PI * R ** 2);– área lateral é altura * comprimento: (2 * PI * R * H);– sendo que R (raio) e H (altura) são dados de entrada e PI é uma constante
de valor conhecido: 3,14.
33
continuação
Passo 4: Construção do algoritmo:início {começo do algoritmo}
real: H, R; {declaração de variáveis}real: C, QTDE, AREA, LITRO; {declaração de variáveis}leia(H, R); {entrada de dados}
AREA ← (3,14 * R ** 2) + (2*3,14*R*H); {processamento}
LITRO ← AREA / 3; {processamento}
QTDE ← LITRO / 5; {processamento}
C ← QTDE * 50,00; {processamento}
escreva( C, QTDE ); {saída de dados}fim. {término do algoritmo}
34
Exercícios de Fixação
1. Construa um algoritmo para calcular as raízes de uma equação do 2º grau, sendo que os valores A, B, C são fornecidos pelo usuário.
2. Construa um algoritmo que, tendo como dados de entrada dois pontos quaisquer do plano, P(x1,y2) e Q(x2,y2), imprima a distância entre eles. A fórmula que efetua tal cálculo é: d=2//( (x2-x1)**2 + (y2-y1)**2)
3. Faça um algoritmo para calcular o volume de uma esfera de raio R, em que R é um valor lido. A fórmula que efetua tal cálculo é: V = 4/3 * (PI * R**3)
35
Estrutura de Seleção: É uma estrutura que permite a escolha de um grupo de ações e estruturas a serem executadas quando determinadas
condições, representadas por expressões, são ou não satisfeitas.
Seleção Simples
se <condição> então
C; {comando único (ação primitiva)}fimse;
onde:<condição> é uma expressão lógica, que, quando avaliada, pode
gerar um resultado verdadeiro ou falso.Se <condição> for verdadeira, a ação primitiva sob a cláusula então
será executada; caso contrário (<condição> for falsa), encerrao comando (fimse), neste caso, sem executar nenhum comando.
36
Exemplo:Estrutura de seleção simples e bloco de comandos
se <condição>
então
início {bloco verdade}
C1;
C2;
...
Cn;
fim {bloco}
fimse;
Se <condição> for verdadeira, então o “bloco verdade” (seqüência de comandos C1...Cn) será executada; caso contrário (<condição> for falsa), nada será executado, encerrando o comando (fimse).
A existência do bloco (demarcado por início e fim) faz-se necessária devido à existência de um conjunto de ações primitivas sob a mesma cláusula então.
37
Exemplo: Sendo N1, N2, N3, N4 as quatro notas bimestrais de um aluno, pode-se avaliar sua situação quanto à aprovação, neste caso, obtida
atingindo-se média superior ou igual a sete.
início {começo do algoritmo}{declaração de variáveis}
real: N1, N2, N3, N4; {notas bimestrais}real: MA; {média anual}{entrada de dados}
leia(N1, N2, N3, N4);{processamento ou cálculo da média aritmética}
MA ← (N1 + N2 + N3 + N4)/4;
{saída de dados}
escreva( MA );se MA >= 7
então escreva (“aluno(a) aprovado(a)”);fimse;
fim. {término do algoritmo
38
Seleção Composta
se <condição> então
início {bloco verdade}C1;C2; {seqüência de comandos}...Cn;fim {bloco}
senãoC; {ação primitiva}
fimse;
onde:Se <condição> for verdadeira, então o “bloco verdade” (seqüência de comandos C1...Cn) seráexecutada; caso contrário (<condição> for falsa), será executado o comando C (ou ação primitiva) que segue a cláusula senão.
39
Exemplo:Estrutura de seleção composta e bloco de comandos
se <condição> então
início {bloco verdade}C1;C2;C3;fim {bloco verdadeiro}
senãoinício {bloco falso}C1;C2;fim {bloco falso}
fimse;
Se <condição> for verdadeira, então o “bloco verdade”(seqüência de comandos C1...C3) será executado;
caso contrário (<condição> for falsa), o “bloco falso” (seqüência de comandos C1...C2) seráexecutado.
40
início {começo do algoritmo}real: N1, N2, N3, N4, MA; {notas bimestrais e média anual}leia(N1, N2, N3, N4);
MA ← (N1 + N2 + N3 + N4) / 4;
escreva( “Media anual = ”, MA );se MA >= 7 então início {bloco verdade}
escreva (“aluno(a) aprovado(a)”);escreva (“Parabéns!”);fim {bloco verdade}
senão início {bloco falso}escreva (“aluno(a) reprovado(a)”);escreva (“Estude mais!”);
fim {bloco falso}fimse;
fim. {término do algoritmo}
Exemplo: Será incluído, no exemplo anterior, a informação que provém do resultado falso da condição (MA >= 7), a reprovação do aluno.
41
Passo 1: dados de entrada: senha suposta pelo usuário (S);Passo 2: dados de saída: “Acesso Permitido” ou “Acesso Negado”;Passo 3: montando uma tabela de decisão:
S=”ASDFG” Açãoverdadeiro escreva “Acesso Permitido”falso escreva “Acesso Negado”
Passo 4: Construção do algoritmoinício {começo do algoritmo}
caractere: S; {senha fornecida pelo usuário}leia(S);se S = “ASDFG”
então escreva(“Acesso Permitido”);senão escreva(“Acesso Negado”);
fimse;fim. {término do algoritmo}
Exemplo: Construa um algoritmo que verifique a validade de uma senha fornecida pelo usuário. A senha é um conjunto de cinco caracteres que são: “ASDFG”.
42
Exemplo: Dados três valores A, B, C, verificar se eles podem ser os comprimentos dos lados de um triângulo e, se forem, verificar se compõem um triângulo eqüilátero, isósceles ou escaleno. Informar se não compuserem nenhum triângulo.
Passo 1: entrada de dados: três lados de um suposto triângulo (A, B, C).Passo 2: saída de dados: “não compõem triângulo”, “triângulo
eqüilátero”, “triângulo isósceles” ou “triângulo escaleno”.Passo 3:
• O que é um triângulo?É uma figura geométrica de três lados, onde cada um é menor do que a soma dos outros dois.
• O que é um triângulo eqüilátero?É um triângulo com três lados iguais.
• O que é um triângulo isósceles?É um triângulo com dois lados iguais.
• O que é um triângulo escaleno?É um triângulo com todos os lados diferentes.
43
é triângulo? é eqüilátero? é isósceles? é escaleno? Ações
V V F F “tr. eq.”
V F V – “tr. is.”
V F F V “tr. es.”
F – – – “Não Tr.”
Passo 4: Montagem da tabela de decisão
é triângulo: (A < B + C) e (B < A + C) e (C < A + B);
é eqüilátero: (A = B) e (B = C);
é isósceles: (A = B) ou (A = C) ou (B = C);
é escaleno:(A <> B) e (B <> C);
Traduzindo as condições para expressões lógicas:
44
Passo 6: Construção do algoritmo
início {começo do algoritmo}inteiro: A,B,C; {lados de um suposto triângulo }leia(A,B,C);se (A < B + C) e (B < A + C) e (c < A + B)então se (A = B) e (B = C)
então escreva(“Triângulo Eqüilátero”);senão se (A = B) ou (A = C) ou (B = C)
então escreva(“Triângulo Isósceles”);senão escreva(“Triângulo Escaleno”);
fimsefimse
senãoescreva(“Estes valores não formam um triângulo”);
fimse;fim. {término do algoritmo}
45
Seleção de Múltipla Escolhaescolha X
caso V1: C1;caso V2: C2;caso V3: C3;caso V4: C4;
fimescolha
Caso, o conteúdo da variável X seja igual ao valor Vi, então o comando Ci será executado: caso contrário será inspecionado até se encontrar a igualdade ou terminarem os casos
escolha Xcaso V1: C1;caso V2,V3: C2;caso V4: C3;caso V5: C4;caso contrário: C5;
fimescolha
Para executar um comando que possui mais de um valor que se verifica sua necessidade, agrupa-se todos esses valores em um único caso. E, para executar um comando que se verifica com todos os outros valores, exceto os discriminados caso a caso, incluí-se outra situação: caso contrário.
46
Exercício usando Escolha
Construa um algoritmo que, tendo como dados de entrada o preço de um produto e um código de origem, emita o preço junto de sua procedência. Caso o código não seja nenhum dos especificados, o produto deve ser visto como importado.
Código de origem:1 – Sul 5 ou 6 – Nordeste2 – Norte 7, 8 ou 9 – Sudeste3 – Leste 10 até 20 – Centro-Oeste4 – Oeste 25 até 50 – Nordeste
47
início {começo do algoritmo}{declaração de variáveis}real: PRECO;inteiro: ORIGEM;{entrada de dados}leia(PRECO, ORIGEM);escolha ORIGEM
caso 1: escreva (PRECO, “ – produto do Sul“);caso 2: escreva (PRECO, “ – produto do Norte“);caso 3: escreva (PRECO, “ – produto do Leste“);caso 4: escreva (PRECO, “ – produto do Oeste“);caso 7,8,9: escreva (PRECO, “ – produto do Sudeste”);caso 10..20: escreva (PRECO, “ – produto do Centro-Oeste”);caso 5,6,25..50: escreva (PRECO, “ – produto do Nordeste”);caso contrário: escreva (PRECO, “ – produto Importanto”);
fimescolhafim. {término do algoritmo}
continuação
48
Aptidões IV
• Compreender e aplicar:– estruturas de repetição controlada por uma
variável; e– estruturas de repetição controlada por uma
condição:
49
Estruturas de Repetição
• Repetição controlada por uma variável;– para I de 1 até N passo 1 faça [...]
• Repetição controlada por uma condição:– condição no início do bloco de comandos;
• enquanto <condição C for verdadeira> faça [...]
– condição no final do bloco de comandos.• repita [...] até <condição C seja verdadeira>
50
Repetição com variável de controle
Exemplo: Obter a soma dos n primeiros números pares positivos.
Entrada: um número inteiro n.Saída: soma dos números pares positivos entre 2 e n.Detalhamento:• Todo número par diferente de zero pode ser obtido por meio da fórmula 2i,
onde i pertence ao conjunto N* = {1,2,3,4, ...}.• Para obter os n primeiros números pares, atribuí-se à variável i os valores
1,2,3, ..., n, o que resulta na seqüência 2, 4, 6, ..., 2n.• Matematicamente, o problema é descrito por:
nS = ∑ 2i
i=1• Para calcular esta soma pode-se simplesmente guardar cada resultado
parcial obtido, sem necessariamente guardar todos os números utilizados. Na verdade, basta guardar o último resultado acumulado para depois somá-lo ao número par seguinte, repetindo estas operações até somar o último número.
51
Repetição com variável de controle
Estratégia Detalhada:– para cada valor de i, pertencente ao conjunto {1,2,3, .., n} , calcula-se o
número par correspondente e o adiciona ao valor da soma S, previamente ajustada com valor zero. I.e., deve-se repetir n vezes as duas operações:
calcular o número par t pela fórmula t = 2i e somar t em S.
– pode-se representar tal operação de repetição por:para i de 1 até n passo 1 faça <bloco>
– Dizemos que tal comando de repetição (operação básica) é uma instrução de repetição controlada por variável.
entrada de dados (valor de n)
repetir n vezes
saída do resultado
Esboço do Algoritmo
calcular um número paracumular numa soma
52
Repetição com variável de controle
Algoritmo SomaParObjetivo: Dado um número n, calcular
a soma dos n primeiros números pares.
Entrada: N (inteiro)Saída : S (inteiro)início:
inteiro: N, I, T, S;[1] leia(N);[2] S ← 0;[3] para I de 1 até N passo 1 faça
início[4] T ← 2 * I;[5] S ← S + T;
fim[6] escreva( S );
fim.
A instrução de repetição écontrolada pela variável i, que é
denominada variável de controle da instrução. A variável i recebe valor inicial 1 e é incrementada
de uma unidade até atingir o valor final N. Enquanto o valor de i for menor ou igual ao valor de N, as instruções contidas no bloco são
executadas sucessivamente. Para cada valor atribuído a i, se
este valor não supera N, as instruções do bloco são
executadas e, em seguida, o valor de i é incrementado de uma
unidade.
53
Simulação do algoritmo para N = 3.
escreva 12F31234613
fim do laçoF31234512
T31263511
T3663410
T364339
execução do laço para i = 3 (valor final)T364258
T324247
T322236
execução do laço para i = 2T322155
T302144
T30-133
execução do laço para i = 1 (valor inicial)30--22
3---11I ≤ NNSTI[ ]#
testevariáveis
54
Simulação do algoritmo para N = 1.
escreva 2F1222613
fim do laçoF1222512
T122155
T102144
T10-133
execução do laço para i = 1 (valor inicial)10--22
1---11
I ≤ NNSTI[ ]#
testevariáveis
55
Escrever um algoritmo para gerar os n primeiros
números impares.
Algoritmo EscrevaImparObjetivo: Dado um número n, escrever os n primeiros números
impares.Entrada: N (inteiro)Saída: T (inteiro)início:
inteiro: N, I, T;[1] leia(N);[2] para I de 1 até N passo 1 faça
início[3] T ← 2 * I - 1;[4] escreva( T );
fimfim.
56
Escrever um algoritmo para gerar os n primeiros
números impares em ordem opostas.
Algoritmo EscrevaImparInvertidoObjetivo: Dado um número n, escrever os n primeiros números
impares em ordem opostas.Entrada: N (inteiro)Saída: T (inteiro)início:
inteiro: N, I, T;[1] leia(N);[2] para I de N até 1 passo -1 faça
início[3] T ← 2 * I - 1;[4] escreva( T );
fimfim
57
Exercícios de Fixação1. Dado a serie, S = 1 + 1/2 + 1/3 + 1/4 + . . . + 1/N, escreva um algoritmo
para calcular e imprimir a soma dos N primeiros termos de S.2. Dado a serie, S = 1 – 1/2 + 1/4 – 1/6 + 1/8 – . . . + 1/200, escreva um
algoritmo calcular e imprimir a soma dos 200 primeiros termos de S.3. Calcular as somas:
a) b) c)
4. Escreva um algoritmo que realiza as seguintes operações:• lê N números INTEIROS do teclado; • encontra e imprime o menor e o maior valor.
∑=
=
20
1
2k
kS ∑=
=
50
5
2
k
kT ∑=
=
100
0k
kU
58
Exercícios de Fixação5. Partindo-se de um único casal de coelhos filhotes recém-nascidos e
supondo que um casal de coelhos torna-se fértil após dois meses de vida e, a partir de então, produz um novo casal a cada mês e que os coelhos nunca morrem, a quantidade de casal de coelhos após n meses é dado pelo n-ésimo termo da seguinte seqüência:– Fn = Fn-2 + Fn-1, n>= 2– F0 = 1,– F1 = 1
Esta seqüência chama-se seqüência de Fibonacci.a) escreva um algoritmo para calcular a quantidade de casais de coelhos após n meses.
6. Tabelar N! para N variando de 0 até 10. Por definição k! = k(k-1)(k-2) ... 3,2,1 para k ∈ N* e 0! = 1.
59
Exercícios de Fixação
7. Escreva um algoritmo que realiza as seguintes operações:
– lê o valor da etiqueta de um produto;
– calcula o valor a pagar para o cliente de acordo com os códigos: 1, 2, 3, e 4 (ver tabela ao lado); e
– imprime o valor a pagar do produto.
Código Descrição da Política
1 10% de desconto para pagamento àvista em cheque ou dinheiro.
2 5% de desconto para pagamento àvista no cartão.
3 0% para pagamento em duas vezes.
4 10% de acréscimo para pagamento em três vezes ou mais.
60
Exercícios de Fixação8. Escrever um algoritmo que calcule e imprima a tabela de amortização de
empréstimo para um de principal 6.000, 10% de juros, período de reembolso de quatro anos.
PVA = 6000k = 10% n = 4
))1(
11(
1),(
nkk
nkFJVFA+
−×=
FJVFA
VPAPMT =
61
Continuação, exercício 8.
6.000,00 1.571,30 7.571,30
0,00 1.720,75 172,07 1.720,75 1.892,82 4
1.720,75 1.564,32 328,51 3.285,07 1.892,82 3
3.285,07 1.422,11 470,72 4.707,18 1.892,82 2
4.707,18 1.292,82 600,00 6.000,00 1.892,82 1
Principal no fim do ano
[(2)-(4)] (5)Principal
[(1)-(3)] (4)Juros
[0,10x(2)] (3)Principal no começo
do ano (2)Pagamento do empréstimo (1)Fim do ano
Pagamentos
(PRINCIPAL $6.000, 10% DE JUROS, PERÍODO DE REEMBOLSO DE QUATRO ANOS)
TABELA DE AMORTIZAÇÃO DE EMPRÉSTIMO
Legenda: (1) = PMT (2) = PVA (3) = PVA * k (4) = (1) – (3) (5) = (2) – (4)
62
Repetição controlada por uma condição
Exemplo: Obter a soma dos números pares positivos menores que 500.
Entrada: um número inteiro 500. Saída: soma dos números pares positivos menores que 500. Detalhamento:• Todo número par diferente de zero pode ser obtido por meio da fórmula 2i,
onde i pertence ao conjunto N* = {1,2,3,4, ...}. Para obter os números pares menores que 500, testa-se a condição que número gerado seja menor ou igual 500, o que resulta na seqüência 2, 4, 6, ..., 2n, onde 2n ≤ 500.
• Matematicamente, o problema é descrito por:n
S = ∑ 2ii=1
• Para calcular esta soma pode-se simplesmente guardar cada resultado parcial obtido, sem necessariamente guardar todos os números utilizados.
para 2i ≤ 500
63
Repetição controlada por uma condição
Estratégia Detalhada:– para cada valor de 2i, pertencente ao conjunto {2, 4, .., n} , testa-se se o
valor de 2i é um número par e é menor que 500. Se a condição for satisfeita, então adicionamos ao valor de 2i a soma S, previamente ajustada com valor zero.
– pode-se representar tal operação de repetição por:enquanto <condição for verdadeira faça <bloco>
– Dizemos que tal comando de repetição (operação básica) é uma instrução de repetição controlada por uma condição.
entrada de dados (número par n)repetir enquanto o número par gerado for menor que n
saída do resultado
Esboço do Algoritmo
calcular um número paracumular numa soma
64
Repetição controladapor uma condiçãoObjetivo: Calcular a soma dos números
pares menores que 500.Entrada: N = 500 (inteiro)Saída : S (inteiro)início:
inteiro: N, I, T, S;[1] leia(N); {N = 500}[2] S ← 0;[3] I ← 1;[4] T ← 2 * I;[5] enquanto (T <= N) faça
início[6] S ← S + T;[7] I ← I + 1;[8] T ← 2 * I;
fim[9] se N = 2[10] então S ← T;[11] escreva( S );
fim.
A instrução de repetição écontrolada pela condição
T ≤ 500. Enquanto o valor de T for menor ou igual ao valor de 500, as instruções contidas no
bloco são executadas sucessivamente. Para cada valor
atribuído a T, se este valor não supera 500, as instruções do bloco são executadas e, em
seguida, o valor de T érecalculado.
Algoritmo SomaPar
65
Escrever um algoritmo para gerar os números impares que 1000.
Algoritmo EscrevaImparMenorQue1000Objetivo: Escrever os números impares que 1000.Entrada: N = 1000 (inteiro)Saída : T (inteiro)início:
inteiro: N, I, T;[1] leia(N); {N = 1000}[2] I ← 1;[3] T ← 2 * I - 1;[4] enquanto (T < N) faça
início[5] escreva( T );[6] I ← I + 1;[7] T ← 2 * I - 1;
fim[8] se N = 1 então[9] escreva( 1 );
fim.
66
Escrever um algoritmo para gerar os números impares em ordem opostas de 1 até 1000.
Algoritmo EscrevaImparInvertidoObjetivo: Escrever os números impares em ordem opostas de 1 até 1000Entrada: N = 1000 (inteiro)Saída : T (inteiro)início:
inteiro: N, I, T;[1] leia(N); {N = 1000}[2] se N mod 2 = 0[3] então I ← N / 2;[4] senão I ← (N + 1) / 2;[5] T ← 2 * I - 1;[6] enquanto (T > 0) faça
início[7] escreva( T );[8] I ← I - 1;[9] T ← 2 * I - 1;
fimfim.
67
Exercícios de Fixação
• Fazer algoritmos dos exercícios 1 a 8 utilizando o laço de repetição enquanto e compará-los como o que já foi feito utilizando o laço de repetição para.
68
Exercícios de Fixação1. Dado a serie, S = 1 + 1/2 + 1/3 + 1/4 + . . . + 1/N, escreva um algoritmo
para calcular e imprimir a soma dos N primeiros termos de S.2. Dado a serie, S = 1 – 1/2 + 1/4 – 1/6 + 1/8 – . . . + 1/200, escreva um
algoritmo calcular e imprimir a soma dos 200 primeiros termos de S.3. Calcular as somas:
a) b) c)
4. Escreva um algoritmo que realiza as seguintes operações:• lê N números INTEIROS do teclado; • encontra e imprime o menor e o maior valor.
∑=
=
20
1
2k
kS ∑=
=
50
5
2
k
kT ∑=
=
100
0k
kU
69
Exercícios de Fixação5. Partindo-se de um único casal de coelhos filhotes recém-nascidos e
supondo que um sacal de coelhos torna-se fértil após dois meses de vida e, a partir de então, produz um novo casal a cada mês e que os coelhos nunca morrem, a quantidade de casal de coelhos após n meses é dado pelo n-ésimo termo da seguinte seqüência:– Fn = Fn-2 + Fn-1, n>= 2– F0 = 1,– F1 = 1
Esta seqüência chama-se seqüência de Fibonacci.a) escreva um algoritmo para calcular a quantidade de casais de coelhos após n meses.
6. Tabelar N! para N variando de 0 até 10. Por definição k! = k(k-1)(k-2) ... 3,2,1 para k ∈ N* e 0! = 1.
70
Exercícios de Fixação
7. Escreva um algoritmo que realiza as seguintes operações:
– lê o valor da etiqueta de um produto;
– calcula o valor a pagar para o cliente de acordo com os códigos: 1, 2, 3, e 4 (ver tabela ao lado); e
– imprime o valor a pagar do produto.
Código Descrição da Política
1 10% de desconto para pagamento àvista em cheque ou dinheiro.
2 5% de desconto para pagamento àvista no cartão.
3 0% para pagamento em duas vezes.
4 10% de acréscimo para pagamento em três vezes ou mais.
71
Exercícios de Fixação8. Escrever um algoritmo que calcule e imprima a tabela de amortização de
empréstimo para um de principal 6.000, 10% de juros, período de reembolso de quatro anos.
PVA = 6000k = 10% n = 4
))1(
11(
1),(
nkk
nkFJVFA+
−×=
FJVFA
VPAPMT =
72
Continuação, exercício 8.
6.000,00 1.571,30 7.571,30
0,00 1.720,75 172,07 1.720,75 1.892,82 4
1.720,75 1.564,32 328,51 3.285,07 1.892,82 3
3.285,07 1.422,11 470,72 4.707,18 1.892,82 2
4.707,18 1.292,82 600,00 6.000,00 1.892,82 1
Principal no fim do ano
[(2)-(4)] (5)Principal
[(1)-(3)] (4)Juros
[0,10x(2)] (3)Principal no começo
do ano (2)Pagamento do empréstimo (1)Fim do ano
Pagamentos
(PRINCIPAL $6.000, 10% DE JUROS, PERÍODO DE REEMBOLSO DE QUATRO ANOS)
TABELA DE AMORTIZAÇÃO DE EMPRÉSTIMO
Legenda: (1) = PMT (2) = PVA (3) = PVA * k (4) = (1) – (3) (5) = (2) – (4)
73
Aptidões V
• Conceituar e aplicar estruturas de dados compostas:– homogêneas unidimensionais (vetor);– homogêneas multidimensionais (matriz); e– heterogêneas (registro).
74
Estrutura de Dados
• Variáveis Compostas Homogêneas• Variáveis Compostas Unidimensionais• Variáveis Compostas Multidimensionais
• Variáveis Compostas Heterogêneas
75
Variáveis Compostas Unidimensionaisou Vetor
Portugol prevê quatro tipos de dados: inteiro, real, cadeia de caracteres e lógico. As palavras-chave que os definem são as seguintes (observe que elas não têm acentuação):
– inteiro: define variáveis numéricas do tipo inteiro (ex: sem casas decimais).
– real: define variáveis numéricas do tipo real (ex: com casas decimais).– caractere: define variáveis do tipo cadeia de caracteres. – logico: define variáveis do tipo binária (ex: valor VERDADEIRO ou
FALSO).Em Portugol pode-se também declarar variáveis estruturadas por meio da palavra-chave vetor.
As estruturas de dados organizam e armazenam logicamente os dados, os quais serão manipulados posteriormente por um algoritmo. Estas estruturas são genericamente classificadas em homogêneas (de um mesmo tipo de dado) e heterogêneas (tipos diferentes).
76
Exemplo de algoritmo sem o uso de Vetor!
O algoritmo inclui a declaração e a instanciação de várias variáveis reais. Estas últimas armazenam as notas de seis alunos.
algoritmo Le6Notasreal : NOTA1, NOTA2, NOTA3, NOTA4, NOTA5, NOTA6;
inicioescreva("Digite a nota do aluno 1: "); leia (NOTA1);escreva("Digite a nota do aluno 2: "); leia (NOTA2);escreva("Digite a nota do aluno 3: "); leia (NOTA3);escreva("Digite a nota do aluno 4: "); leia (NOTA4);escreva("Digite a nota do aluno 5: "); leia (NOTA5);escreva("Digite a nota do aluno 6: "); leia (NOTA6);
fim
77
Comentário (continuação)
• Por meio do algoritmo Le6Notas seria possível ler 6 notas de 6 alunos e armazená-las em 6 variáveis diferentes?– Uma instrução de repetição não melhoraria muito esta lógica, dada a
independência das variáveis.• Como seria se a leitura de todas as notas dos alunos do
módulo de “algoritmo e estrutura de dados I” tivessem que serem lidas pelo seu algoritmo?
• É em situação como esta que as estruturas de dados são fundamentais para o processamento dos dados.
• A estrutura de dados é do tipo: homogênea. Este tipo pode assumir duas formas básicas, a saber: Vetor e Matriz.
78
ESTRUTURA DE DADOS COMPOSTA HOMOGÊNEA - VETOR
Uma estrutura de dados composta homogênea consiste em uma única variável que pode armazenar vários valores do mesmo tipo.
Suas principais características são:– contém vários valores; – todos valores são do mesmo tipo de dado (ex: inteiro); – possui um único identificador; – cada valor do conjunto é acessível independentemente, de
acordo com o seu índice (ou posição na estrutura).
79
Exemplo de Vetor• Suponha a existência de uma estrutura que armazena as notas de 6
alunos. O nome do identificado da variável homogênea unidimensional éNOTAS.
• Os valores ou as notas correspondem aos conteúdos lidos, por exemplo, do teclado. Os índices correspondem às posições que identificam os valores armazenados. Por exemplo, se desejar mostrar a nota do quarto aluno, assim o conteúdo desta posição (4) é igual a 8.0 (nota do aluno).
• Um vetor é uma variável composta porque ele pode armazenar vários valores. Ele é unidimensional porque possui variação em uma dimensão. E finalmente, ele é homogêneo porque só armazena um único tipo de dado.
valores 5.0 6.4 7.2 8.0 9.0 8.0
índices 1 2 3 4 5 6
NOTAS
80
A sintaxe para a declaração e criação de uma estrutura de dados composta unidimensional em Portugol é da seguinte forma:
Formato da declaração de uma estrutura de dados composta unidimensional ou vetor:
tipo <identificador> = vetor[1..N] : <tipo básico>
onde:<tipo básico> é o tipo de dado que será armazenado na
estrutura, por exemplo, real;<identificador>é o nome atribuído ao vetor;[1..N] é a quantidade de elementos que o vetor
poderá armazenar, onde N representa o tamanho do vetor.
Exemplo:
tipo notas = vetor[1..6] : real notas : NOTAS;
81
A variável NOTAS é um vetor que pode armazenar até 6 números reais diferentes.
A operação, tanto de leitura como de escrita de um elemento em um vetor,pode ser realizada por meio da combinação do nome do vetor seguida do índice desejado entre colchetes. Por exemplo, o valor de NOTAS[ 6 ] é 8.0, o valor de NOTAS[ 4 ] é 7.5, e assim por diante.
Exemplos de comandos em Portugol:escreva( NOTAS[ 6 ] ) // Deve mostrar na tela o valor 8.0escreva( NOTAS[ 4 ] ) // Deve mostrar na tela o valor 7.5NOTAS[ 6 ] ← 9.5 // Deve alterar na posição 6 para 9.5NOTAS[ 4 ] ← 8.6 // Deve alterar na posição 4 para 8.6
escreva( NOTAS[ 6 ] ) // Deve mostrar na tela o valor 9.5escreva( NOTAS[ 4 ] ) // Deve mostrar na tela o valor 8.6
NOTAS 5.0 6.4 7.2 7.5 9.0 8.0
1 2 3 4 5 6
NOTAS 5.0 6.4 7.2 8.6 9.0 9.5
1 2 3 4 5 6
82
continuação
real: SOMA, MEDIA;
SOMA ← 0;SOMA ← SOMA + NOTAS[ 1 ];SOMA ← SOMA + NOTAS[ 2 ];SOMA ← SOMA + NOTAS[ 3 ];SOMA ← SOMA + NOTAS[ 4 ];SOMA ← SOMA + NOTAS[ 5 ];SOMA ← SOMA + NOTAS[ 6 ];
MEDIA ← SOMA / 6;
83
Exemplo: Escrever um programa que declare um vetor de reais e leia as notas de 45 alunos.
algoritmo calculoMediatipo notas = vetor[1..45] : real {vetor de reais}início
notas : NOTAS;inteiro : I;para I de 1 até 45 passo 1 faça
escreva("Digite a nota do aluno [",I,”] : ”);leia (NOTA[ I ]);
fimpara;fim
84
Escrever um programa que declare um vetor de cadeia de caracteres e leia os nomes de 45 alunos. O identificador do vetor será NOMES. Ele terá a capacidade para armazenar 45 nomes.
algoritmo listaDeAlunostipo nomes = vetor[1..45] : caractere {vetor de cadeias de caracteres}início
nomes : NOMES;inteiro : I;I ← 1;repita
escreva("Digite o nome do aluno [",I,”] : ”);leia (NOMES[ I ]);I ← I + 1;
até que i > 45;fim
85
ComentáriosO algoritmo listaDeAlunos utiliza a estrutura de controle repita <comandos> até que <condição>.
repita enquanto <condição> comando 1; comando 1;comando 2; comando 2;comando 3; comando 3;
até que <condição> fim
A estrutura de controle repita é similar à estrutura de controle enquanto. A diferença básica consiste na posição do teste que decide pela continuação ou não da execução do bloco de comandos. Na estrutura repita, primeiramente, o bloco de comandos é executa e depois a condição é verificada. É importante notar que o bloco de comandos dentro da estrutura repita executará sempre pelo menos uma vez.
86
Exercícios de FixaçãoEm cada um dos exercícios propostos, deve-se apresentar a análise do problema, definir o objetivo, dar as especificações de entrada e saída e descrever o algoritmo em linguagem algorítmica.
1) Dado um vetor com os resultados da MEGA SENA, identifique se cada número é par, ímpar, múltiplo de três, múltiplo de cinco ou múltiplo de sete.
ExemploEntrada: 27, 16, 42, 30, 10, 35Saída: 27 ímpar, múltiplo de 3
16 par42 par, múltiplo de 3, múltiplo de 730 par, múltiplo de 3, múltiplo de 510 par, múltiplo de 535 ímpar, múltiplo de 5, múltiplo de 7
87
continuação2) Uma empresa decidiu dar uma gratificação de Natal a seus funcionários,
baseada no número de horas extras e no número de horas que o empregado faltou ao trabalho.
Dados os números de identificação dos funcionários, o número de horas extras e o número de horas-faltas, imprimir uma relação com duas colunas, a primeira contendo o número do funcionário e a segunda o valor do prêmio a que faz jus. Os dados de entrada e saída devem ser organizados em vetores de dados.
TABELA I
O valor de prêmio é obtido pela consulta à Tabela I, em que H éo número de horas-extras subtraído de dois terços do número de horas-faltas.
H (horas) Prêmio (R$)
(40, 100] 100,00
(30, 40] 80,00
(20, 30] 60,00
(10, 20] 40,00
(0, 10] 20,00
88
continuação
3) Dado o vetor de números inteiros X que contem, respectivamente, aos dígitos do número de CPF de um contribuinte, calcular os dígitos verificadores.
Se S1 mod 11 > 9 então X10 ← 0 senão X10 ← S1 mod 11.
Se S2 mod 11 > 9 então X11 ← 0 senão X11 ← S2 mod 11.
ixSi
i ×=∑=
9
11
)1(10
22 −×=∑
=
ixSi
i
89
Matriz é uma:ESTRUTURA DE DADOS COMPOSTA HOMOGÊNEA
O que já dito anteriormente para Vetor vale para Matriz:• Uma estrutura de dados composta homogênea consiste em
uma única variável que pode armazenar vários valores do mesmo tipo. Suas principais características são:– contém vários valores; – todos valores são do mesmo tipo de dado (ex: real); – possui um único identificador; – cada valor do conjunto é acessível independentemente, de
acordo com o seu índice (ou posição na estrutura).
90MAm108.07.26.45.010
m97.08.88.09.59
m87.08.88.09.58
m78.08.57.58.67
m69.09.07.06.76
m58.07.26.45.05
m47.08.88.09.54
m38.08.57.58.63
m29.09.07.06.72
m18.07.26.45.01
ii
4321j
índice – colunas ( j )
índ
ice
–lin
has
( i
)
∑=
=
=
4
11010 4
1 n
j
jAm
∑=
=
=
4
111 4
1 n
j
jAm
Suponha a existência de duas estruturas (A e M) que armazenam as 4 notas bimestrais de 10 alunos e as suas respectivas médias.
O nome do identificador da variável homogênea bidimensional é A (as notas da turma). O nome do identificador da variável homogênea unidimensional éM (as médias da turma).
91
• Os valores ou as notas correspondem aos conteúdos lidos, por exemplo, do teclado. Os índices correspondem às posições que identificam os valores armazenados. Por exemplo, se desejar mostrar a nota do segundo bimestre do quarto aluno, assim o conteúdo desta posição (linha = 4, coluna = 2) é igual a 8.0 (nota do aluno). A formula abaixo mostra o cálculo da média das notas do aluno 4.
• Uma matriz A é uma variável composta porque ele pode armazenar vários valores. Ela é bidimensional porque possui variações em duas dimensões. E finalmente, ela é homogênea porque só armazena um único tipo de dado.
• Um vetor M é uma variável composta porque ele pode armazenar vários valores. Ele é unidimensional porque possui variação em uma dimensão. E finalmente, ele é homogêneo porque só armazena um único tipo de dado.
32.84
0.78.80.85.9
4
)( 444342414 =
+++=
+++=
AAAAm
92
A sintaxe para a declaração e criação de uma estrutura de dados composta bidimensional em Portugol.
Formato da declaração de uma estrutura de dados composta bidimensional:tipo <identificador> = vetor[1..N, 1..M] : <tipo básico>
onde:<tipo básico> é o tipo de dado que será armazenado na estrutura,
por exemplo, real;<identificador>é o nome atribuído ao vetor;[1..N], [1..M] N x M é a quantidade de elementos que a matriz
poderá armazenar, onde N representa o número de linhas e M o número de colunas.
Exemplos:tipo matReal = vetor[1..10,1..4] : real {estrutura bidimensional}matReal : A;tipo vetReal = vetor[1..10] : real {estrutura unidimensional}vetReal : M;
93
A variável A é uma matriz que pode armazenar até 40 números reais diferentes.
8.07.26.45.010
7.08.88.09.59
7.08.88.09.58
8.08.57.58.67
9.09.07.06.76
8.07.26.45.05
7.08.88.09.54
8.08.57.58.63A = 9.09.07.06.72
8.07.26.45.01
i
4321j A operação, tanto de leitura como de escrita de um elemento em uma matriz, pode ser realizada por meio da combinação do nome do vetor seguida do índice desejado entre colchetes.
Por exemplo, o valor de A[4][2] é 8.0, o valor de A[4][4] é 7.0, e assim por diante.
94
A =
j 1 2 3 4
i
1 5.0 6.4 7.2 8.0
2 6.7 7.0 9.0 9.0
3 8.6 7.5 8.5 8.0
4 9.5 8.6 8.8 7.0
5 5.0 6.4 7.2 8.0
6 6.7 7.0 9.0 9.5
7 8.6 7.5 8.5 8.0
8 9.5 8.0 8.8 7.0
9 9.5 8.0 8.8 7.0
10 5.0 6.4 7.2 8.0
Exemplos de comandos em Portugol:// Deve mostrar na tela o valor 6.7 escreva( A[ 6 ][ 1 ] )// Deve mostrar na tela o valor 7.5 escreva( A[ 3 ][ 2 ] )// Deve alterar na posição // linha=6,coluna=4 para 9.5 A[ 6 ][ 4 ] ←←←← 9.5// Deve alterar na posição // linha=4,coluna=2 para 8.6A[ 4 ][ 2 ] ←←←← 8.6// Deve mostrar na tela o valor 9.5 escreva(A[ 6 ][ 4 ])// Deve mostrar na tela o valor 8.6 escreva(A[ 4 ][ 2 ]) real: S, M;
S ← 0;S ← S + A[ 4 ][ 1 ];S ← S + A[ 4 ][ 2 ];S ← S + A[ 4 ][ 3 ];S ← S + A[ 4 ][ 4 ];
M ←←←← S / 4;
A variável S possui a soma das 4 notas bimestrais do aluno da linha 4 da matriz A. M éa média.
95
algoritmo calculoDaMediaTurmatipo matReal = matriz[1..45, 1..4] : real tipo vetReal = vetor[1..45] : realinício
matReal : A; vetReal : M;real : S;inteiro : I, J;para I de 1 até 45 passo 1 façainicio
escreva("Para o Aluno ”,I, “ informe suas notas: ”);S ← 0;para J de 1 até 4 passo 1 façainicio
escreva("Nota do bimestre: ”,J);leia (A[ I ][ J ]);S ← S + A[ I ][ J ];
fimpara;M[ I ] ← S / 4;
fimparafim
Escrever um programa que declare uma
matriz de reais e leia as notas bimestrais de 45 alunos e calcule as
médias bimestrais para cada aluno.
96
Exercícios de Fixação
1) Escreva um algoritmo que:a) soma a matriz A100x200 com a matriz B100x200 e armazena o
resultado desta soma em uma matriz C100x200; eb) encontra e imprima o maior valor presente na matriz C100x200.
As propriedades da soma de matrizes para quaisquer matrizes A, B e C, de mesma ordem m×n, vale a igualdade:a) associativa: (A + B) + C = A + (B + C)b) comutativa: A + B = B + Ac) elemento neutro: 0 + A = Ad) elemento oposto: A + (-A) = 0
Exemplo: a soma das matrizes A2x2 e B2x2 é a matriz C2x2 indicada abaixo.
=
+
−
99
62
65
15
34
53
97
2. Escreva um algoritmo que calcule a pontuação de um campeonato de futebol. Este campeonato conta com as equipes: E1, E2, E3 e E4. A pontuação é calculada da seguinte forma: três pontos para cada vitória, um ponto para cada empate e zero para cada derrota.
Tab. 1. Número de vitórias, empates e derrotas.
Equipe Vitória Empate Derrota Pontos
E1 9 3 2 Vitória 3
E2 7 4 3 Empate 1
E3 3 5 6 Derrota 0
E4 6 5 3
O cálculo da pontuação de cada equipe pode ser expresso por meio da multiplicação de uma matriz e um vetor. A Tabela 1 pode ser transformada em matriz de 4 linhas e 3 colunas, onde cada linha representa uma equipe e as colunas representam respectivamente o número de vitórias, empates e derrotas.
×
=
=
=
=
=
0
1
3
356
653
347
239
234
143
252
301
E
E
E
E
98
3) Dadas as matrizes A, B e I, escreva os algoritmo que calcule:C, D, E e F, cujas as formulas são as seguintes:
BAC ×=
BAD +=
TCE =
IAF ×=
=
7529
8451
5286
4152
A
=
8343
6343
7837
2424
B
=
1000
0100
0010
0001
I
99
4) A tabela dada a seguir contém vários itens que estão estocados em diversos armazéns de uma companhia. É fornecido, também, o custo de cada um dos produtos armazenados.
Tabela 2. Estoque de produtos.
Prod. 1 (unidade) Prod 2 (unidade) Prod 3 (unidade)
Armazém 1 1200 3700 3737
Armazém 2 1400 4210 2444
Armazém 3 200 2240 330
Custo (R$) 260 420 330
Fazer um programa que:
1. leia o estoque inicial e os custos por produto;2. determine e imprime quantos itens estão armazenados em cada armazém;3. qual o armazém que possui a maior quantidade de produto 2 armazenado;4. o custo total de:
1. cada produto em cada armazém; 2. estoque em cada armazém; 3. cada produto em todos os armazéns.
100
Variáveis Compostas Heterogêneas
• Registro;• Vetor de Registros
101
Estrutura de dados composta heterogênea.
Uma estrutura de dados composta heterogênea consiste em uma única variável que pode armazenar vários valores de diferentes tipos primitivos ou não. Suas principais características são:
– contém vários valores; – todos valores são de um tipo de dado não primitivo ou
abstrato; – possui um único identificador; – cada valor do conjunto é acessível independentemente, de
acordo com o seu índice (ou posição na estrutura).
102
Exemplo de Registro
REGISTRO GERAL (RG)N
O
M
E
S
E
XO
N
Ú
M
E
RO
DATA DE
NASCIMENTO
DATA DE
EMISSÃO
FILIAÇÃO ÓRGÃO
EXPED
IDOR
NATURALI
DADE
D
IA
M
ÊS
A
NO
D
IA
M
ÊS
A
NO
N
O
M
E
DA
M
ÃE
N
O
M
E
DO
P
AI
M
U
N
I
C
Í
P
IO
E
S
T
A
DO
103
Exemplo de Tabela de Dados
• Suponha a existência de uma estrutura que armazena:– os nomes, – os sobrenomes,– as notas bimestrais e – a média final
• de 10 alunos do módulo “Algoritmos e Estrutura de Dados I”.
• O nome do identificador da variável heterogênea é A.
• Os conjuntos destes dados são ilustrados na estrutura descrita a seguir.
104
L REGISTRO ESCOLAR
I NOME SOBRENOME PA N1B N2B N3B N4B MEDIA
1 Pedro Silva ALG 5,0 6,4 7,2 8,0 6,7
2 Maria Andrade ALG 6,7 7,0 9,0 9,0 7,9
3 João Pires ALG 8,6 7,5 8,5 8,0 8,2
4 Márcia Pereira ALG 9,5 8,0 8,8 7,0 8,3
5 Ana Silva ALG 5,0 6,4 7,2 8,0 6,7
6 Luiz Antunes ALG 6,7 7,0 9,0 9,0 7,9
7 Henrique Forte ALG 8,6 7,5 8,5 8,0 8,2
8 José Coragem ALG 9,5 8,0 8,8 7,0 8,3
9 Marcos Pinto ALG 9,5 8,0 8,8 7,0 8,3
10 Joana Peres ALG 5,0 6,4 7,2 8,0 6,7
A
ALG = Algoritmos e Estrutura de Dados I
105
• Os nomes, os sobrenomes, o PA e as notas correspondem aos conteúdos lidos, por exemplo, do teclado.
• Cada coluna armazena uma informação indicada por um nome e um tipo de dado. Por exemplo, se deseja mostrar a nota do segundo bimestre do quarto aluno e seu sobrenome, assim os conteúdos (linha: 4, colunas: N2B, SOBRENOME) são iguais a 8.0 e Pereira.
• A formula abaixo mostra o cálculo da média das notas do aluno 4.
• O vetor A (definido na próxima página) é uma variável composta àmedida que ela pode armazenar vários valores de um tipo abstrato de dados.
• Ela é heterogênea porque os dados que ela armazena são definidos por meio de um tipo de abstrato de dados.
• A última coluna MEDIA pode ser calculada.
32.84
0.78.80.85.9
4
)4.3.2.1.(. 4444
4 =+++
=+++
=BNABNABNABNA
MEDIAA
106
A sintaxe para a declaração e criação de uma estrutura de dados composta heterogênea em Portugol.
Formato da declaração de uma estrutura de dados composta unidimensional, cujo tipo de dados é heterogêneo:
tipo <identificador> = vetor[1..N] : <tipo abstrato> onde:<tipo abstrato> é o tipo de dado que será armazenado na estrutura;<identificador> é o nome atribuído ao vetor;[1..N] N é a quantidade de elementos que o vetor poderá
armazenar.
tipo registro = registroRE {Exemplo de tipo abstrato}inicio
caracter : NOME, SOBRENOME, PA;real : N1B, N2B, N3B, N4B, MEDIA;
fim.
tipo vetRegistroRE = vetor[1..10] : registroRE;vetRegistroRE : A;
107
6,78,07,26,45,0ALGPeresJoana10
8,37,08,88,09,5ALGPintoMarcos9
8,37,08,88,09,5ALGCoragemJosé8
8,28,08,57,58,6ALGForteHenrique7
7,99,09,07,06,7ALGAntunesLuiz 6
6,78,07,26,45,0ALGSilvaAna5
8,37,08,88,09,5ALGPereiraMárcia4
8,28,08,57,58,6ALGPiresJoão 3
7,99,09,07,06,7ALGAndradeMaria2
6,78,07,26,45,0ALGSilvaPedro1
MEDIAN4BN3BN2BN1BPASOBRENOMENOMEI
REGISTRO ESCOLARL
ALG = Algoritmos e Estrutura de Dados I
A variável A é um vetor de registros que pode armazenar até 30 valores do tipo caracter e 50 valores do tipo real.
A=
108
A operação, tanto de leitura como de escrita de um elemento em um vetor de registros heterogêneos, pode ser realizada por meio da combinação do nome do vetor seguida do índice desejado entre colchetes e o nome do campo.
Por exemplo, o valor de A[4].N2B é 8.0, o valor de A[4].MEDIA é 8,3, e assim por diante.
Exemplos de comandos em Portugol:
escreva( A[ 6 ].NOME ) // Deve mostrar na tela o valor Luizescreva( A[ 4 ].SOBRENOME) // Deve mostrar na tela o valor Pereira
A[ 6 ].N4B ← 9.5 // Deve alterar na posição// linha=6,coluna=N4B para 9.5
A[ 4 ].N2B ← 8.6 // Deve alterar na posição // linha=4,coluna=2 para 8.6
109
6,78,07,26,45,0ALGPeresJoana10
8,37,08,88,09,5ALGPintoMarcos9
8,37,08,88,09,5ALGCoragemJosé8
8,28,08,57,58,6ALGForteHenrique7
7,99,59,07,06,7ALGAntunesLuiz 6
6,78,07,26,45,0ALGSilvaAna5
8,37,08,88,69,5ALGPereiraMárcia4
8,28,08,57,58,6ALGPiresJoão 3
7,99,09,07,06,7ALGAndradeMaria2
6,78,07,26,45,0ALGSilvaPedro1
MEDIAN4BN3BN2BN1BPASOBRENOMENOMEI
REGISTRO ESCOLARL
ALG = Algoritmos e Estrutura de Dados I
A=
110
escreva(A[ 6 ].N4B) // Deve mostrar na tela o valor 9.5escreva(A[ 4 ].N2B) // Deve mostrar na tela o valor 8.6
real: S, M;
S ← 0;
S ← S + A[ 4 ].N1B;S ← S + A[ 4 ].N2B;S ← S + A[ 4 ].N3B;S ← S + A[ 4 ].N4B;
M ← S / 4; // A variável S possui a soma das 4 // notas bimestrais do aluno da linha// 4 do vetor de registros A. M é a média.
111
Exemplo (vetor de registros): Escrever um programa que declare um vetor de registros e leia os nomes, os sobrenomes, as notas bimestrais de 45
alunos e calcule as médias bimestrais para cada aluno.
algoritmo registroEscolartipo registro = registroREinicio
caracter : NOME, SOBRENOME, PA;real : N1B, N2B, N3B, N4B, MEDIA;
fimtipo vetRegistroRE = vetor[1..45] : registroRE;vetRegistroRE : A; {declação da variável A}início
matReal : A;inteiro : I;caracter : NOMEPA;escreva("Informe o nome do PA: “);leia( NOMEPA );
112
continuação
para I de 1 até 45 passo 1 façainicio
escreva("Nome: “);leia( A[ I ].NOME )escreva("Sobrenome: “);leia( A[ I ].SOBRENOME )escreva("Nota do 1o Bimestre: “);leia( A[ I ].N1B )escreva("Nota do 2o Bimestre: “);leia( A[ I ].N2B )escreva("Nota do 3o Bimestre: “);leia( A[ I ].N3B )escreva("Nota do 4o Bimestre: “);leia( A[ I ].N4B );A[ I ].PA ← NOMEPA;A[ I ].MEDIA ← (A[ I ].N1B + A[ I ].N2B + A[ I ].N3B + A[ I ].N4B) / 4;
fimparafim
113
Exercício de Fixação1) Em um certo município, vários proprietários de imóveis estão em atraso
com o pagamento do imposto predial. Desenvolver um algoritmo quecalcule e imprima o valor da multa a ser paga por estes proprietários, considerando que:
– Os dados de cada imóvel – número de registro, valor do imposto e número de meses em atraso – devem ser lidos pelo teclado;
– As multas devem ser calculadas a partir do valor do imposto e deacordo com a seguinte tabela (lidos do teclado):
Valor do imposto % por mês em atrasoAté R$ 1000,00 1%De R$ 1000,01 a R$ 2.800,00 2%De R$ 2.800,01 a R$ 7.000,00 4%De R$ 7.000,01 a R$ 15.000,00 7%
Acima de R$ 15.000,01 10%– na saída deverão ser: impressos o NRO DO REGISTRO, VALOR DO
IMPOSTO, MESES EM ATRASO e a MULTA a ser paga.
114
2. Para cada uma das situações a seguir, declare as estruturas de dados:1. para um concurso de expositores de gado leiteiro precisa-
se armazenar os dados das 80 vacas, que são: número da inscrição, peso, idade, nome do proprietário e região;
2. para um apicultor necessita-se armazenar os dados de 230 colméias, que são: código, região, estado, qualificação (forte, médio, fraco), número de abelhas;
3. para um comerciante precisa-se armazenar os dados de 1500 produtos, que são: código, descrição, quantidade em estoque, quantidade mínima, preço, dada de fabricação e data de validade;
4. para uma biblioteca precisa-se armazenar os dados de 5000 livros, que são: código, título, categoria e data de empréstimo e data de devolução.
115
3. Fazer um algoritmo para cada um dos itens a seguir: 1. cadastrar imóveis a serem alugados/vendidos com os seguintes dados:
1. tipo (loja, apartamento, casa, kit), 2. endereço (rua, número, bairro, complemento), 3. valor, 4. situação (aluguel ou venda). 5. Mostrar todos os dados dos imóveis cadastrados;
2. cadastrar os produtos de um armazém com os seguintes dados:1. código, 2. descrição, 3. estoque mínimo, 4. estoque atual e preço. 5. Mostrar todos os dados dos produtos que contenham o estoque
atual menor que o estoque mínimo;