BC & T Universidade Federal do ABC Estruturas de repetição estão divididas em três tipos: – Estrutura enquanto (while) – Estrutura repita (do while) – Estrutura para (for) • Quando uma seqüência de comandos deve ser executada repetidas vezes usamos uma estrutura de repetição. • A estrutura de repetição, assim como a de decisão, envolve sempre a avaliação de uma condição. • Também conhecidas como laços de repetição ou loops. bloco Um arquivo chamado resultado.txt armazena o resultado final da disciplina de modo que cada linha tem duas colunas, a primeira tem o número de matrícula de todos os alunos e a segunda coluna a situação final do aluno: aprovado ou reprovado. Queremos determinar a quantidade de alunos aprovados. 01222 03440 01999 02113 01110 12345 01010 02900 aprovado reprovado aprovado aprovado reprovado aprovado aprovado aprovado Um arquivo chamado resultado.txt armazena o resultado final da disciplina de modo que cada linha tem duas colunas, a primeira tem o número de matrícula de todos os alunos e a segunda coluna a situação final do aluno: aprovado ou reprovado. Queremos determinar a quantidade de alunos aprovados. Um solução: 1. Se não é fim do arquivo, leia uma linha do arquivo; 2. se a linha corresponde a um aluno aprovado • então incremente o contador de alunos aprovados • senão, volte para o passo 1. • A estrutura de repetição enquanto permite especificar instruções que devem ser repetida enquanto determinada condição for verdadeira • Exemplo: enquanto não terminar o arquivo, leia linha e incremente contador de aprovados se for o caso. •O corpo da enquanto pode instrução ou um execução estrutura ser uma bloco de bloco • Quando a condição da estrutura enquanto se tornar falsa, a ação (ou bloco de ações) da estrutura será pulada. • O programa continuará com a ação imediatamente após a estrutura enquanto. • IMPORTANTE: você deve sempre prever o comando, ou ação, que tornará falsa a condição do comando enquanto, caso contrário, seu programa entrará em loop infinito. bloco bloco condição ? F Pseudolinguagem enquanto <condição> faça <bloco_de_execução> início V Leonardo de Pisa (ou Fibonacci, 1170 - 1250) descreveu o crescimento de uma população de coelhos por uma sequência de números que agora é conhecida por sequência de Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... Essa sequência é definida por F(1) = F(2) = 1 e se n > 2 então F(n) = F(n-1) + F(n-2). Dado um inteiro n>0, obter F(n), o n-ésimo número de Fibonacci. Esboço de uma solução: 1. Dado n; 2. se n=1 ou n=2, então responda “F(n)=1”; 3. senão, tome i igual a 2 e faça 3.2. i ← i+1; 3.3. F(i) ← F(i-1) + F(i-2); 3.4. se i<n então volte para 3.2; 4. responda “F(n)=” F(i). Obs: A linha 3.1 é executada apenas uma vez e a linha 3.3 aumenta o valor da variável i até que i=n e, nesse caso, o laço termina pois a condição na linha 3.4 torna-se falsa. Exercício: Resolver usando enquanto. Algoritmo Fibonacci inicio inteiro n, a, b, prox, cont; leia (n); a ← b ← 1; se ( n=1 n=2 ) entao inicio escreva (b); fimentao senao inicio cont ← 2; enquanto ( cont <> n ) faça inicio prox ← a + b; a ← b; b ← prox; cont ← cont + 1; fimenquanto fimsenao escreva(b); fimalgoritmo. Sabe-se que um número inteiro positivo da forma n³ é a soma de n números ímpares conscutivos. Por exemplo, 1^3 = 1 2^3 = 3+5 3^3 = 7+9+11 4^3 = 13+15+17+19, ... n^3 = k + (k+2) + (k+4) + ... + (k+2(n -1)), para algum k ímpar. Dado um inteiro n>0, determinar k tal que n³ pode ser escrito como soma de n ímpares consecutivos como descrito acima. Esboço de uma solução: 1. leia(n) 2. k=1; 3. soma = k + (k+2) + (k+4)+ ... + (k + 2(n -1)), para algum k; 4. se (soma = n³) então achou, responda k; 5. senão incrementa k de 2 e volta pra linha 3. Problema: Como avaliar k + (k+2) + (k+4)+ ... + (k + 2(n -1))? Como avaliar k + (k+2) + ... + (k + 2(n -1))? Outro laço: 1. dado k, dado n e inicializadas com 0 as variáveis i e soma; 2. enquanto i <= 2(n-1) faça 2.1. soma ← soma + (k + i); 2.2. i← i+2; Algoritmo Cubo como soma de ímpares consecutivos início inteiro: n, soma, k, i; lógico: achou; leia ( n ); // n>=1 achou ← falso; k ← 1; enquanto ( ~achou ) faça inicio i ← soma ← 0; enquanto ( i < 2*n ) faça inicio soma ← soma + (k + i); i ← i + 2; fimenquanto se ( soma = n^3 ) entao inicio achou ← verdadeiro; fimentao senao inicio k ← k + 2; fimsenao fimenquanto escreva(k); fimalgoritmo • • Características de funcionamento: Não é necessário o conhecimento prévio do número de repetições Executa a repetição enquanto a condição for verdadeira, testando-a desde seu início Os comandos do loop podem não ser executados instruções Validação inicial enquanto <condição> faça <bloco> fimenquanto • O que indica quantas vezes uma repetição será realizada? • A estrutura enquanto não oferece este recurso. • Solução: uso de um contador, ou variável contadora, que tem um certo valor inicial (atribuído fora do laço) e é incrementada a cada repetição. • Exemplo de contador: inteiro cont; // declaração do contador cont 0; // inicialização do contador cont cont + 1; // incrementa contador em uma unidade • Associado O que ao indica quantas vezes CONTADOR, devemos ter: uma repetição será realizada? 1 – Atribuição de Valor Inicial Definição enquanto de Condição deoferece Continuidade Parada do Laço • 2A–estrutura não este ou recurso. Repetição • de Solução: uso de um contador, ou variável contadora, 3 – Definição de Passo (Incremento/Aumento ou que tem um certo valor inicial (atribuído fora do laço) e é Decremento/Diminuição) do Valor do Contador incrementada a cada repetição. • Os Exemplo dedevem contador: três itens ser construídos de forma a permitir que o Laço de Repetição realize o que se pede. Isto é inteiro cont; // declaração do contador responsabilidade do programador!!! cont 0; // inicialização do contador cont cont + 1; // incrementa contador em uma unidade Usamos i no exemplo 3: i ← 0; enquanto ( i < 2*n ) faça inicio soma ← soma + (k + i); i ← i + 2; fimenquanto Usamos cont no exemplo 2: cont ← 2; enquanto ( cont <> n ) faça inicio prox ← a + b; a ← b; b ← prox; cont ← cont + 1; fimenquanto • Valor de sentinela (finalizador, de sinal ou de flag) – valor especial que indica o final de entrada de dados. Usado pelo usuário para indicar final do laço de repetição. • Exemplo: se a entrada de um problema é um sequência de inteiros positivos podemos usar -1 como sinal de fim da entrada. Uso do sentinela para indicar o fim da entrada de dados: Escreva um algoritmo que determine se números inteiros e positivos são pares, ou ímpares. Utilize a estrutura enquanto para permitir a entrada da seqüência de números. O último número, que não será considerado na análise, deve assumir o valor –1 (sentinela). Algoritmo ParImpar início inteiro: valor, resto; string: mensagem; leia ( valor ); enquanto ( valor –1 ) faça resto valor mod 2; se ( resto=0 ) então inicio mensagem “Número par”; fimentao senão inicio mensagem “Número ímpar”; fimsenao escreva( mensagem); leia ( valor ); fimenquanto fimalgoritmo • Outro exemplo: em computação EOF é uma condição que indica fim-de-arquivo (End-Of-File). Concretamente, é um flag cujo valor de fato depende do sistema operacional e que não corresponde a um carater válido, usualmente é -1. Um arquivo chamado resultado.txt armazena o resultado final da disciplina de modo que cada linha tem duas colunas, a primeira tem o número de matrícula de todos os alunos e a segunda coluna a situação final do aluno: aprovado ou reprovado. Queremos determinar a quantidade de alunos aprovados. 01222 03440 01999 02113 01110 12345 01010 02900 aprovado reprovado aprovado aprovado reprovado aprovado aprovado aprovado String: linha; inteiro: aprovados; aprovados ← 0; enquanto (~EOF(resultado.txt)) faça inicio leia (linha); se (linha termina em “aprovado”) inicio aprovados ← aprovados + 1; fimse fimenquanto escreva(aprovados); fimalgoritmo Obs.: EOF = “End Of File” = “Fim de Arquivo” JAVA Pseudolinguagem // Não é padrão while <condição> <comando>; enquanto <condição> faça <bloco> // Padrão com {} while <condição> { <comandos> } Algumas linguagens (Ex.: Java, C#, C++, C) contém operadores especiais para simplificar a atribuição de valores às variáveis As Estruturas de Repetição demandam o uso frequente de operadores associados às variáveis de controle Portanto, recomenda-se usar os seguintes operadores em Java (seja i uma variával): i++; ou ++i;: i--; ou --i;: Se colocado sozinho em uma linha, equivale ao comando: i = i + 1; No caso de contador: adiciona 1 ao valor do contador Se colocado sozinho em uma linha, equivale ao comando: i = i - 1; No caso de contador: subtrai 1 do valor do contador Para o caso de existir mais de um comando na mesma linha em que estes operadores, a colocação de “++” (ou “--”) antes ou depois da variável define a ordem em que as operações serão executadas. Em laços de repetição, deve-se usar “i++” ou “i—”. Existem ainda operadores em Java para outras operações aritméticas (sejam i e b duas variáveis): i+=b; i-=b; Equivale ao comando: i = i * b; i/=b; Equivale ao comando: i = i - b; i*=b; Equivale ao comando: i = i + b; Equivale ao comando: i = i / b; Estes operadores são menos utilizados, mas i++; e i--; são muito comuns na programação em Java! import java.io.*; import java.util.*; public class resultado { public static void main(String[] args) throws FileNotFoundException { String linha, arquivo="resultado.txt"; Scanner sc = new Scanner(new File(arquivo)); int aprovados = 0, total = 0; while ( sc.hasNext() ) { total = total + 1; //computa o numero de alunos linha = sc.nextLine() ; if ( linha.endsWith("aprovado") ){ aprovados = aprovados + 1; } } System.out.println("número de alunos matriculados: " + total); System.out.println("número de alunos aprovados: " + aprovados); System.out.println("número de alunos reprovados: " + (totalaprovados)); }//fim do main }//fim da classe import java.util.*; public class fibonacci { public static void main (String[] args) { Scanner s = new Scanner(System.in); int n=0, a=1, b=1, cont=2, prox=0; System.out.print("Entre n: "); n = s.nextInt(); if ( n==1 || n==2 ) System.out.println( "F("+n+")="+b ); else { while ( cont != n ) { prox = a + b; a = b; b = prox; cont = cont + 1; } } System.out.println("F("+n+")="+b); }//fim do main }// fim da classe import java.util.*; public class cuboXsoma { public static void main (String[] args) { Scanner s = new Scanner(System.in); int n, soma, k, i; boolean achou=false; // achou o valor de k? System.out.print("Entre n: "); n = s.nextInt(); int cubo = n*n*n; //soma == cubo economiza operações comparado com //soma == n*n*n no condicional abaixo k=1; //primero ímpar while ( !achou ) {// enquanto não achou i=0; soma = 0; while ( i < 2*n ) { // avalia k + (k+2) + ...+(k + 2(n-1)) soma = soma + ( k + i ); i = i+2; } if (soma == cubo) { achou = true;} else {k = k+2;} // tome o próximo ímpar } System.out.println("k = " + k); }//fim do main }fim da classe Implemente um jogo de dados que: • O jogador inicie o jogo com R$ 100,00 • A cada jogada, o jogador jogue dois dados • Se a soma dos números dos dados for 7 ou 11, o jogador recebe o dobro do que tenha apostado no momento • Se a soma dos números não for 7 ou 11, o jogador perde R$ 20,00 • O jogo acaba quando o saldo do jogador for menor ou igual a zero. Ou então quando o jogador decidir parar • Ao final, escreva o total de dinheiro que o jogador tem, e quantas vezes ele ganhou e quantas vezes perdeu no jogo Algoritmo JogoDeDados início real: dinheiro, aposta; inteiro: dado1, dado2, soma, numVitoria, numDerrota; string: continua; dinheiro 100,00; numVitoria = 0; numDerrota = 0; escreva( “Deseja jogar?” ); leia ( continua ); enquanto ( (continua = “S”) (dinheiro > 0) ) faça leia ( aposta ); dado1 randomico(1..6); dado2 randomico(1..6); soma dado1 + dado2; se ( (soma = 7) (soma = 11) ) então numVitoria numVitoria + 1; dinheiro dinheiro + 2*aposta; senão numDerrota numDerrota + 1; dinheiro dinheiro - 20; escreva( “Deseja jogar?” ); leia ( continua ); fimenquanto escreva( numVitoria ); escreva( numDerrota ); escreva( dinheiro ); fimalgoritmo import java.util.*; public class JogoDados { public static void main(String[] args) { double dinheiro, aposta; int dado1, dado2, soma, numVitoria, numDerrota; String continua = null; dinheiro = 100.00; numVitoria = 0; numDerrota = 0; Scanner s = new Scanner(System.in); Scanner n = new Scanner(System.in); System.out.print("Deseja jogar? (s/n)"); continua = s.nextLine(); while ( continua.equals("s") && dinheiro > 0 ) { System.out.print("Digite sua aposta: "); aposta = n.nextDouble(); Random num = new Random(); dado1 = num.nextInt( 5 ) + 1; dado2 = num.nextInt( 5 ) + 1; soma = dado1 + dado2; System.out.print(" Dado 1 = " + dado1); System.out.println(" Dado 2 = " + dado2); if ( soma == 7 || soma == 11 ){ numVitoria = numVitoria + 1; dinheiro = dinheiro + 2*aposta; System.out.println("Vitorias = " + numVitoria); System.out.println(" Dinheiro = " + dinheiro); }// fim if else{ numDerrota = numDerrota + 1; dinheiro = dinheiro - 20; System.out.println("Derrotas = " + numDerrota); System.out.println("Dinheiro="+dinheiro); }//fim else System.out.print("Deseja jogar? (s/n)"); continua = s.nextLine(); } //fim while } // fim método } // fim da classe Estruturas de repetição: – Estrutura enquanto (while) –Estrutura repita (do while) – Estrutura para (for) • Para realizar a repetição com teste no final deve ser utilizado a estrutura repita, que permite uma ação (ou bloco) ser executada enquanto uma determina condição seja verdadeira. • Exemplo: soma nota, enquanto número de notas for menor que 10. • O corpo da estrutura repita pode ser uma instrução única, ou um bloco de comandos Repita bloco V F Pseudocódigo repita <bloco> enquanto <condição>; repita Bloco de Execução enquanto condição ? F V Reescrevendo a solução para números de Fibonacci 1. Dado n; 2. se n=1 ou n=2, então responda “F(n)=1”; 3. senão, tome i igual a 2 e faça 3.2. i ← i+1; 3.3. F(i) ← F(i-1) + F(i-2); 3.4. se i<n então volte para 3.2; 4. responda “F(n)=” F(i). Obs: Se n>2 então as linhas 3.2, 3.3 e 3.4 serão executadas pelo menos uma vez. Algoritmo Fibonacci_v2 inicio inteiro n, a, b, prox, cont; leia (n); a ← b ← 1; se ( n=1 n=2 ) entao inicio escreva (b); fimentao senao inicio cont ← 2; repita inicio prox ← a + b; a ← b; b ← prox; cont ← cont + 1; fim enquanto (i<>n); fimsenao escreva(b); fimalgoritmo. Java // Não é padrão Pseudocódigo repita <bloco> enquanto<condição>; do comando; while ( condição ) ; Java // Padrão: com { } do { comandos; } while ( condição ) ; • Tem a mesma função que o laço while, só que o teste só é feito no final • Pelo menos uma vez os comandos serão executados • Note que, no do...while, o uso do “;” após a condição é obrigatório A mesma observação vale no exemplo 3. Queremos avaliar k + (k+2) + ... + (k + 2(n -1)). A solução foi: 1. dados k e n; 2. i ← 0; 3. soma ← 0; 4. enquanto i <= 2(n-1) 4.1 soma ← soma + (k + i); 4.2 i← i+2; Como n >= 1 o primeiro teste de “i<=2(n-1)” sempre valerá. Exercício: Reescreva o pseudocódigo do exemplo 3 usando repita-enquanto no laço mais interno. Algoritmo Cubo como soma de ímpares consecutivos início inteiro: n, soma, k, i; lógico: achou; leia ( n ); // n>=1 achou ← falso; k ← 1; enquanto ( ~achou ) faça inicio i ← soma ← 0; repita inicio soma ← soma + (k + i); i ← i + 2; fim enquanto (i < 2*n); se ( soma = n^3 ) entao inicio achou ← verdadeiro; fimentao senao inicio k ← k + 2; fimsenao fimenquanto escreva(k); fimalgoritmo Estruturas de repetição: – Estrutura enquanto (while) – Estrutura repita (do while) –Estrutura para (for) • Executa o bloco de predeterminado de vezes; instruções um Pseudocódigo para V de vi até vf passo p faça <bloco_de_execução> • • • • V é a variável de controle vi é o valor inicial de V vf é o valor final de V (até onde ela vai chegar) p é o valor de incremento número limite ? não sim No exemplo 3, queremos avaliar k + (k+2) + ... + (k + 2(n -1)). Usando a instrução para, podemos reescrever o pseudo código como soma ← 0; para i de 0 até 2*(n-1) passo 2 faça inicio soma ← soma + (k+i); fimpara Exercício: Escreva um algoritmo em pseudocódigo que recebe dois inteiros positivos, digamos k e n, e devole a soma dos n primeiros múltiplos de 5 maiores ou iguais a k. Java // Não é padrão Pseudocódigo para V de vi até vf passo p faça for (V = vi; V <= vf; V = V + passo) comando; Java <bloco_de_execução> // Padrão: com { } for (V = vi; V <= vf; V = V + passo) comando; 1. Usando as três opções de estruturas de repetição, resolva os exercícios a seguir sem alterar o código entre { } abaixo: { System.out.print (“i=” + i + “\t”); } Imprimir os números: Entre 1 e 10, inclusive (vale para todos os itens a seguir), em ordem crescente Entre 0 e 10, em ordem crescente Entre 0 e 20, em ordem crescente Pares entre 0 e 20, em ordem crescente Ímpares entre 0 e 20, em ordem crescente Entre 0 e 20, em ordem crescente e variando de 3 em 3 números Entre 0 e 20, em ordem crescente e variando de 5 em 5 números Entre 10 e 1, em ordem decrescente Entre 20 e 0, em ordem decrescente Pares entre 20 e 0, em ordem decrescente Entre 20 e 0, em ordem decrescente e variando de 4 em 4 números •FORBELLONE, A. L. V.; EBERSPACHER, H. F., Lógica de Programação – A Construção de Algoritmos e Estruturas de Dados, Prentice Hall, 2005 •Deitel, H. M. e Deitel, P. J.; JAVA – Como Programar; 6ª edição, Editora Pearson Prentice-Hall, 2005