(Parte 1 de 3)

Capítulo 4 Comandos de Repetição

No mundo real, é comum a repetição de procedimentos para se realizar tarefas. Esses procedimentos não são repetidos eternamente, mas se encerram quando o objetivo é atingido. Por exemplo, quando uma pessoa aperta um parafuso, ela gira a chave de fenda uma vez, duas vezes etc. até que o parafuso esteja apertado o suficiente. Durante esse processo, é verificado, a cada volta, se o parafuso já está bem firme.

Da mesma forma, podemos estruturar várias atividades diárias como repetitivas. Durante a chamada feita por um professor, por exemplo, ele chama os nomes enquanto não terminar a lista. Outras repetições podem ser quantificadas com antecedência. O aluno de castigo que precisa escrever 100 vezes no quadro negro: “Não vou fazer bagunça nunca mais”, executa a mesma instrução 100 vezes.

Todas as repetições têm uma característica comum: o fato de haver uma verificação de condição que pode ser representada por um valor lógico, para determinar se a repetição prossegue ou não. Essa é a base para a implementação dos comandos de repetição em algoritmos. Em vez de fazermos um trabalho braçal, escrevendo a mesma instrução várias vezes, poderemos utilizar uma estrutura que indique que tal instrução será executada quantas vezes for necessária.

4.1 Comando enquanto

Antes de vermos a sintaxe em nosso pseudocódigo, vejamos um exemplo do mundo real: o problema do elevador.

Um elevador residencial tem um comportamento que pode ser descrito de forma algorítmica. Vejamos o seu funcionamento:

• Na subida: sobe cada andar, verificando se está em um andar selecionado dentro do elevador. Isso é feito até chegar ao andar mais alto selecionado dentro ou fora do elevador.

61Capítulo 4 • Comandos de Repetição enquanto não chegar ao andar mais alto selecionado interna/externamente faça início suba um andar, se o andar foi selecionado internamente então início pare, abra as portas, feche as portas, fim fim

• Na descida: desce cada andar, verificando se está em um andar selecionado dentro ou fora do elevador. Isso é feito até chegar ao andar mais baixo selecionado dentro ou fora do elevador enquanto não chegar ao andar mais baixo selecionado interna/externamente faça início desça um andar, se o andar foi selecionado interna/externamente então início pare, abra as portas, feche as portas, fim fim

O comando enquanto caracteriza-se por uma verificação de encerramento de atividades antes de se iniciar (ou reiniciar) a execução de seu bloco de instruções. Dessa forma, no algoritmo do elevador, antes de subir/descer um andar é verificado se o andar atual é o mais alto/baixo selecionado. Caso não seja, um conjunto de atividades é executado (sobe/desce um andar, verifica se é um andar selecionado e abre (ou não) as portas).

Vejamos sua sintaxe:

enquanto <valor booleano> faça <bloco de instruções>

<continuação do algoritmo>

Voltemos ao exemplo do aluno de castigo. Fazer um algoritmo que escrevesse para ele, cem vezes, “Não vou fazer mais bagunça”, antes deste capítulo, seria uma tarefa inglória. O algoritmo seria semelhante ao descrito a seguir.

Algoritmo Lição_Aluno_Versão1 início escreva(“Não vou fazer mais bagunça!”); escreva(“Não vou fazer mais bagunça!”); escreva(“Não vou fazer mais bagunça!”); escreva(“Não vou fazer mais bagunça!”); ...

{ O comando precisa ser escrito 100 vezes}

fim

62Algoritmos e Programação

Para que possamos utilizar o comando de repetição, precisaremos verificar, de alguma forma, se o comando já foi executado 100 vezes.

enquanto <não foi executado 100 vezes o próximo bloco > faça escreva(“Não vou fazer mais bagunça!”);

Bem, o problema reside em implementar essa verificação. Uma estratégia muito comum para esse tipo de situação é acompanhar a execução das repetições contando cada vez que o bloco é executado. Cada execução do bloco de instruções é chamada iteração. O próprio comando de repetição em conjunto com seu bloco de instruções é conhecido como loop ou laço.

Para que tenhamos a informação de quantas iterações já foram realizadas no laço, necessitaremos de uma variável que fará o papel de contador. Essa variável conterá o número de iterações já realizadas, sendo atualizada a cada nova iteração.

4.1.1 Problema 1 – Escrever 100 vezes "Não vou fazer mais bagunça"

Faça um algoritmo que escreva 100 vezes o texto: “Não vou fazer mais bagunça”, utilizando um comando de repetição.

Algoritmo Lição_Aluno_Versão2

contador  0;{ Nenhuma iteração foi feita até aqui }

var contador: inteiro; início enquanto (contador < 100) faça { O bloco será repetido 100 vezes } início escreva(“Não vou fazer mais bagunça!”); contador contador + 1; { A cada iteração, conta-se mais 1 } fim fim

Vejamos a seguir outros exemplos.

4.1.2 Problema 12 – Ler 100 números e calcular a soma e a média Faça um algoritmo que leia 100 números e retorne a soma e a média desses valores.

Algoritmo Soma_Média100 var contador: inteiro; valor, soma, média: real; início

1 contador  0;{ Nenhuma iteração foi feita até aqui }
2 soma  0;{ Ainda não foi somado nenhum valor }

3 enquanto (contador < 100) faça { O bloco será repetido 100 vezes }

63Capítulo 4 • Comandos de Repetição início 4 escreva(“Entre com um valor: ”); 5 leia(valor); 6 soma soma + valor;

7 contador contador + 1; { A cada iteração, conta-se mais 1 } fim

10 escreva(“Média: ”, média); fim

É interessante verificar o processo de acumulação de valores feito na variável soma (linha 6). Seu valor é atualizado a cada iteração, somando-se seu valor atual com o novo valor lido. Para que isso funcione, é importante que o valor inicial da variável seja definido antes da entrada do laço, para que um valor desconhecido não seja atribuído na primeira iteração do laço.

Vejamos o teste de mesa para a melhor compreensão do processo. Para viabilizar a realização do teste de mesa, consideremos o laço até 3 e não até 100, como está no algoritmo (Tabela 4.1).

Entrada: 5, 4, 9 (ou seja, os valores que serão entrados pelo usuário serão 5, 4 e 9, nesta seqüência).

Tabela 4.1 – Teste de mesa para Soma_Média100

64Algoritmos e Programação

Note que a condição de entrada/saída do laço está na linha 3. Esse teste é executado nas instruções 3, 8, 13 e 18. Perceba também que o teste é repetido sempre após o bloco de instruções (linha 7) pertencente ao laço. Quando a condição é verdadeira, a instrução a ser executada é a do início do bloco, na linha 4 (instruções 4, 9 e 14). Porém, na instrução 18, a condição é falsa (no nosso teste, estamos considerando enquanto contador < 3) e a próxima instrução a ser executada (instrução 19) está na linha 8, após o bloco de instruções pertencente ao comando enquanto.

Exercício proposto

1. Adapte o algoritmo Soma_Média100 para que o número de valores a ser computado seja determinado a partir de uma variável de entrada e não como um valor fixo no programa, como fora definido.

4.1.3 Problema 13 – Calcular a multiplicação de dois números sem o operador "*"

Faça um algoritmo que calcule a multiplicação de dois números inteiros sem utilizar o operador “*”. Em vez disso, utilize apenas o operador de adição “+”.

Para implementar esse algoritmo, devemos lembrar que qualquer multiplicação pode ser expressa por meio de somas. Por exemplo, o resultado da expressão 6 * 3 é o mesmo de 6 + 6 + 6 ou 3 + 3 + 3 + 3 + 3 + 3. Ou seja, soma-se um elemento com ele próprio o número de vezes do segundo elemento.

Algoritmo Mult_Soma var contador: inteiro; operando1, operando2, resultado, contador: inteiro; início

1 contador  0;{ Nenhuma iteração foi feita até aqui }
2 resultado  0;{ Ainda não foi somado nenhum valor }

7 enquanto (contador < operando2) faça { O bloco será repetido “operando2” vezes } início

9 contador  contador + 1;{ A cada iteração, conta-se mais 1 }

10 escreva(“O resultado da multiplicação é: “,resultado); fim

Exercícios propostos

1. Faça três testes de mesa para o algoritmo anterior com as seguintes entradas: 0, 3; 3, 6 e 6, 3.

65Capítulo 4 • Comandos de Repetição

2. Se você fez o exercício anterior, pode notar que o número de instruções a serem executadas para a segunda e a terceira entrada é diferente, apesar de o resultado ser o mesmo. Isso porque sempre o operando1 será somado e o operando2 determinará quantas vezes o laço será repetido. Melhore o algoritmo para que o valor maior seja somado e o valor menor seja o determinante para o controle do laço, garantindo assim que o menor número de instruções seja executado para qualquer entrada, independentemente de sua ordem.

4.1.4 Problema 14 – Calcular o fatorial de um número

Faça um algoritmo que leia um número inteiro e calcule o seu fatorial. Se o número for negativo, informe que o valor é inválido.

n * (n - 1) * (n - 2) ** 1, para n > 0 e n! = 1 para n = 0

Sabemos que o fatorial de um número n, representado por n!, é dado por:

Como dito anteriormente, um ponto crucial para resolver um problema que inclua a repetição é a definição do ponto de saída do laço. Além disso, é importante se definir a situação desejada para a entrada no laço e o que vai ser executado em cada iteração.

Nesse problema, o laço só pode se iniciar após a leitura do valor n e a verificação se tal valor é válido. Caso o valor seja 0, o fatorial deve ser retornado como 1 e o comando de repetição não precisa ser executado.

A cada iteração dentro do laço, é necessário acumular o resultado da multiplicação do valor pelo subseqüente (n * n - 1 *...). Também é preciso subtrair 1 do último valor que foi multiplicado, preparando-o para a próxima iteração ou para a saída do laço.

A saída do laço é feita quando o valor a ser multiplicado chegar a 1.

Algoritmo Fatorial

n  n – 1;{ A cada iteração, diminui-se 1 }

var valor, fat, n: inteiro; início escreva(“Entre com um valor: ”); leia(valor); se (valor < 0) então escreva(“Valor inválido!”); senão início fat 1; n valor; enquanto (n > 1) faça início fat fat * n; fim escreva(“O fatorial calculado é: “, fat); fim fim

66Algoritmos e Programação

Note que o valor inicial de fat é 1 e não 0, como se poderia imaginar. Isso porque o elemento neutro na multiplicação é o 1 e não o 0, como na adição, ou seja, qualquer número multiplicado por 1 é ele próprio, assim como acontece com o 0 em relação à adição.

O fatorial de 1 ou 0 é calculado implicitamente, já que nesses casos o laço não é executado, pois a condição de controle do laço (n > 1) não é satisfeita nenhuma vez e o valor do fatorial permanece em 1, como esperado. Esta situação ilustra o fato de que o bloco de instruções pertencente ao laço pode não ser executado nenhuma vez, caso a condição de controle não seja satisfeita na primeira passagem.

Exercício proposto

1. Faça dois testes de mesa referentes ao algoritmo Fatorial para o cálculo do fatorial dos números 1 e 5.

4.2 Comandos de repetição combinados com comandos de condição

A utilização de comandos de repetição combinados com comandos de condição permite resolver problemas bem mais complexos que os vistos até agora. Na realidade, o ferramental já apresentado é a base para toda a seqüência de algoritmos, e sua compreensão é absolutamente fundamental para o desenvolvimento de algoritmos mais sofisticados.

Os comandos de condição podem fazer parte de blocos pertencentes a comandos de repetição e vice-versa. Ou seja, estruturas como as descritas a seguir podem ocorrer intercaladas quantas vezes forem necessárias.

Exemplo:

fim{ Fim do bloco se }
senão

... se <valor booleano> então início ... enquanto <valor booleano> faça início ... fim ... início ... enquanto <valor booleano> faça início ... se <valor booleano> então início fim senão

67Capítulo 4 • Comandos de Repetição

fim{ Fim do bloco enquanto }
fim{ Fim do bloco senão }

início fim <continuação do algoritmo> fim

Na estrutura anterior temos comandos de decisão aninhados a comandos de repetição e vice-versa. Esse tipo de estrutura é extremamente útil para resolver problemas em diversas situações. Vejamos a seguir alguns exemplos.

4.2.1 Problema 15 – Calcular a soma dos números ímpares de um intervalo

Faça um algoritmo que calcule a soma de todos os números ímpares dentro de uma faixa de valores determinada pelo usuário.

Um número é ímpar quando sua divisão por 2 não é exata, ou seja, o resto resultante da divisão inteira do número por 2 tem valor 1. Vejamos como fica o código:

se ((número resto 2) = 1) então <código para número ímpar> [senão <código para número par> ]

Como o algoritmo solicita a soma dos valores ímpares dentro de uma faixa, teremos que fazer o acúmulo do resultado apenas quando a condição ímpar for atendida. Essa condição será testada para todos os números dentro da faixa, por meio de um laço.

Algoritmo Soma_Ímpares_Versão1 var inferior, superior, num, soma: inteiro; início soma 0; escreva(“Entre com o limite inferior: “); leia(inferior); escreva(“Entre com o limite superior: “); leia(superior); num inferior; enquanto (num <= superior) faça início se (num resto 2 = 1) então soma soma + num; num num + 1; fim escreva(“Somatório: “, soma); fim

68Algoritmos e Programação

Exercícios propostos 1. Faça o teste de mesa com intervalo definido entre 4 e 13.

2. Adapte o algoritmo Soma_Ímpares_Versão1 para obrigar o usuário a entrar com um valor para o limite inferior menor que o valor definido para o limite superior. Para isso, faça um laço que garanta a entrada de um intervalo válido (inferior < superior).

3. Adapte o algoritmo Soma_Ímpares_Versão1. Substitua o teste em que verificamos se o número é ímpar dentro do laço para, então, acumulá-lo à variável soma pela seqüência:

a. Faça um único teste antes do laço.

b. Determine se o número é ímpar e considere como limite inferior o próximo ímpar (ou o próprio número caso este seja ímpar).

c. Faça o laço aumentando 2 a 2 seu valor para que apenas os números ímpares sejam calculados, sem a necessidade de novas verificações.

4. Faça o teste de mesa dos algoritmo Soma_Ímpares_Versão1 adaptado no exercício proposto 3, considerando os limites 4 e 13. Compare o número de instruções executadas com o teste de mesa do algoritmo Soma_Ímpares_Versão1 (visto no exercício 1).

4.2.2 Problema 16 – Determinar se um número é primo

Faça um algoritmo que leia um número inteiro positivo e determine se este é primo ou não.

Por definição, um número é primo quando é divisível somente por si próprio e por 1. Portanto, para determinar se um número é primo, temos de definir por quais números é divisível. A aproximação mais simples, e que podemos dizer ser uma aproximação de “força bruta”, poderia ser testar a divisibilidade do número avaliado por todos os números menores que ele. Vejamos a implementação deste algoritmo.

Algoritmo Primo_Versão1 var número, divisor: inteiro; divisível: booleano; { Variáveis booleanas são úteis para determinar a saída ou não de laços } início escreva(“Entre com um número a ser testado: ”); leia(número); divisível F;

69Capítulo 4 • Comandos de Repetição divisor número – 1; enquanto (não(divisível) e divisor > 1) faça início se (número resto divisor = 0) então divisível V; senão divisor divisor – 1; fim se (não(divisível)) então escreva(“O número “, número, “ é primo.”); senão escreva(“O número “, número, “ não é primo.”); fim

Apesar de o algoritmo Primo_Versão1 ser eficaz, visto que resolve o problema para o qual foi projetado, não se pode dizer que seja propriamente eficiente. Basta que analisemos com um pouco mais de profundidade que perceberemos que várias otimizações podem ser aplicadas ao raciocínio utilizado nesse algoritmo. Vejamos:

1. Números pares (com exceção do 2) não podem ser primos, visto que são divisíveis por 2. Se um número não for divisível por 2, não será divisível por nenhum outro número par. Portanto, com exceção do número 2, só precisaremos testar números ímpares.

(Parte 1 de 3)

Comentários