AP Aulas 05, 06 e 07

Prévia do material em texto

*
*
Algoritmos e Programação
Ruy Barbosa Figueiredo Júnior
Aulas 05, 06 e 07 – AED I
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Este material foi reproduzido do livro: Lógica de Programação – Forbellone / Eberspacher – Capítulo 3
Lógica de Programação
Estruturas de Controle
Lógica de Programação – Forbellone / Eberspacher – Capítulo 3
Este material foi reproduzido do livro: Lógica de Programação – Forbellone / Eberspacher – Capítulo 3
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
O Fluxo de Controle segue a mesma seqüência linear da nossa escrita, ou seja:
De cima para baixo;
Da esquerda para direita
Cada ação é seguida de um ;
Objetiva separar uma ação da outra
Indica que a próxima ação da seqüência deve ser executada
Estrutura Seqüencial
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Algoritmo 3.2 - Média Aritmética
Estrutura Seqüencial
	início
		// declaração de variáveis
		real: N1, N2, N3, N4, // notas bimestrais
					MA; // média anual
		// entrada de dados
		leia (N1, N2, N3, N4);
		// processamento
		MA ¬ (N1 + N2 + N3 + N4) / 4;
		// saída de dados
		escreva (MA);
	fim.
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Exemplos
1- Construa um algoritmo que calcule a quantidade de latas de tinta necessárias e o custo para pintar tanques cilíndricos de combustível, em que são fornecidos a altura e o raio desse cilindro.
Sabendo que:
A lata de tinta custa R$ 50,00
Cada lata contém 5 litros
Cada litro pinta 3 metros quadrados
	Dados de entrada: altura (H) e raio (R)
	Dados de Saída: custo (C) e quantidade (QTDE)
Utilizando o planejamento reverso, sabemos que:
O custo é dado pela quantidade de latas * R$ 50,00;
A quantidade de latas é dada pela quantidade total de litros /5 ;
A quantidade total de litros é dada pela área do cilindro/3 ;
A área do cilindro é dada pela área da base + área lateral;
A área da base é (PI * pot(R,2)); 
A á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
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
 “Algoritmo: Quantidade de Latas de Tinta”
início
fim
	real: H, R;
	real: C, Qtde, Area, Litro;
	leia (H, R);
	Area (3.14 * pot (R,2) + (2 * 3,14 * R * H);
	Litro Area/3;
	Qtde Litro/5;
	C Qtde * 50,00;
	escreva (C, Qtde) ;
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
São aquelas que permitem alterar o Fluxo de Execução, de forma a selecionar qual parte deve ser executada
Essa “decisão” de execução é tomada a partir de uma condição, que pode resultar apenas em Verdade ou Falsidade
Uma condição é representada por expressões relacionais ou lógicas
As estruturas de seleção podem ser classificadas em simples, compostas ou encadeadas
Estruturas de Seleção
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Seleção Simples
	se <condição> então
		início // início do bloco verdade
			comando 1;
			comando 2;
			...
			comando n;
		fim; // fim do bloco verdade
	fimse;
Quando a <condição> for verdadeira o “bloco verdade” é executado
Quando a <condição> for falsa o “bloco verdade” não é executado
Quando existir somente apenas uma ação após a cláusula, basta escrevê-la; já quando precisamos colocar diversas ações é necessários usar um bloco delimitado por início e fim.
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Seleção Simples
	início
		// declaração de variáveis
		real: N1, N2, N3, N4, // notas bimestrais
					MA; // média anual
		// entrada de dados
		leia (N1, N2, N3, N4);
		// processamento
		MA ¬ (N1 + N2 + N3 + N4) / 4;
		// saída de dados
		escreva (MA);
		se (MA >= 7) então
			escreva (“Aluno Aprovado !”);
		fimse;
	fim.
Algoritmo 3.4 - Média Aritmética com Aprovação
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Seleção Composta
	se <condição> então
		início // início do bloco verdade
			comando 1;
			comando n;
		fim; // fim do bloco verdade
	senão
		início // início do bloco falsidade
			comando 1;
			comando n;
		fim; // fim do bloco falsidade
	fimse;
Quando a <condição> for verdadeira o “bloco verdade” é executado
Quando a <condição> for falsa o “bloco falsidade” é executado
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
	início
		// declaração de variáveis
		real: N1, N2, N3, N4, // notas bimestrais
					MA; // média anual
		leia (N1, N2, N3, N4);
		MA ¬ (N1 + N2 + N3 + N4) / 4;
		escreva (MA);
		se (MA >= 7) então
			início
				escreva (“Aluno Aprovado !”); 
				escreva (“Parabéns !”);
			fim;
		senão
			início
				escreva (“Aluno Reprovado !”);
				escreva (“Estude mais !”);
			fim;
		fimse;
	fim.
Algoritmo 3.5 - Média Aritmética com aprovação e reprovação
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Seleção Encadeada
Ocorre quando uma seleção tem como ação uma outra seleção
Uma seleção encadeada pode ser:
Heterogênea: Quando não é possível identificar padrão de comportamento, não conseguimos identificar um padrão lógico de construção.
Homogênea: Quando é possível identificar padrão de comportamento
se – então – se: quando depois de cada então ocorre outro se
se – senão – se: quando depois de cada senão ocorre outro se
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
	se <condição 1> 
			então
					se <condição 2> 
							então
									início // início do bloco verdade 1
										C 1;
										 .
										 .
										C n;
									fim; // fim do bloco verdade 1
					fimse;
Seleção Encadeada Heterogênea
Podemos construir uma estrutura de seleção de diversas formas, sendo que, ao encadearmos várias seleções, as diferentes possibilidades de construção tendem a um número elevado.
Quando não conseguimos identificar um padrão lógico de construção em uma estrutura de seleção encadeada, dizemos que ela é uma estrutura de seleção heterogênea. 
O modelo a seguir expressa um exemplo de uma seleção heterogênea.
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
			senao
					se <condição 3> 
						então
									início // início do bloco verdade 2
										C 1;
										 .
										 .
										C n;
									fim; // fim do bloco verdade 2
					
					senao
									se <condição 4> 
										então	
										 se <condição 5> 
										 então
											 CV; // comando verdade
										 fimse;
									senao
										CF; // comando falsidade
							 fimse; 
 fimse;
 fimse;
Seleção Encadeada Heterogênea
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Seleção Encadeada Heterogênea
Dados três valores A, B, C, verificar se eles podem ser os comprimentos dos lados de um triângulo, se forem, verificar se compõe um triângulo equilátero, isóceles, ou escaleno. Informar se não compuserem nenhum triângulo. 
Exemplos:
Dados de entrada: três lados de um suposto triângulo (A, B, C).
Dados de Saída – Mensagens: não compõem triângulo, triângulo equilátero, triângulo isósceles, triânguloescaleno.
Oque é um triângulo ?
Resp: figura geométrica fechada de três lados, em que cada um é menor do que a soma dos outros dois
O que é um triângulo equilátero ?
Resp: um triângulo com três lados iguais.
O que é um triângulo isósceles ?
Resp: um triângulo com dois lados iguais
O que é um triângulo escaleno ?
Resp: Um triângulo com todos os lados diferentes
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Tabela de decisão:
Estruturas de Seleção
Traduzindo as condições para expressões lógicas:
É triângulo: (A < B + C) e (B < A+C) e (C < A + B)
É equilátero: (A = B) e (B = C)
É isósceles: (A = B) ou (A=C) ou (B = C )
É escaleno: (A <> B) e (B <> C) e (A <> C)
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Seleção Encadeada Heterogênea
	início
		inteiro: A, B, C; // tamanho dos lados
		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 (“Triangulo Equilátero”); 
			senão
				se (A=B) ou (B=C) ou (A=C) então
					escreva (“Triângulo Isósceles”);
				senão
					escreva (“Triangulo Escaleno”);
				fimse;
			fimse;
		senão
			escreva (“Estes valores não formam um triângulo”);
		fimse;
	fim.
Algoritmo 3.6 – Tipos de Triângulo
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Seleção Encadeada Homogênea
Chama-se de seleção encadeada homogênea a construção de diversas estruturas de seleção encadeadas que seguem um determinado padrão lógico
se – então – se 
	se <Cond1> então 
		se <Cond2> 	então 
			se <Cond3>	então 
				se <Cond4> então W;
				fimse;
			fimse;
		 fimse;
	 fimse;
É equivalente a:
	se <Cond1> e <Cond2> e <Cond3> e <Cond4> então W;
	fimse;
Esta construção segue um padrão. Após cada então existe outro se, não existem senões; temos uma estrutura encadeada homogênea. Outro fator importante é que o comando W só será executado quando todas as condições forem ao mesmo tempo verdadeiras; portanto seria equivalente a escrever, simplificadamente:
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Seleção Encadeada Homogênea
se – então – se 
	se <Cond1> então 
		se <Cond2> 	então 
			se <Cond3>	então 
				se <Cond4> então W;
				fimse;
			fimse;
		 fimse;
	 fimse;
É equivalente a:
	se <Cond1> e <Cond2> e <Cond3> e <Cond4> então W;
	fimse;
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Vamos supor que em determinado algoritmo uma variável X possa assumir apena 4 valores, V1, V2, V3, V4, e que exista um comando diferente que será executado para cada valor armazenado em X, temos por exemplo a seguinte situação:
	se X=V1 então 
		C1;
	fimse;
	se X=V2 então 
		C2;
	fimse;
	se X=V3 então 
		C3;
	fimse;
	se X=V4 então 
		C4;
	fimse;
se X=V1 
	então C1;
	senão se X=V2 
						 então C2;
				 		 senão se X=V3 
												 então C3;
												 senão se X=V4 
															 então C4; 
														 fimse;
											fimse;
					fimse;
fimse;
se – senão – se
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Seleção de Múltipla Escolha
Seleções encadeadas homogêneas se-senão-se são bastante freqüentes para o tratamento de listas de valor
Para simplificar a escrita, pode-se utilizar o comando escolha.
Adaptando o algoritmo anterior:
	escolha X
		caso V1: C1;
		caso V2: C2;
		caso V3: C3;
		caso V4: C4;
	fimescolha;
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Seleção de Múltipla Escolha
Construa um algoritmo que, tendo como dado entrada o preço de um produto e seu código de origem, mostre o preço junto de sua procedência. Caso o código não seja de nenhum dos especificados, o produto deve ser encarado como importado. Siga a tabela de códigos a seguir
	
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Seleção de Múltipla Escolha
	início
		real: Preço;
		inteiro: Origem;
		leia (Preço, Origem);
		escolha Origem
			caso 1: escreva (Preço, “ – produto do Sul”);
			caso 2: escreva (Preço, “ – produto do Norte”);
			caso 3: escreva (Preço, “ – produto do Leste”);
			caso 4: escreva (Preço, “ – produto do Oeste”);
			caso 7, 8, 9: escreva (Preço, “ – produto do Sudeste”);
			caso 10..20: escreva (Preço, “ – produto do Centro-Oeste”);
			caso 5, 6, 25..50: escreva (Preço, “ – produto do Nordeste”);
			caso contrário: escreva (Preço, “ – produto importado”);
		fimescolha;
	fim.
Algoritmo 3.7 – Múltipla Escolha
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Estruturas de Repetição
São aquelas que permitem executar mais de uma vez (repetir) um determinado trecho do algoritmo
O trecho do algoritmo em repetição é também chamado de laço (ou “loop”)
As repetições devem ser sempre finitas
Quanto a quantidade de repetições, os laços podem ser
Pré-determinados: Sabe-se antes a quantidade de execuções
Indeterminados: Não se conhece a quantidade de execuções
Quanto ao critério de parada, os laços podem utilizar
Teste no início
Teste no final
Variável de controle
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Repetição com Teste no Início
Laço que verifica antes de cada execução, se é “permitido” executar o trecho do algoritmo
Trata-se de um laço que se mantém repetindo enquanto uma dada condição permanecer verdadeira
	enquanto <condição> faça
		comando 1;
		comando 2;
		...
		comando n;
	fimenquanto;
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Repetição com Teste no Início
Contador: Variável que reproduz o processo de contagem
início
	inteiro: CON;
	CON ¬ 0;
	enquanto CON < 3 faça
		CON ¬ CON + 1;
	fimenquanto;
fim.
CON
0
1
2
3
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Repetição com Teste no Início
Voltando ao algoritmo que calcula a média aritmética, quantas vezes ele será executado ? Do modo em que se encontra o processamento, só é realizado uma única vez e para um único aluno. E se forem mais alunos ?
Como já vimos, podemos solucionar esse problema escrevendo o algoritmo em questão uma vez para cada aluno. Ou seja, se forem 50 alunos, teríamos de escrevê-lo 50 vezes !!! Trata-se de uma solução simples porém inviável.
Outro modo de resolver essa questão seria utilizar a mesma sequência de comandos novamente, ou seja, teríamos de realizar um retrocesso – ao início dos comandos – para cada aluno, fazendo, portanto, com que o fluxo de execução repetisse certo trecho do algoritmo, o que nessa aplicação corresponderia a repetir o mesmo trecho 50 vezes, sem, no entanto ter de escrevê-lo 50 vezes.
A esses trechos do algoritmo que são repetidos damos o nome de laços de repetição.
O número de repetições pode ser indeterminado, porém necessariamente finito.
Os laços de repetição também são conhecidos como loops ou looping.
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Repetição com Teste no Início
	início
		// declaração de variáveis
		real: N1, N2, N3, N4, // notas bimestrais
					MA; // média anual
		inteiro: CON; // contador
		CON ¬ 0; // inicialização do contador
		enquanto (CON < 50) faça // teste da condição de parada
			leia (N1, N2, N3, N4);
			MA ¬ (N1 + N2 + N3 + N4) / 4;
			escreva (MA);
			se (MA >= 7) então
				escreva (“Aluno Aprovado.Parabéns !”); 
			senão
				escreva (“Aluno Reprovado. Estude mais !”);
			fimse;
			 CON ¬ CON + 1; // incremento do contador
		fimenquanto;
	fim.
Algoritmo 3.8 - Média Aritmética para 50 alunos
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Repetição com Teste no Início
Acumulador: Variável que reproduz o processo de acumulação
início
	inteiro: CON, X, ACM;
	CON ¬ 0;
	ACM ¬ 0;
	enquanto CON < 3 faça
		CON ¬ CON + 1;
		leia (X);
		ACM ¬ ACM + X;
	fimenquanto;
fim.
CON
0
1
2
3
ACM
0
5
7
11
X
5
2
4
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Repetição com Teste no Início
Algoritmo 3.9 - Média Aritmética da turma de 50 alunos acumulando as médias e mostrando a média anual da turma
	início
		// declaração de variáveis
		real: MA, // média anual de dado aluno
				 ACM, // Acumulador
				 MAT; // Média Anual da Turma
		inteiro: CON; // contador
		CON ¬ 0; // inicialização do contador
		ACM ¬ 0; // inicialização do acumulador
		enquanto (CON < 50) faça // teste da condição de parada
			leia (MA);
			ACM ¬ ACM + MA; // soma em ACM os valores lidos em MA
			CON ¬ CON + 1; // incremento do contador
		fimenquanto;
		MAT ¬ ACM / 50; // calculo da média anual da turma
		escreva (“média anual da turma = “, MAT);
	fim.
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Repetição com Teste no Final
Laço que verifica depois de cada execução, se é “permitido” continuar executando o trecho do algoritmo
Trata-se de um laço que se mantém repetindo até que uma dada condição se torne verdadeira
	repita
		comando 1;
		comando 2;
		...
		comando n;
	até <condição>;
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Repetição com Teste no Final
O algoritmo anterior utiliza o pré-conhecimento a quantidade de alunos da turma da qual se desejava a média geral, o que permitiu construir um laço de repetição com quantidade pré-determinada de execuções. Entretanto, se não soubéssemos quantos eram os alunos, o que faríamos para controlar o laço de repetição ?
Precisaríamos de um laço que fosse executado por uma quantidade indeterminada de vezes. Assim, teríamos de encontrar outro critério de parada, que possibilitasse que o laço fosse finalizado após a última média anual (independente de quantas sejam) ter sido informada. Isso pode ser feito utilizando um valor predefinido como finalizador, a ser informado após a última média.
Para aplicar este conceito ao algoritmo média geral da turma, usaremos como finalizador o valor -1 que, quando encontrado, encerra o laço sem ter seu valor computado ao acumulador. 
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Repetição com Teste no Final
	início
		// declaração de variáveis
		real: MA, // média anual de dado aluno
				 ACM, // Acumulador
				 MAT; // Média Anual da Turma
		inteiro: CON; // contador
		CON ¬ 0; // inicialização do contador
		ACM ¬ 0; // inicialização do acumulador
		repita
			leia (MA);
			ACM ¬ ACM + MA; // soma em ACM os valores lidos em MA
			CON ¬ CON + 1; // incremento do contador
		até (CON >= 50); // teste da condição de parada
		MAT ¬ ACM / 50; // calculo da média anual da turma
		escreva (“média anual da turma = “, MAT);
	fim.
Algoritmo 3.12 - Média Aritmética da turma com Repita
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Repetição com Variável de Controle
Laço simplificado para utilização em repetições de quantidade predeterminada
Incorpora internamente o funcionamento de um contador de repetições
	para V de vi até vf passo p faça
		comando 1;
		comando 2;
		...
		comando n;
	fimpara;
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Repetição com Teste no Final
	início
		// declaração de variáveis
		real: MA, // média anual de dado aluno
				 ACM, // Acumulador
				 MAT; // Média Anual da Turma
		inteiro: V; // contador
		ACM ¬ 0; // inicialização do acumulador
		para V de 1 até 50 passo 1 faça
			leia (MA);
			ACM ¬ ACM + MA; // soma em ACM os valores lidos em MA
		fimpara;
		MAT ¬ ACM / 50; // calculo da média anual da turma
		escreva (“média anual da turma = “, MAT);
	fim.
Algoritmo 3.12 - Média Aritmética da turma com Para
*
*
Cursos: Engenharias
Disciplina: Algoritmos e Estruturas de Dados I
Prof. Ruy Barbosa Figueiredo Júnior
Comparação entre Estruturas de Repetição
Aprendemos 3 maneiras de construir laços de repetição
É importante perceber que existem laços mais adequados ou convenientes para cada situação
*
*
Perguntas
*
*
Bom Feriado a Todos !!!!!!!!!!!!!!
*
*
Referências
FORBELLONE, André Luiz Villar; EBERSPÄCHER, Henri Frederico. Lógica de programação: a construção de algoritmos e estrutura de dados. 3.ed. São Paulo: Makron Books do Brasil, 2010. 
GUIMARÃES, Ângelo de Moura; LAGES, Newton Alberto de Castilho. Algoritmos e estruturas de dados. Rio de Janeiro: Livros Técnicos e Científicos, 1994. 
ZIVIANI, Nivio. Projeto de Algoritmos com implementações em Java e C++, 2007.
*
An-1 para An - 
*
An-1 para An - 
*
An-1 para An -