* De acordo com [1], iterar significa "tornar a fazer (...) repetir (...)" enquanto recorrer significa "tornar a correr (...)". São, portanto, conceitos semelhantes. Em termos de linguagens de programação, no entanto, envolvem mecanismos diferentes, como se verá. No entanto há relações fortes entre os dois conceitos (ver discussão acerca de como transformar soluções recursivas em soluções iterativas em [2, secção 3.4]).
A execução da instrução while consiste na execução repetida de instrução enquanto espressão_booleana tiver o valor verdadeiro (true). A expressão_booleana é sempre calculada antes da instrução, que, se a expressão for falsa (false), não chega a ser executada, passando o fluxo de execução para a instrução subsequente ao while. Note-se que instrução pode consistir em qualquer instrução do C++, nomeadamente um bloco de instruções.while(expressão_booleana) instrução
À expressão booleana de controlo do while chama-se a guarda do ciclo, enquanto à instrução controlada se chama passo. Assim, o passo é repetido enquanto a guarda for verdadeira.
Por exemplo, se se pretender escrever um procedimento que, dado como parâmetro um inteiro n, escreva no ecrã uma linha com todos os números inteiros de zero a n (exclusivé):
void escreveInteiros(int n) // 1
{ // 2
int i = 0; // 3
while(i < n) { // 4
cout << i << ' '; // 5
i++; // 6
} // 7
cout << endl; // 8
} // 9
Neste procedimento começa por se inicializar a variável i
com 0 (linha 3) e em seguida executa-se o ciclo while que:
Programar deve ser uma actividade orientada pelos objectivos: pretende-se resolver um problema, i.e., dadas determinadas condições iniciais, atingir determinados objectivos. A construção de ciclos é feita da mesma forma. Sejam:
inicconduz (se terminar) a CO verdadeira se PC também o for. Estas demonstrações levem à conclusão de que o ciclo está parcialmente correcto, i.e., verificadas as pré-condições, conduz a CO, mas apenas se terminar, o que não se demonstrou. Para assegurar a correcção do ciclo pode-se usar o conceito de funções de limitação (bound functions) [4]. Aqui, far-se-á apenas uso de conceitos informais.
while(G) {
passo
}
// PC: n > 0 e x = X e n = NNote-se que se impôs que o resultado corresponde à potência N de X, sendo N e X constantes correspondentes aos valores iniciais de n e x. Isto serve para evitar soluções ingénuas como *:
// CO: resultado = XN
double potência(double x, int n)
{
// PC
double resultado;
....
// CO
return resultado;
}
// PC: n > 0 e x = X e n = NComo desenvolver o interior da função? Uma potência é a multiplicação de um valor por si próprio várias vezes, pelo que a utilização dum ciclo parece apropriada:
// CO: resultado = xn
double potência(double x, int n)
{
// PC
double resultado;
resultado = 0;
x = 0;
n = 1;
// CO
return resultado;
}
// PC: n > 0 e x = X e n = NA metodologia típica de desenvolvimento de um ciclo corresponde a:
// CO: resultado = XN
double potência(double x, int n)
{
// PC
double resultado;
inic
// CI: ??
while(G) {
// CI e G
passo
// CI
}
// CI e ~ G => CO
// CO
return resultado;
}
// PC: n > 0 e x = X e n = Nque, sem as asserções, fica (mas note-se que se mantiveram os comentários com PC, CO e CI, pois documentam perfeitamente a função):
// CO: resultado = XN
double potência(double x, int n)
{
// PC: n > 0 e x = X e n = N
double resultado = x;
int i = 1;
// CI: resultado = xi e 0 <= i <= n e x = X e n = N
while(i != n) { // G: i <> n
// CI e G, ou seja, resultado = xi e 0 <= i <= n e x = X e n = N e i <> n
// ou seja, resultado = xi e 0 <= i < n e x = X e n = N
// ou seja, resultado x = xi x = xi+1 e 1 <= i + 1 < n + 1 e x = X e n = N
// ou seja, resultado x = xi x = xi+1 e 1 <= i + 1 <= n e x = X e n = N
// que implica resultado x = xi x = xi+1 e 0 <= i + 1 <= n e x = X e n = N
// o pelo que se porna evidente que a acção a usar é
resultado *= x; // resultado = resultado * x
i++; // i = i + 1
// pois conduz a resultado = xi e 0 <= i <= n e x = X e n = N
// ou seja, conduz a CI
}
// CI e ~ G => CO, ou seja
// resultado = xi e 0 <= i <= n e x = X e n = N e i = n => resultado = XN
return resultado;
}
// PC: n > 0 e x = X e n = NEste foi um exemplo simples, no qual a utilização da metologia apresentada pode parecer excessiva. Mas a verdade é que a disciplina no desenvolvimento de programas trará vantagens muito evidentes quando a complexidade dos problemas aumentar.
// CO: resultado = XN
double potência(double x, int n)
{
double resultado = x;
int i = 1;
// CI: resultado = xi e 0 <= i <= n e x = X e n = N
while(i != n) {
resultado *= x;
i++;
}
return resultado;
}
Finalmente, note-se que a metologia apresentada não é de todo exaustiva: a escolha do invariante pode ser feita de outras formas. Na realidade, por vezes tem de ser feita de outra forma. Mas essa é matéria para Computação e Algoritmia.
* Note-se que, nas asserções, tenta-se usar a simbologia habitual da matemática, onde = significa "igual a", e não a atribuição. Só mesmo no código C++ se usa o formato ==. No caso da desigualdade, à falta, em HTML, do símbolo habitual, usa-se <> para o as asserções, e != apenas no código C++.
inico C++ disponibiliza um forma abreviada para os escrever: através da instrução for:
while(G) {
acção
prog
}
for(inic; G; prog)em que inic e prog têm de ser expressões em C++ (mas inic pode definir variáveis locais). A função potência() desenvolvida acima pode portanto ser escrita:
acção
// PC: n > 0 e x = X e n = NUm outro tipo de ciclo em C++ é o correspondente à instrução do while. A sintaxe desta instrução é:
// CO: resultado = XN
double potência(double x, int n)
{
double resultado;
int i;
// CI: resultado = xi e 0 <= i <= n e x = X e n = Nfor(resultado = x, i = 1; i != n; i++)
resultado *= x;return resultado;
}
A execução da instrução do while consiste na execução repetida de instrução enquanto espressão_booleana tiver o valor verdadeiro (true). Mas, ao contrário do que se passa no caso da instrução while, a expressão_booleana é sempre calculada e verificada depois da instrução. Quando o resultado é falso o fluxo de execução passa para a instrução subsequente ao do while. Note-se que instrução pode consistir em qualquer instrução do C++, nomeadamente um bloco de instruções.do instrução while(expressão_booleana);
Se se pretender validar uma entrada de dados por um utilizador (se o utilizador apenas devesse escrever números entre 0 e 10, por exemplo) e se se quiser obrigar à repetição da entrada de dados até o utilizador escrever o número correcto:
cout << "Introduza valor (0 a 10): ";
cin >> n;
while(n < 0 || n > 10) {
cout << "Incorrecto, introduza de novo (0 a 10): ";
cin >> n;
}
A instrução cin >> n aparece duas vezes, o que não
parece uma solução muito elegante. Isto deve-se a que,
antes de entrar no ciclo para a primeira iteração, tem de
fazer sentido verificar se n está ou não dentro
dos limites impostos. A alternativa usando o ciclo do while
seria:
cout << "Introduza valor (0 a 10): ";
do {
cin >> n;
if(n < 0 || n > 10)
cout << "Incorrecto, introduza de novo (0 a 10): ";
} while(n < 0 || n > 10);
Este ciclo executa o corpo pelo menos uma vez dado que a guarda só
é avaliada depois da primeira execução. Assim,
só é necessária uma instrução cin
>> n. A contrapartida é a necessidade da instrução
alternativa if dentro do ciclo...
Em geral os ciclos while e for são suficientes para resolver os problemas, sendo muito raras as utilizações onde a utilização de do while resulta em código realmente mais claro.
#include <iostream> using namespace std;// Escreve um triângulo oco de asteriscos com a altura passada // como argumento: void escreveTriângulo(int altura) { for(int i = 0; i < altura ; i++) { for(int j = 0; j < altura ; j++) if (j == 0 || j == i || i == altura - 1) cout << '*'; else cout << ' '; cout << endl; } } int main() { cout << "Introduza a altura do triângulo: "; int a; cin >> a; escreveTriângulo(a); }
1.a) Desenvolva uma função que calcule, duma forma iterativa, o factorial de um inteiro passado como argumento. Compare com a versão recursiva desenvolvida em aulas anteriores.
1.b) Desenvolva um procedimento que, dados dois inteiros como argumento, um o dividendo e outro o divisor, sendo o dividendo não negativo e o divisor positivo, calcule o quociente e o resto da divisão do dividendo pelo divisor e os guarde em variáveis externas à função (use passagem de argumentos por referência). Nota: não pode usar os operadores *, / e %. Qual será o invariante?
2.a) Escreva uma função devolva true se o valor do argumento inteiro for primo e false no caso contrário. Recorda-se que um número primo é todo aquele que apenas é divisível por 1 e por si mesmo.
2.b) Desenvolva um programa que escreva no ecrã todos os números primos entre 2 e n (inclusivé), sendo n dado pelo utilizador.
2.c) Sabendo que todos os números primos maiores que 3 se podem escrever na forma 6m-1 ou 6m+1 (mas nem todos os números desta forma são primos!), torne o programa da alínea anterior mais eficiente.
3.a) Faça um procedimento que imprima no ecrã um quadrado com a altura indicada como argumento e com o interior vazio. Crie um pequeno programa para testar o procedimento. Exemplo:
3.b) Faça um procedimento que imprima no ecrã um quadrado com a altura indicada como argumento e com as diagonais assinaladas. Crie um pequeno programa para testar o procedimento. Exemplo:Introduza a altura do quadrado: 4 **** * * * * ****
4. Faça uma função que permita ao utilizador inserir 20 caracteres e devolva quantos dos caracteres introduzidos pelo utilizador são asteriscos. Crie um pequeno programa para testar esta função. Exemplo:Introduza a altura do quadrado: 8 ******** ** ** * * * * * ** * * ** * * * * * ** ** ********
Introduza um conjunto de caracteres: qwe*98*8wer*we112rwq Contei 3 asteriscos.
1.b) Escreva uma função que calcule a multiplicação inteira de dois números recorrendo apenas aos operadores aritméticos + e -.
2. Suponha que as letras A, B, C e D foram codificadas em zeros e uns da seguinte forma: A = 0, B = 11, C = 100 e D = 101. Crie um programa que, quando é introduzida uma sequência de zeros e uns apartir do teclado, descodifique as várias letras. Atenção: pode haver sequências que não terminam com a codificação total de um caracter (por exemplo 01 = A?). O programa deve estar preparado para lidar com esse tipo de erros do utilizador. Por exemplo:
Introduza um conjunto de zeros e uns: 10010011001101 CCBAABA?Utilize uma função para descodificar cada caractere. A leitura deve terminar quando for introduzido um caractere que não seja '0' nem '1'.
3. Crie uma função que leia uma sequência de números inteiros e devolva um valor booleano que indica se este conjunto de números está por ordem crescente (no sentido lato). A sequência termina quando o utilizador insere o número 0 (zero). Como é evidente este número serve apenas como marcador do fim da sequência e não é tido em conta para o resultado da função. Pode assumir que a sequência tem sempre dois ou mais números. Crie um pequeno programa para testar esta função.
4. Crie uma função que leia uma sequência de números inteiros e devolva um valor inteiro que será 2 caso a sequência esteja ordenada por ordem crescente (em sentido lato), 1 caso esteja por ordem decrescente (em sentido lato), 0 (zero) caso seja constante e -1 caso não seja monótona. A sequência termina quando o utilizador insere o número 0 (zero). Como é evidente este número serve apenas como marcador do fim da sequência e não é tido em conta para o resultado da função. Crie um pequeno programa para testar esta função.
[2] Yedidyah Langsam, Moshe J. Augenstein e Aaron M. Tenenbaum, "Data Structures Using C and C++", segunda edição, Prentice Hall, Upper Saddle River, New Jersey, 1996.
[3] Donald E. Knuth, "Fundamental algorithms", volume 1 de "The Art of Computer Programming", segunda edição, segunda edição, Addison-Wesley Publishing Company, Reading, Massachusetts, 1973.
[4] David Gries, "The Science of Programming", volume da série "Texts and Monographs in Computer Science", editada por David Gries, Springer-Verlag, Nova Iorque, 1981 [1989]. *