estrutura repeticao

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
Algoritmos e Estruturas de Dados I – Estrutura de Repetição
Profa. Mercedes Gonzales Márquez
*
Estrutura de Repetição
Referência bibliográfica : SALVETTI/BARBOSA e HARRY FARRER
Execução de uma seqüência de ações repetidas vezes. O computador abandona o fluxo natural da execução (de cima para baixo) e volta a executar a seqüência de ações desejada. Pode apresentar duas formas:
1.Repetição com variável de controle: 
O número de repetições no loop (laço) está previamente determinado pelo valor inicial e pelo valor final da variável de controle.
2.Repetição controlada por condição
Não sabemos a-priori quantas vezes executar a repetição. A execução do loop deve ser controlada por uma condição. A condição pode controlar a interrupção da repetição no início ou no final da sequência de comandos desta.
*
Repetição com variável de controle
1. Repetição com variável de controle
 Formato :
 Para variável_controle de valor_inicial até valor_final passo valor_passo repita
 seqüência de comandos
 Fim para
O número de repetições no loop (laço) está previamente determinado pelo valor inicial e pelo valor final da variável de controle. Quando valor_passo é 1, podemos omitir a especificação de passo.
 
*
Repetição com variável de controle
 Exemplo:
	Algoritmo <exemplo1>
	inteiro: i
	Inicio	
		Para i de 1 até 5 repita 
		 escreva (i)
	 	Fim Para
	Fim
*
Repetição com variável de controle
Exercício 2. (1º forma) Faça um algoritmo que imprima os 4 primeiros números inteiros pares positivos.
	
Algoritmo <pares>
inteiro: i
Inicio	
	Para i de 1 até 4 repita 
	 escreva (2*i)
	Fim Para
Fim
*
Repetição com variável de controle
Exercício 2. (2º forma) Faça um algoritmo que imprima os 4 primeiros números inteiros pares positivos.
	
Algoritmo <pares>
inteiro: i
Inicio	
	Para i de 2 até 8 passo 2 repita 
	 escreva (i)
	Fim Para
Fim
*
Repetição com variável de controle
Exercício 2. (3º forma) Faça um algoritmo que imprima os 4 primeiros números inteiros pares positivos.
	
Algoritmo <pares>
inteiro: i,n
Inicio
	n	←0
	Para i de 1 até 4 repita 
		n ←n+2
 		escreva (n)
	Fim Para
Fim
*
Repetição com variável de controle
Exercício 3. Faça um algoritmo que imprima a soma dos 4 primeiros números inteiros positivos.
Algoritmo <cincoprimeiros>
inteiro: i,s
Inicio
	s	←0
	Para i de 1 até 4 repita 
		s ←s+i
	Fim Para
	escreva (s)
Fim
*
Exercício 4. Faça um algoritmo que imprima a soma dos 4 primeiros números inteiros pares positivos.
Algoritmo <pares2>
inteiro: i,s
Inicio
	s	←0
	Para i de 1 até 4 repita 
		s ←s+2*i
	Fim Para
	escreva (s)
Fim
Repetição com variável de controle
*
Exercício 5. Faça um algoritmo que imprima a soma dos n primeiros números inteiros pares positivos.
Algoritmo <pares3>
inteiro: i,s,n
Inicio
	leia (n)
	s	←0
	Para i de 1 até n repita 
		s ←s+2*i
	Fim Para
	escreva (s)
Fim
Repetição com variável de controle
*
Exercício 6. Faça um algoritmo que imprima a soma dos n primeiros números inteiros ímpares positivos.
Algoritmo <impares>
inteiro: i,s,n
Inicio
	leia (n)
	s	←0
	Para i de 1 até n repita 
		s ←s+2*i-1
	Fim Para
	escreva (s)
Fim
Repetição com variável de controle
*
Algoritmo <soma>
inteiro: i,s
Inicio
	s ←1
	Para i de 1 até 100 repita 
		s ←s+1/(2*i)
	Fim Para
Fim
Exercício 7. Desenvolver um algoritmo para calcular a soma:
Repetição com variável de controle
*
Exercício 8. Tem-se a altura e o nome de 50 pessoas. Fazer um algoritmo que escreva o nome da pessoa mais alta. Se tiver mais de uma pessoa possuíndo a maior altura, escreva o nome de quaisquer delas.
Algoritmo <altura>
inteiro: i 
Literal: nome,nomemaisalta
Real:altura, maioraltura 
Inicio
	maioraltura←0
	Para i de 1 até 50 repita 
		leia (nome,altura)
		se (altura>maioraltura) então
			maioraltura←altura
			nomemaisalta←nome
		fim se
	Fim Para
	escreva (nomemaisalta,maioraltura)
Fim	
Repetição com variável de controle
*
Exercício 9. Num frigorífico existem 90 bois. Cada boi traz preso no pescoço um cartão contendo seu número de identificação e seu peso. Fazer um algoritmo que escreva o número e peso do boi mais gordo e do boi mais magro.
Algoritmo <bois>
inteiro: i,numero,gordo,magro
Real:peso,pesomenor, pesomaior
Inicio
	pesomenor←10000
	pesomaior←0
	Para i de 1 até 90 repita 
		leia (numero,peso)
		se (peso>pesomaior) então
			pesomaior←peso
			gordo←numero
		fim se
		se (peso<pesomenor) então
			pesomenor←peso
			magro←numero
		fim se
	Fim Para
	escreva (gordo,pesomaior)
	escreva (magro,pesomenor)
Fim	
Repetição com variável de controle
*
Exercício 10. Sendo H=1+1/2+1/3+1/4+...+1/N faça um algoritmo para calcular H. O número N é lido. 
Algoritmo <H>
inteiro: i,n
real: H
Inicio
	leia (n) 
	H ←0
	Para i de 1 até n repita 
		H ←H+1/i
	Fim Para
	escreva (H)
Fim
Repetição com variável de controle
*
Exercício 11. Imprimir os N primeiros termos da seqüência 
com 
Seja N=5. O primeiro termo é definido pela condição inicial e os demais são calculados pela formula de recorrência dada
Algoritmo <nprimeiros>
inteiro: i,n,y
Inicio
	leia (n) 
	y ←1
	escreva (y)
	Para i de 1 até n-1 repita 
		y ←y+2
		escreva (y)
	Fim Para
Fim
Repetição com variável de controle
*
Exercício 12. Faça um algoritmo que calcule a seguinte soma ( o símbolo representa somatório.
Algoritmo <somatorio>
inteiro: i,s
Inicio
	s ←0
	Para i de 1 até 10 repita 
		s ←s+i**2
	Fim Para
Fim
Resolvendo o somatório
Repetição com variável de controle
*
Exercício 13. Faça um algoritmo que calcule e escreva o valor da seguinte somatória
Algoritmo <somatorio2>
inteiro: i,s
Início
	s ←0
	Para i de 0 até 4 repita 
		s ←s+2**i/3**i
	Fim Para
Fim
Procurando uma fórmula 
Algoritmo <somatorio2>
inteiro: i,s
Início
	s ←1
	Para i de 1 até 4 repita 
		s ←s+2**i/3**i
	Fim Para
Fim
ou
Repetição com variável de controle
*
Exercício 14. Faça um algoritmo que calcule e escreva o valor da seguinte somatória
Procurando uma fórmula 
Algoritmo <somatorio2>
inteiro: i,s
Início
	s ←1
	Para i de 1 até 4 repita 
		s ←s+2**i/3**(i+1)
	Fim Para
Fim
Repetição com variável de controle
*
Exercício 15. Faça um algoritmo que calcule e escreva o valor da seguinte somatória
Procurando uma fórmula 
Algoritmo <somatorio2>
inteiro: i,s
Início
	s ←1
	Para i de 1 até 4 repita 
		s ←s+2**i/3**(5-i)
	Fim Para
Fim
Repetição com variável de controle
*
Exercício 16. Faça um algoritmo que calcule e escreva o valor da seguinte somatória
Procurando uma fórmula 
Algoritmo <somatorio2>
inteiro: i,s
Início
	s ←1
	Para i de 1 até 4 repita 
		s ←s+(-1 )**i*2**i/3**i
	Fim Para
Fim
Algoritmo <somatorio2>
inteiro: i,s
Início
	s ←1
	Para i de 1 até 4 repita 
		s ←s+(-2)**i/3**i
	Fim Para
Fim
Repetição com variável de controle
*
Exercício 17. Faça um algoritmo que calcule e escreva o valor da seguinte somatória
Algoritmo <somatorio2>
inteiro: i,s
Inicio
	s ←0
	Para i de 1 até 15 repita 
		s ←s+2**(i-1)/(16-i)**2
	Fim Para
Fim
Procurando uma fórmula 
Repetição com variável de controle
*
Exercício 18. Faça um algoritmo que calcule o valor do seno de A através da seguinte série:
 
 O valor de A e o número N de termos da série devem ser lidos.
Algoritmo <senoA>
inteiro: i,n
real: A
Inicio
	leia (n,A)
	soma←A
	den←1
	num←A
	Para i de 2 até n repita
		num← -num*A*A
		den←den*(2*i-1)*(2*i-2)
		soma←soma+num/den
	Fim Para
Fim
Repetição com variável de controle
*
Exercício 19. O número 3025 possui a seguinte característica: 
 	
Algoritmo <caracteristica>
inteiro: i
Inicio
Para i de 1000 até 9999 repita
	Se (((mod(i,100)+div(i,100))**2)=i)
		escreva (i)
	Fim se
Fim Para
Fim
 
Repetição com variável de controle
Faça um algoritmo que
pesquise e imprima todos os números de quatro algarismos que apresentam tal característica.
*
Exercício 20. 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, 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:
Essa seqüência chama-se seqüência de Fibonacci.
Repetição com variável de controle
*
(a) Mostre como os termos dessa série correspondem à solução do problema proposto.	
meses
Repetição com variável de controle
*
Algoritmo <fibonacci>
inteiro: i,n,fibonacci,fib0,fib1
Inicio
	leia (n)
	fib0 ←1
	fib1←1
	Para i de 2 até n repita 
		fibonacci ←fib0+fib1
		fib0 ←fib1
		fib1 ←fibonacci
	Fim Para
Fim
b) Redija um algoritmo para calcular a quantidade de casais de coelhos após n meses.
Repetição com variável de controle
*
Repetição controlada por condição
As vezes precisamos que nosso algoritmo realize uma certa quantidade de repetições, mas não sabemos o número exato de repetições necessárias. 
Exemplo:
Faça um algoritmo que determine os quadrados de um conjunto de números inteiros positivos.
Neste caso não podemos usar a estrutura de repetição com variável de controle pois o conjunto de dados de entrada é formado por um número desconhecido de elementos. Não é fornecida pelo usuário a quantidade de números existem no conjunto.
O que desejamos é repetir o bloco de comandos (leitura, comandos, saída) enquanto existir um número inteiro positivo na lista de entrada dos dados.
*
Repetição controlada por condição
Nestes casos usamos a repetição controlada por condição.
Repetição controlada por condição.
Não sabemos a-priori quantas vezes executar a repetição. A execução do loop deve ser controlada por uma condição.
Esta repetição é também chamada de repetição controlada por sentinela ou flag.
No exemplo, a condição para interromper a repetição é que o número não seja positivo. O valor sentinela será então qualquer número que não seja positivo. Por exemplo, o número zero ou o número -1.
*
Representamos essa estrutura de repetição através de uma das duas instruções: 
(1) enquanto-faça 
(2) repita-até-que.
As duas instruções são equivalentes. Entretanto, há situações em que uma é preferível à outra.
Repetição controlada por condição
*
Instrução Enquanto-Faça
Formato.
Enquanto <condição> faça 
<bloco de comandos>
Fim enquanto
Nesta instrução, <bloco de comandos> só é executado se <condição> for verdadeira. 
Antes de ser executado pela primeira vez é necessário que a <condição> esteja definida. 
Se na primeira vez em que a <condição> for testada ela for falsa, o loop não é executado nenhuma vez. 
Dentro do loop deve existir uma instrução que altera o valor da <condição>, caso contrário, o loop pode se tornar de execução infinita (não parar).
Repetição controlada por condição
*
Exemplo 1. Faça um algoritmo que determine os quadrados de um conjunto de números inteiros positivos.
Algoritmo <quadrados>
inteiro: numero
Inicio	
	leia (numero)
	enquanto (numero>0) faça 
	 escreva (numero*numero)
		 leia (numero)
	fim enquanto
Fim
Repetição controlada por condição
*
Exemplo 2: Faça um algoritmo que leia uma lista de números inteiros. A leitura de dados terminará quando for ingressado o número zero (flag). Pede-se a soma e a média de todos os números lidos (excluindo o zero).
Algoritmo <media>
inteiro: numero,soma,cont
real: media
Inicio	
	cont ←0
	soma ←0
	leia (numero)
	enquanto (numero<>0) faça 
	 soma ← soma+numero
		cont ← cont+1
		 leia (numero)
	fim enquanto
	se (cont>0) então
		media ←soma/cont
		escreva (media)
	fim se
Fim
Repetição controlada por condição
*
Exercício 3. Escrever um algoritmo que receba dois números inteiros positivos, e determine o produto dos mesmos, utilizando o seguinte método de multiplicação: 
dividir, sucessivamente, o primeiro número por 2, até que se obtenha 1 como quociente;
paralelamente, dobrar, sucessivamente, o segundo número;
somar os números da segunda coluna que tenham um número ímpar na primeira coluna. O total obtido é o produto procurado.
Exemplo:						9 x 6
			9		 6→		 6
			4		12	
			2		24
			1		48→		+48
								___
								 54
Repetição controlada por condição
*
Algoritmo <produto>
inteiro: i,a,b,pro
Inicio
	leia (a,b)
	pro←0
	Enquanto (a<>1) faça
		Se (mod(a,2)<>0) então
			pro←pro+b
		Fim se
		a←div(a,2)
		b←b*2
	Fim enquanto
	pro ←pro+b
Fim
Repetição controlada por condição
*
Exemplo 4: Faça um algoritmo que encontre a primeira potência de 2 maior que 1000.
Repetição controlada por condição
*
Instrução Repita-Até-Que
Formato.
repita 
<bloco de comandos> 
até que <condição>
 
Nesta instrução, <bloco de comandos> pelo menos uma vez porque somente após a sua execução a <condição> é testada. 
Dentre as instruções do loop deve existir pelo menos uma que altere o valor de <condição>.
Para o mesmo problema as condições de controle dos comandos enquanto-faça e repita-até-que são condições complementares. Observe que a negação de A>0 é A<=0 e vice-versa.
Repetição controlada por condição
*
Algoritmo <quadrados>
inteiro: numero
Inicio	
	leia (numero)
	repita
		escreva (numero*numero)
		leia (numero)
	até que (numero<=0) 
Fim
Algoritmo <quadrados>
inteiro: numero
Inicio	
	leia (numero)
	enquanto (numero>0) faça 
	 escreva (numero*numero)
		 leia (numero)
	fim enquanto
Fim
Exemplo comparativo.- Faça um algoritmo que determine os quadrados de um conjunto de números inteiros positivos.
Observe que a primeira estrutura de repetição (enquanto-faça) é mais conveniente para resolver o problema proposto. 
Repetição controlada por condição
*
Exercício2: Suponha que no ano N a população americana seja maior que a brasileira. Sabendo-se que os Estados Unidos possuem um crescimento anual de 2% na sua população e que o Brasil tem crescimento anual de 4%, determinar o ano em que as duas populações serão iguais (em quantidade). São dados os números de habitantes dos Estados Unidos e do Brasil no ano N.
Algoritmo <populacao>
inteiro: ano,br,am
Inicio	
	leia (ano,br,am)
	enquanto (am>br) faça 
		am ←am*1.02
		br ←br*1.04
		ano ←ano+1
	fim enquanto
 escreva (ano)
Fim
Algoritmo <populacao>
inteiro: ano,br,am
Inicio	
	leia (ano,br,am)
	repita
		br ←br*1.04
		am ←am*1.02
		ano ←ano+1
	até que (br>=am)
	escreva (ano)
Fim
*
1. Se usarmos repita-até-que, 
as duas populações primeiro sofrem um acréscimo, e depois o teste da condição será executado.
Esta instrução é indicada se considerarmos sabido que inicialmente a população americana é de fato maior que a população brasileira.
2. Se usarmos enquanto-faça
Se os valores de entrado fossem desconhecidos, esta instrução é mais adequada pois primeiro o teste da condição é efetuado e conforme o resultado do teste o bloco será o não executado dentro do loop.
Repetição controlada por condição
*
	Tarefas:
Estude os exercícios resolvidos de estrutura de repetição do livro Introdução à Programação 500 Algoritmos Resolvidos de Anita Lopes.
Estude a lista de exercícios resolvidos de estrutura de repetição que se encontra no site da disciplina.
Resolva a lista de exercícios propostos de estrutura de repetição que também já está disponível no site da disciplina.
Estrutura de Repetição
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*