4  Controlo do fluxo dos programas

Todos os algoritmos minimamente interessantes envolvem tomadas de decisões e repetições.  Dificilmente se consegue escrever um algoritmo insteressante que não envolva, quando lido em português, as palavras 'se' e 'enquanto'.  Afinal, quantas iguarias conhece cuja receita possa ser escrita sem essas palavras?  Neste capítulo estudar-se-ão os mecanismos que a linguagem C++ fornece para exprimir esse conceitos.

4.1  Instruções de selecção em C++

Nesta secção apresentam-se os mecanismos do C++ que permitem tomar decisões, i.e., optar por alterativas.  Estes mecanismos correspondem às chamadas instruções de selecção ou alternativa.

4.1.1  As instruções if e if else

As instruções if e if else são das mais importantes instruções de controlo do fluxo* de um programa.  Estas instrução permitem-nos executar um conjunto de instruções caso uma condição seja verdadeira e, no caso da instrução if else, um outro conjunto caso a condição seja falsa.  Por exemplo *: 
if(x < 0)  // 1
    x = 0; // 2
else       // 3
    x = 1; // 4
....       // 5
As quatro linhas, 1 a 4, correspondem a uma única instrução, dita de selecção, que é composta de uma condição (na linha 1) e duas instruções alternativas (linhas 2 e 4).  Se x for menor do que zero quando este troço de código é executado, então é executada a instrução 2, passando o valor de x a ser zero.  No caso contrário, se x for maior ou igual a zero, é executada a instrução 4, passando a variável x a ter o valor 1.  Em qualquer dos casos, a execução continua na linha 5 (excepto em alguns casos *).

Em certos casos pretende-se apenas executar instruções se determinada condição se verificar, não se desejando fazer nada caso a condição seja falsa.  Nestes casos pode-se omitir o else.  Por exemplo: 

if(x < 0)  // 1
    x = 0; // 2
....       // 3
A este tipo restrito de instrução de selecção também se chama instrução condicional.

Se x fôr menor do que zero, então é executada a instrução 2, passando o valor de x a ser zero, sendo em seguida executada a instrução na linha 5 (excepto em alguns casos *).   No caso contrário a execução passa directamente para a linha 5.

Em muitos casos é necessário que o computador execute condicionalmente, não uma instrução simples, mas um conjunto de instruções.  Para o conseguir, agrupam-se essas instruções num bloco de instruções ou instrução composta, colocando-as entre chavetas {}.  Por exemplo: 

int m, n;
....
if(m < n) {
    int auxiliar = m;
    m = n;
    n = auxiliar;
}
Caso seja necessário podem-se encadear instruções de selecção umas dentro das outras.  Por exemplo, para verificar qual a posição de a relativamente a um intervalo [minimo, maximo] : 
int a, minimo, maximo;
cin >> minimo >> maximo >> a;

if(a < minimo)
    cout << a << " menor que mínimo." << endl;
else {
    if(a < maximo)
        cout << a << " entre mínimo e máximo." << endl;
    else
        cout << a << " maior que máximo." << endl;
}
Note-se que, sendo as instruções de selecção instruções por si só, o teste acima se pode escrever simplesmente: 
if(a < minimo)
    cout << a << " menor que mínimo." << endl;
else
    if(a < maximo)
        cout << a << " entre mínimo e máximo." << endl;
    else
        cout << a << " maior que máximo." << endl;
No entanto, a sintaxe das instruções if e if else do C++ presta-se a ambiguidades.  No código: 
if(m == 0)
    if(n == 0)
        cout << "m e n são zero." << endl;
else
    cout << "m não é zero." << endl;
O else não pertence ao primeiro if, ao contrário do que a indentação do código sugere: pertence ao segundo if.  Em caso de dúvida, um else pertence ao if mais próximo (e acima...) dentro mesmo bloco de instruções e que não tenha já o respectivo else.  Para corrigir o exemplo anterior é necessário construir uma instrução composta, muito embora consista de uma única instrução de selecção: 
if(m == 0) {
    if(n == 0)
        cout << "m e n são zero." << endl;
} else
    cout << "m não é zero." << endl;
Para evitar erros deste tipo, é conveniente usar blocos de instruções duma forma liberal, pois construções como a que se apresentou podem dar origem a erros muito difíceis de detectar e corrigir.  Os compiladores de qualidade, no entanto, avisam o programador da presença de semelhantes ambiguidades.

Um outro erro frequente é escrever: 

if(x < 0);
    x = -x;
Neste caso a intenção seria que, depois do if, x conteria o módulo do valor original.  Mas a interpretação feita pelo compilador (e a correcta dada a sintaxe da linguagem C++) é: 
if(x < 0)
    ; // instrução nula: não faz nada.
x = -x;
Ou seja, se x fosse inicialmente positivo tornar-se-ia negativo!  Estes erros, não sendo muito comuns, são ainda mais difíceis de detectar.

* Chama-se fluxo do programa à sequência pela qual as instruções são executadas.
* Podem existir instruções return, break, continue ou goto que alterem o fluxo normal de execução.

Um pouco de formalismo

Suponhase que, num dado ponto do programa, se verifica uma dada pré-condição (PC) e que se pretende atingir uma dada condição objectivo (CO).  Por exemplo, suponha-se que existe uma variável x inteira e que se pretende que x contenha, depois dum pedaço de código a construir, o valor absoluto do valor que continha originalmente.  Ou seja*:
// PC: x = x
.... // código a escrever
// CO: x = |x|
Em que condições a atribuição x = x leva a CO?  É evidente que apenas quando PC e x >= 0.  E em que condições a atribuição leva a CO?  É também evidente que apenas quando PC e x < 0.  Então, temos que:
// PC: x = x
// x >= 0
x = x;
// => CO: x = |x|
e
// PC: x = x
// x < 0
x = -x;
// => CO: x = |x|
ou seja,
// PC: x = x
if(x < 0)
    x = -x;
else // x >= 0
    x = x;
// => CO: x = |x|
que, como a atribuição x = x é, no mínimo, inútil, se pode simplificar para
// PC: x = x
if(x < 0)
    x = -x;
// => CO: x = |x|
Em geral, sempre não se consegue um único conjunto de instruções que leve sequencialmente de PC a CO, mas se conseguem encontrar instruções que o fazem em diferentes condições, torna-se necessário usar um if.  Sejam C0 a Cn-1 um conjunto de condições tal que pelo menos uma delas é sempre verdadeira se se souber que PC o é.  Sejam instrução0 a instruçãon-1 instruções tal que, dada PC, se a condição Ci for verdadeira então a instrução instruçãoi leva forçosamente a CO.  Então, as instruções seguintes resolvem o problema, i.e., levam sempre de PC a CO:
// PC
if(C0)
    instrução0
else if(C1)
    instrução1
else if(C2)
    instrução2
...
else if(Cn-1) // aqui, por construção, basta um else
    instruçãon-1
// CO
O que se passa é essencialmente que se descobriram métodos diferentes para atingir o resultado pretendido em condições diferentes.  Se ao fazê-lo se cobriram todas as possibilidades* (dadas pela PC), então resolveu-se o problema!

* As variáveis x e x são conceptualmente diferentes: x é uma variável C++, enquanto x é uma variável matemática, usada neste caso para denotar o valor inicial de x.  A notação utilizada encontra-se no Apêndice A.

* As possiblidades estão todas cobertas desde que PC => (E i : 0 <= i < n : Ci), ou, o que é o mesmo, PC => (C0 ou C1 ou ... ou Cn-1).

4.1.2  A instrução switch

Suponha-se que se pretende escrever um procedimento que, dado um inteiro entre 0 e 9, o escreve por extenso no ecrã, em português (escrevendo "erro" se o inteiro for inválido).  Como os nomes dos dígitos decimais em Português, como em qualquer outra língua, não obedecem a qualquer regra lógica, a função terá de prever cada um dos 10 casos separadamente.  Usando a instrução if else:
void escreveDígitoPorExtenso(int dígito)
{
    // PC: 0 <= dígito < 10
    if(dígito == 0)
        cout << "zero";
    if(dígito == 1)
        cout << "um";
    if(dígito == 2)
        cout << "dois";
    if(dígito == 3)
        cout << "três";
    if(dígito == 4)
        cout << "quatro";
    if(dígito == 5)
        cout << "cinco";
    if(dígito == 6)
        cout << "seis";
    if(dígito == 7)
        cout << "sete";
    if(dígito == 8)
        cout << "oito";
    if(dígito == 9)
        cout << "nove";
    if(dígito < 0 || dígito > 9)
        cout << "erro";
    // CO: surgiu no ecrã a versão por extenso de dígito.
}
Uma vez que dígito não pode tomar dois valores ao mesmo tempo, esta solução é ineficiente, pois obriga a onze testes qualquer que seja o dígito a imprimir.  Uma alternativa melhor é a sugerida no final da secção anterior:
// Repare na estrutura, em que else e if são colocados na
// mesma linha e se repete a indentação em cada linha.  Fica
// mais claro que é uma sequência de alternativas.
void escreveDígitoPorExtenso(int dígito)
{
    // PC: 0 <= dígito < 10
    if(dígito == 0)
        cout << "zero";
    else if(dígito == 1)
        cout << "um";
    else if(dígito == 2)
        cout << "dois";
    else if(dígito == 3)
        cout << "três";
    else if(dígito == 4)
        cout << "quatro";
    else if(dígito == 5)
        cout << "cinco";
    else if(dígito == 6)
        cout << "seis";
    else if(dígito == 7)
        cout << "sete";
    else if(dígito == 8)
        cout << "oito";
    else if(dígito == 9)
        cout << "nove";
    else
        cout << "erro";
    // CO: surgiu no ecrã a versão por extenso de dígito.
}
Existe uma solução mais usual para este problema: usando a instrução de selecção switch.  Quando é necessário comparar uma variável com vários valores possíveis, e executar uma acção diferente em cada um dos casos, deve-se usar esta instrução.  O procedimento anterior ficaria: 
void escreveDígitoPorExtenso(int dígito)
{
    switch(dígito) {
      case 0: cout << "zero";
          break;
      case 1: cout << "um";
          break;
      case 2: cout << "dois";
          break;
      case 3: cout << "três";
          break;
      case 4: cout << "quatro";
          break;
      case 5: cout << "cinco";
          break;
      case 6: cout << "seis";
          break;
      case 7: cout << "sete";
          break;
      case 8: cout << "oito";
          break;
      case 9: cout << "nove";
          break;
      default: cout << "erro";
        break;
    }
}
Esta instrução tem algumas particularidades.  Em primeiro lugar não permite a especificação de gamas de valores nem de desigualdades: construções como case 1..10: ou case < 10: são inválidas.  Assim, é possível usar como expressão de controlo do switch (i.e., a expressão que se coloca entre parênteses após a palavra-chave switch) apenas expressões de um dos tipos inteiros ou de um tipo enumerado, devendo os valores colocados nos case ....: respectivos ser do mesmo tipo.

É possível agrupar várias alternativas: 

switch(valor) {
  case 1:
  case 2:
  case 3: cout "1, 2, ou 3";
    break;
  ....
}
Isto acontece porque a construção case n: apenas indica qual o ponto de entrada nas instruções que compõem o switch quando a sua expressão de controlo (entre parênteses após a palavra-chave switch) tem valor n.  A execução do corpo do switch (o bloco de instruções entre {}) só termina quando for atingida chaveta final, ou quando for executada uma instrução de break (terminado o switch a execução continua sequencialmente).  A consequência deste facto é que, se no exemplo anterior se eliminarem os break:
  
void escreveDígitoPorExtenso(int dígito)
{
    switch(dígito) {
      case 0: cout << "zero";
      case 1: cout << "um";
      case 2: cout << "dois";
      case 3: cout << "três";
      case 4: cout << "quatro";
      case 5: cout << "cinco";
      case 6: cout << "seis";
      case 7: cout << "sete";
      case 8: cout << "oito";
      case 9: cout << "nove";
      default: cout << "erro";
    }
}
uma chamada escreveDígitoPorExtenso(7) resulta em: 
seteoitonoveerro
que não é o que se pretendia!

Note-se que, pelas razões que se indicaram atrás, não é possível usar a instrução switch (pelo menos duma forma imediata) como alternativa a:

void escreveGama(double x)
{
    // PC: 0 <= valor e valor < 10000.
    if(x < 10)
        cout << "unidades";
    else if(x < 100)
        cout << "dezenas";
    else if(x < 1000)
        cout << "centenas";
    else
        cout << "milhares";
    // CO: surgiu no ecrã a gama de valor.
}
Suponha-se que os valores passados como argumento a escreveGama() são equiprováveis.  Nesse caso consegue-se demostrar que, em média, são necessárias 2,989 comparações ao executar o procedimento e que invertendo para
void escreveGama(double x)
{
    // PC: 0 <= valor e valor < 10000.
    if(x >= 1000)
        cout << "milhares";
    else if(x >= 100)
        cout << "centenas";
    else if(x >= 10)
        cout << "dezenas";
    else
        cout << "unidades";
    // CO: surgiu no ecrã a gama de valor.
}
são necessárias 1,11 comparações (demonstre-o)!  A ordem pela qual se fazem as comparações pode ser muito relevante!

4.1.3  Exercícios

1.  Escreva uma função que devolva zero caso o argumento (de vírgula flutuante) seja menor do que zero, devolva o próprio argumento caso esteja entre zero e um e devolva 1 caso o argumento seja maior do que 1.  Crie um pequeno programa para testar esta função e faça o traçado desse programa.

2.  Escreva um programa que, dado um número inteiro entre 0 e 99 o escreva por extenso.  Exemplo: 

Introduza um número:
35
O número introduzido foi três dezenas e cinco unidades.
Se se desejasse que o programa escrevesse 
O número introduzido foi trinta e cinco.
o que se deveria fazer?

3.  Escreva uma função que devolva o número de dias de um mês num dado ano passado como argumento.  Lembre-se que os anos múltiplos de 4 são bissextos, com excepção dos múltiplos de 100, mas incluindo os múltiplos de 400 (esta fórmula só é válida para datas ocidentais em geral depois de 1752).

4.a)  Faça um programa que, dado um número inteiro que representa a idade de uma pessoa, escreva qual a sua faixa etária.  As faixas etárias são definidas do seguinte modo: entre 0 e 12 anos - criança, de 12 a 20 - adolescente, de 20 a 60 - adulto, acima de 60 - idoso.

4.b)  Modifique o programa anterior de modo a que seja inserido o sexo da pessoa (m ou f) em questão e as respostas sejam adequadas a esta informação.  Por exemplo, se a pessoa em questão for do sexo feminino em vez de escrever "adulto" deve escrever "adulta".

5.  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 é introduzido um conjunto de zeros e uns apartir do teclado descodifique a primeira letra que aparece.  Por exemplo: 

Introduza um conjunto de zeros e uns:
1001001100110
C
6.  Caso já se sinta apto a usar a noção de ciclo, tente fazer um programa que descodifique toda a cadeia de zeros e uns.  Atenção: pode haver sequências que não terminam com a codificação total de um caracter (por exemplo 01 = A?).  O seu programa deve estar preparado para lidar com esse tipo de erros do utilizador.  Exemplo: 
Introduza um conjunto de zeros e uns:
10010011001101
CCBAABA?

4.2  Instruções de iteração em C++

Na maioria dos programas há conjuntos de operações que é necessário repetir várias vezes: afinal, conhece alguma receita de cozinha que não implique alguma forma de repetição ou pelo menos de espera por uma condição?  Para controlar o fluxo do programa de modo a que um conjunto de instruções sejam repetidos condicionalmente usam-se as instruções iterativas * ou cíclicas.

* 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]).

4.2.1  A instrução de iteração while

A mais importante das instruções iterativas no C++ (como noutras linguagens) é a instrução while.  A instrução while tem uma sintaxe bastante simples: 
while(expressão_booleana)
    instrução
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.

À expressão booleana de controlo do while chama-se a guarda do ciclo (representada por G), enquanto à instrução controlada se chama passo.  Assim, o passo é repetido enquanto a G for verdadeira.  Ou seja

while(G)
    passo
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:
  1. Verifica se a condição i < n é verdadeira (linha 4).
  2. Se a condição for verdadeira, executa as instruções nas linhas 5 e 6, voltando-se depois a verificar a condição (volta-se a A.).
  3. Se a condição for falsa, o ciclo termina.
Finalmente, depois de terminado o ciclo, escreve-se um fim-de-linha.  É de notar que, depois da inicialização e até ao final do ciclo (salvo após a execução da linha 5), se pode afirmar que se escreveram já no ecrã todos os inteiros entre 0 e i - 1 com 0 <= i <= n.  Como esta afirmação é verdadeira sempre (com a excepção indicada), chama-se-lhe a condição invariante do ciclo (representada por CI).  Note-se ainda que quando o ciclo termina a G é forçosamente falsa, ou seja a condição i >= n é verdadeira.   A conjunção desta condição com a condição invariante leva-nos a concluir que, no final do ciclo, estão de facto escritos no ecrã todos os inteiros entre 0 e n - 1, pois i >= n (falsidade da guarda) e 0 <= i <= n só podem ser simultaneamente verdadeiras se i = n!  Ou seja, demonstrou-se que CI e ~ G => CO.  O desenvolvimento de ciclos é uma tarefa muitas vezes difícil.  Mas abaixo se falará de uma metodologia de desenvolvimento de ciclos que, não substituindo a intuição, proporciona ao programador uma base sólida na qual assentar a sua intuição e a sua arte.

4.2.2  Variantes do ciclo while: for e do while

Uma vez que a maior parte dos ciclos usando a instrução while têm a forma
inic
while(G) {
    acção
    prog
}
sendo inic as instruções de inicialização, prog o chamado progresso do ciclo, e acção a sua acção (ver Secção 4.3.2), o C++ disponibiliza um forma abreviada de os escrever: através da instrução for:
for(inic; G; prog)
    acção
em que inic e prog têm de ser expressões em C++ (embora inic possa definir variáveis locais).  A função escreveInteiros() desenvolvida acima pode portanto ser escrita: 
void escreveInteiros(int n)     // 1
{                               // 2
    for(int i = 0; i < n; i++)  // 3
        cout << i << ' ';       // 4
    cout << endl;               // 5
}
Note-se que, ao converter o while num for, aproveitou-se para restringir ainda mais a visibilidade da variável i que, estando definida no cabeçalho do for, só é visível nessa instrução (linhas 3 e 4).  Lembre-se que é de toda a conveniência que a visibilidade das variáveis seja sempre o mais restrita possível à zona onde de facto são necessárias.

Um outro tipo de ciclo em C++ é o correspondente à instrução do while.  A sintaxe desta instrução é: 

do
    instrução
while(expressão_booleana);
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.

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.

4.2.4  Exemplo simples

A título de exemplo de utilização simultânea de instruções de iteração e de selecção, segue-se um programa que escreve um triângulo rectângulo de asteriscos com o interior vazio: 
#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 <= i; 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);
}
Faça o traçado deste programa.

4.2.5  return, break, continue, e goto em ciclos

Se um ciclo estiver dentro duma função e se pretender terminar a função a meio do ciclo, então pode-se usar a instrução de return.  Por exemplo, se se pretender escrever uma função que devolva V caso o seu parâmetro (inteiro) seja primo e F no caso contrário, ver-se-á mais tarde que uma possibilidade é (Secção 4.3.2, Outro exemplo):
// PC: n >= 0
// CO: devolve valor lógico de ((Q i : 2 <= i < n : n % i <> 0) e n > 1)
bool éPrimo(int n)
{
    if(n <= 1)
        return false;

    // PC': n > 1
    // CO': devolve o valor lógico de (Q i : 1 < i < n : n % i <> 0)

    for(k = 2; k != n; k++)
        if(n % k == 0)
            return false;
    return true;
}

Este tipo de terminação abrupta de ciclos pode ser muito útil, mas também pode contribuir para tornar os programas incompreensíveis.  Deve ser usado com precaução e apenas em funções muito curtas.  Noutros casos torna-se preferível usar técnicas de reforço das guardas do ciclo (ver também Secção 4.3.2, Outro exemplo).

Outras possibilidades de alterar o funcionamento normal dos ciclos são através das instruções de break, continue, e goto.  A sintaxe da última encontra-se em qualquer livro sobre o C++ (e.g., [6]), e não será explicada aqui.  A instrução break serve para terminar abruptamente as instruções while, for, do while, ou switch mais interior dentro do qual se encontre (ou seja, se existirem duas dessas instruções encadeadas, uma instrução de break termina apenas a instrução interior).  A instrução continue serve para começar antecipadamente a próxima iteração do ciclo (apenas no caso das instruções while, for e do while).  A ambas as instruções se aplicam as recomendações feitas quanto à utilização da instrução return em ciclos.

4.3  Desenvolvimentos de ciclos

O desenvolvimento de programas usando ciclos é simultanemente uma arte [3] e uma ciência [4].  Embora a intuição seja muito importante, é fundamental usar metologias de desenvolvimento de ciclos que permitam provar simultaneamente a sua correcção.  Embora esta seja matéria seja formalizada na cadeira de Computação e Algoritmia, apresentar-se-ão aqui algumas ideias sobre o assunto.  Começar-se-á por uma introdução (ou melhor revisão) sobre quantificadores.

4.3.1  Algumas notas sobre quantificadores

Apresentam-se aqui algumas notas sobre quantificadores que são úteis para a construção de condições representativas de estados dos programas, por exemplo, para especificar uma CO (condição objectivo) ou a CI (condição invariante) de um ciclo.  A notação utilizada encontra-se no Apêndice A.

Somas

O quantificador soma corresponde ao usual somatório.  Na notação utilizada, (S i : m <= i < n : f(i)) tem exactamente o mesmo significado que o somatório (representado pela letra sigma maiúscula, impossível de escrever em HTML) de f(i) com i variando entre m e n (exclusivé).  Por exemplo, é um facto conhecido que (S i : 0 <= i < n : i ) = n (n - 1) / 2 se n >= 0 e (S i : 0 <= i < n : i ) = 0 se n < 0.

Se se pretendesse escrever a condição objectivo duma função que calcula a soma dos n primeiros números ímpares (sendo n um parâmetro da função), poder-se-ia começar por escrever o corpo (quase) vazio da função, colocando no seu início a PC (pré-condição) e no seu final, antes da devolução do resultado, a CO (condição objectivo):

int somaÍmpares(int n)
{
    // PC: n >= 0 e n = n
    int soma;

    // CO: soma = (S i : 0 <= i < n : 2 i + 1) e n = n
    return soma;
}

Note-se que a proposição n = n se encontra tanto na PC como na CO, o que significa que se deseja que n não mude de valor ao longo da função, já que é igual à variável matemática n (que o C++ não tem poderes para alterar...) no início e no fim da função.  Este tipo de restrição, por ser tão obviamente necessário, deixará de ser escrito nas condições de aqui em diante.

Produtos

O quantificador produto corresponde ao produto de termos por vezes conhecido como produtório.  Na notação utilizada, (P i : m <= i < n : f(i)) tem exactamente o mesmo significado que o usual produto (representado pela letra pi maiúscula, impossível de escrever em HTML) de f(i) com i variando entre m e n (exclusivé).  Por exemplo, a definição de factorial é n! = (P i : 1 <= i <= n : i ) se n >= 0.

Se se pretendesse escrever a condição objectivo duma função que calcula o factorial de n (sendo n um parâmetro da função), poder-se-ia escrever:

int factorial(int n)
{
    // PC: n >= 0
    int resultado;

    // CO: resultado = (P i : 1 <= i <= n : i)
    return resultado;
}

Conjunções e o quantificador universal

O quantificador universal corresponde à conjunção de vários predicados usualmente conhecida por "qualquer que seja"*.  Na notação utilizada, (Q i : m <= i < n : p(i)) tem exactamente o mesmo significado que a conjunção das proposições p(i) com i variando entre m e n (exclusivé).  Por exemplo, a definição da função (matemática!) primo(n), que tem valor V se n é primo e F no caso contrário, é: assumindo que % é a operação resto da divisão inteira (como em C++).

Se se pretendesse escrever a condição objectivo duma função (agora em C++) que devolve o valor lógico verdadeiro quando n (sendo n um parâmetro da função) é um número primo, e falso no caso contrário, poder-se-ia escrever:

bool éPrimo(int n)
{
    // PC: n >= 0
    bool é_primo;

    // CO: é_primo = ((Q i : 2 <= i < n : n % i <> 0) e n > 1)
    return é_primo;
}

* Se não é claro para si, pense no significado de escrever "todos os humanos têm cabeça".  A tradução para linguagem (quase) matemática seria "qualquer que seja h pertencente ao conjunto dos humanos, h tem cabeça".  Como o conjunto dos humanos é finito, podemos escrever por extenso, listando todos os possíveis humanos: "o Yeltsin (aparenta) ter cabeça e o Sampaio tem cabeça e ...".  Isto é, a conjunção de todas as afirmações.

Disjunções e o quantificador existencial

O quantificador existencial corresponde à disjunção de vários predicados usualmente conhecida por "existe pelo menos um".  Na notação utilizada, (E i : m <= i < n : p(i)) tem exactamente o mesmo significado que a disjunção das proposições p(i) com i variando entre m e n (exclusivé).

Este quantificador está estreitamente relacionado com o quantificador universal.  É sempre verdade que ~ (Q i : m <= i < n : p(i)) = (E i : m <= i < n : ~ p(i)), ou seja, se não é verdade que para qualquer i p(i) é verdadeira, então existe pelo menos um i para o qual p(i) é falsa.  Aplicado à definição de número primo acima, temos ~ primo(n) = ~ (Q i : 1 < i < n : n % i <> 0) = (E i : 1 < i < n : n % i = 0), para n > 1.  I.e., um número maior do que 1 não é primo se for divisível por algum inteiro maior do que 1 e menor que ele próprio.

Se se pretendesse escrever a condição objectivo duma função que devolve o valor lógico verdadeiro quando um valor k existe numa matriz m com n elementos (sendo k, m e n parâmetros da função), e falso no caso contrário, poder-se-ia escrever (as matrizes serão vistas no Capítulo 5):

bool existeNaMatrix(int k, int m[], int n)
{
    // PC: n >= 0
    bool existe;

    // CO: existe = (E i : 0 <= i < n : m[i] = k)
    return existe;
}

Contagens

O quantificador de contagem (N i : m <= i < n : p(i)) tem como valor (inteiro) o número de predicados p(i) verdadeiros para i na gama indicada.  Por exemplo, (N i : 1 <= i < 10 : primo(i)) = 4, ou seja, "existem quatro primos entre 1 e 9", é uma afirmação verdadeira.

Este quantificador é extremamente útil quando é necessário especificar condições em que o número de ordem é fundamental.  Se se pretendesse escrever a condição objectivo duma função que devolve o índice da segunda ocorrência de um dado valor k numa matriz m com n elementos (sendo k, m e n parâmetros da função), assumindo que k ocorre pelo menos duas vezes na matriz, poder-se-ia escrever:

int índiceDoSegundo(int k, int m[], int n)
{
    // PC: n >= 2 e (N i : 0 <= i < n : m[i] = k) >= 2
    int índice;

    // CO: (N i : 0 <= i < índice : m[i] = k) = 1 e m[índice] = k
    return existe;
}

O resto da divisão
Quando se apresentou o operador %, resto da definição inteira, não se fez uma definição formal dele.  Esta pode ser feita à custa de alguns dos quantificadores apresentados.  Seja m % n = resto(m, n) (com m >= 0 e n > 0).  Então, resto(m, n) é o único elemento do conjunto {r : 0 <= r < n e (E : q >= 0 : m = qn + r)}.  Claro que a definição está incompleta enquanto não se demonstrar que de facto o conjunto tem um único elemento, ou seja que, quando m >= 0 e n > 0, se tem (N r : 0 <= r < n : (E : q >= 0 : m = qn + r)) = 1.  Essa demonstração deixa-se como exercício para o leitor.

4.3.2  Desenvolvimento de ciclos e provas de correcção

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: Suponha-se uma dada CI.  Se se demonstrar que, dada a PC, as instruções em inic implicam que a CI é verdadeira, então a CI é verdadeira no início do ciclo.  Por outro lado, se se demonstrar que dadas CI e G, as instruções no passo implicam que a CI é verdadeira (isto é, a veracidade da guarda e da condição invariante garantem que, depois do passo do ciclo, a condição invariante é ainda verdadeira), então é claro que CI é verdadeira do início ao fim do ciclo (isto é, CI é de facto invariante).  Finalmente, se se demonstrar que CI e ~ G => CO, então, como a condição invariante é verdadeira no final do ciclo e a guarda é forçosamente falsa (de outro modo o ciclo não teria terminado), conclui-se forçosamente que o ciclo:
inic
while(G) {
    passo
}
conduz (se terminar) a CO verdadeira, isto se PC também o for inicialmente!  Estas demonstrações levem à conclusão de que o ciclo está parcialmente correcto, i.e., verificadas as pré-condições, o ciclo conduz das PC às 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.

Exemplo

Pretende-se desenvolver uma função que devolva a potência inteira positiva de um valor real arbitrário.  A interface natural para essa função será: double potência(double x, int n), sendo x o valor a potenciar e n a potência desejada.  Assim, a função terá a forma (em comentários colocam-se as asserções que se garante serem verdadeiras em cada linha da função):
// PC: n > 0 e x = x e n = n
// CO: resultado = xn e x = x e n = n
double potência(double x, int n)
{
    // PC
    double resultado;
    ....
    // CO
    return resultado;
}
Note-se que se impôs que o resultado corresponde à potência n de x, sendo n e x variáveis matemáticas (e portanto constantes do ponto de vista do C++) correspondentes aos valores iniciais de n e x.  Isto serve para evitar soluções engenhosas como:
// PC: n > 0 e x = x e n = n
// CO: resultado = xn
double potência(double x, int n)
{
    // PC
    double resultado;
    resultado = 0;
    x = 0;
    n = 1;
    // CO
    return resultado;
}
(Este preciosismo, de garantir através da PC e da CO que determinadas variáveis não mudam de valor, será abandonado na maior parte dos exemplos destas folhas, por se admitir que essa restrição é evidentemente necessária.)

Como 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:

// PC: n > 0 e x = X e n = N
// CO: resultado = xn e x = x e n = n
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;
}

Metodologia

A metodologia típica de desenvolvimento de um ciclo corresponde a:
  1. Escolher uma CI para o ciclo.
  2. Escolher uma guarda G tal que CI e ~ G => CO.
  3. Escolher uma inicialização inic de modo a garantir a veracidade de CI logo no início do ciclo.
  4. Escolher o passo do ciclo de modo a que o invariante se mantenha verdadeiro e, muito importante, se garanta a terminação do ciclo.
A escolha da CI faz-se, obviamente, olhando para a CO do ciclo.  Esta escolha é, porventura, a fase mais difícil no desenvolvimento de um ciclo.  Não existem panaceias para esta dificuldade.  É necessário usar de intuição, arte, engenhosidade, conhecimento de casos semelhantes, etc.  Mas existe uma metodologia, desenvolvida por Edsger Dijkstra [5], que funciona bem para um grande número de casos.  A ideia subjacente à metodologia é que a CI se deve obter por relaxamento da CO, pois pretende-se que CI e ~ G => CO.  Apresentar-se-ão aqui apenas dois dos possíveis métodos para o fazer:
  1. Substituir uma das constantes da CO por uma variável com limites apropriados, obtendo-se assim a CI.  A maior parte das vezes substitui-se uma constante que seja limite de um quantificador.
  2. Se a CO corresponde à conjunção de várias proposições, escolher parte delas para a CI e outra parte para a G.  Por exemplo, se CO: C0 e C1 e Cm-1, então poder-se-ia escolher CI: C0 e C1 e ... Cm-2 e G: Cm-1, por exemplo.  A este método chama-se factorização da CO.
Note-se que muitas vezes só ao se desenvolver o passo do ciclo se verifica que a CI escolhida não é apropriada.  Sempre que se verificar que a CI não é apropriada, deve-se voltar atrás e escolher uma nova CI.

No caso do exemplo apresentado a escolha apropriada (só se pode confirmar se a escolha foi apropriada depois de completado o desenvolvimento do ciclo) corresponde a substituir n por uma variável inteira i (o nome não é importante, desde que não colida com os de outras variáveis da função).  Assim, CI: resultado = xi e 1 <= i <= n e x = x e n = n.  Ou seja, a condição invariante indica que resultado contém uma potência de x entre 1 e n.  Note-se que se introduziu na CI a gama de valores aceitável para a nova variável i (neste caso, como n > 0, escolheu-se 0 < i).  Note-se ainda que xn = (P k : 0 <= k < n : x), pelo que de facto se procedeu como sugerido na metodologia.

A escolha da guarda também é simples neste caso. ~ G deve ser tal que resultado = xi e 1 <= i <= n e x = x e n = n e ~ G obriguem a que i seja n e portanto resultado = xn!  A escolha acertada é ~ G: i = n, ou seja, G: i <> n.  Traduzindo para C++:

    // 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 1 <= i <= n e x = x e n = n e i <> n
        passo
        // CI
    }
    // CI e i = n => CO
Em seguida deve-se escolher a inicialização inic.  Deve sempre escolher-se uma inicialização o mais trivial possível.  Neste caso, essa escolha corresponde a atribuir 1 a i e x a resultado, pois nesse caso CI é verdadeira: x = x1 e 1 <= 1 <= n e x = x e n = n (lembre-se que a PC impõe n > 0).  Ou seja, traduzindo para C++:
    // 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
Note-se que se poderia igualmente ter inicializado resultado com 1 e i com 0 (desde que se alargasse a gama de valores aceitáveis para i em CI), mas isso punha o problema da indeterminação 00, pois o valor inicial de x pode ser qualquer.  Como resolveria o problema?

Em seguida deve-se escolher o passo.  Sendo que o ciclo começa com i = 1 e termina quando i = n (e n > 0), então é óbvio que, se i aumentar de pelo menos uma unidade em cada passo, ultrapassará fatalmente n em tempo finito!  Assim, parte do passo corresponderá a aumentar o valor de i, sendo a escolha mais simples a simples incrementação: i++.  Esta escolha tem a vantagem adicional de garantir que i atinge n, o que é fundamental para que a guarda se torne falsa e o ciclo termine.  Mas esta é apenas uma parte do passo: é chamado o progresso (prog) do ciclo, pois garante que ele progride em direcção à falsidade da guarda.

Mas o passo tem de levar também à veracidade de CI.  Para isso, são necessárias normalmente acções que mantenham a veracidade de CI apesar do progresso.  A essa parte do passo chama-se normalmente a acção do ciclo.  Assim, normalmente passo corresponde a

    acção
    progresso
sendo que neste caso já se escolheu o progresso:
    acção
    i++;
Colocando as asserções que são verdadeira no passo do ciclo e manipulando-as um pouco (matematicamente):
     // CI e G, ou seja, resultado = xi e 1 <= i <= n e x = x e n = n e i <> n
    // ou seja, resultado = xi e 1 <= i < n e x = x e n = n
    // ou seja, resultado  x = xi x = xi+1 e 2 <= i + 1 < n + 1 e x = x e n = n
    // ou seja, resultado  x = xi x = xi+1 e 2 <= i + 1 <= n e x = x e n = n
    // o que implica, resultado  x = xi x = xi+1 e 1 <= i + 1 <= n e x = x e n = n
    // o pelo que se torna evidente que a acção a usar é
    resultado *= x; // resultado = resultado * x
    i++; // i = i + 1
    // pois conduz, em conjunto com o progresso, a
    // resultado = xi e 1 <= i <= n e x = x e n = n
    // ou seja, conduz a CI, como se pretendia!
Concluindo, a metodologia apresentada permitiu desenvolver o seguinte ciclo (e função) e demonstrar simultaneamente o seu bom funcionamento:
// PC: n > 0 e x = x e n = n
// CO: resultado = xn e x = x e n = n
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 1 <= i <= n e x = x e n = n
    while(i != n) { // G: i <> n
        // CI e G, ou seja, resultado = xi e 1 <= i <= n e x = x e n = n e i <> n
        // ou seja, resultado = xi e 1 <= 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 1 <= i + 1 <= n e x = x e n = n
        // o pelo que se torna evidente que a acção a usar é
        resultado *= x; // resultado = resultado * x
        i++; // i = i + 1
        // pois conduz, em conjunto com o progresso, a
        // resultado = xi e 1 <= i <= n e x = x e n = n
        // ou seja, conduz a CI, como se pretendia!
    }
    // CI e ~ G => CO, ou seja
    // resultado = xi e 1 <= i <= n e x = x e n = n e i = n
    // => CO: resultado = xn e x = x e n = n
    return resultado;
}
que, 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):
// PC: n > 0 e x = x e n = n
// CO: resultado = xn e x = x e n = n
double potência(double x, int n)
{
    double resultado = x;
    int i = 1;
    // CI: resultado = xi e 1 <= i <= n e x = x e n = n
    while(i != n) {
        resultado *= x;
        i++;
    }
    return resultado;
}
Ou, usando a instrução iterativa for,
// PC: n > 0 e x = x e n = n
// CO: resultado = xn e x = x e n = n
double potência(double x, int n)
{
    // CI: resultado = xi e 1 <= i <= n e x = x e n = n
    double resultado = x;
    for(int i = 1; i != n; i++)
        resultado *= x;
    return resultado;
}
Este 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.

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.  Estes assuntos serão tratados com maior profundidade em Computação e Algoritmia.

Outro exemplo

Pretende-se desenvolver uma função que 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).  Como anteriormente, começa por se escrever o "esqueleto" da função (ver Secção 4.3.1, Conjunções e o quantificador universal):
bool éPrimo(int n)
{
    // PC: n >= 0
    bool é_primo;

    // CO: é_primo = ((Q i : 2 <= i < n : n % i <> 0) e n > 1)
    return é_primo;
}

Como abordar este problema?  Em primeiro lugar, é conveniente verificar que os valores 0 e 1 são casos particulares.  O primeiro porque é divisível por todos os naturais, e o segundo porque, apesar de só ser divisível por 1 e por si próprio, não é considerado um número primo.  Mas então, como se tem que PC => (n <= 1 ou n > 1), e que
// PC e n <= 1
é_primo = false;
// CO
e se deseja construir um ciclo ciclo para resolver o problema mais genérico (é óbvio que será um ciclo, pois têm de se testar todos os possíveis divisores entre 2 e n)
// PC e n > 1
ciclo
// CO
pode-se resolver o problema, de acordo com a descrição mais formal da semântica do if feita na Secção 4.1.1, estruturando a função da seguinte forma:
bool éPrimo(int n)
{
    // PC: n >= 0
    bool é_primo;

    if(n <= 1)
        é_primo = false;
    else
        ciclo
    // CO: é_primo = ((Q i : 2 <= i < n : n % i <> 0) e n > 1)
    return é_primo;
}

Assim, o problema resume-se a escrever o ciclo
// PC': n > 1
ciclo
// CO': é_primo = (Q i : 2 <= i < n : n % i <> 0)
A condição invariante deste ciclo pode ser obtida pela mesma metodologia usada anteriormente: basta substituir o limite superior da conjunção (o "qualquer que seja") por uma variável k criada para o efeito.  Assim, obtém-se
// PC': n > 1
int k;
inic
// CI: (é_primo = (Q i : 2 <= i < k : n % i <> 0)) e 2 <= k <= n
while(G) {
    passo
}
// CO': é_primo = (Q i : 1 < i < n : n % i <> 0)
O que significa esta condição invariante?  Simplesmente que a variável é_primo tem valor lógico verdadeiro se e só se não existirem divisores de n superiores a 1 e inferiores a k, sendo k um valor entre 2 e n.

A escolha da guarda é muito simples: quando o ciclo terminar CI e ~ G deve implicar a CO.  Isso consegue-se simplesmente fazendo ~ G: k = n, ou seja, G: k <> n.  Quanto à inicialização, também é simples, pois basta atribuir 2 a k para que a conjunção não tenha qualquer termo e portanto tenha valor lógico V.  Assim, a inicialização é:

int k = 2;
é_primo = true;
Ou seja
// PC': n > 1
int k = 2;
é_primo = true;
// CI: (é_primo = (Q i : 2 <= i < k : n % i <> 0)) e 2 <= k <= n
while(k != n) {
    passo
}
// CO': é_primo = (Q i : 1 < i < n : n % i <> 0)
Que progresso utilizar?  A forma mais simples de garantir a terminação do ciclo é simplesmente incrementar k.  Ou seja
// PC': n > 1
int k = 2;
é_primo = true;
// CI: (é_primo = (Q i : 2 <= i < k : n % i <> 0)) e 2 <= k <= n
while(k != n) {
    acção
    k++;
}
// CO': é_primo = (Q i : 1 < i < n : n % i <> 0)
Finalmente, falta determinar a acção a executar para garantir a veracidade da CI apesar do progresso.  No início do passo tem-se que quer a CI quer a G são verdadeiras, ou seja:
(é_primo = (Q i : 2 <= i < k : n % i <> 0)) e 2 <= k <= n e k <> n
ou seja,
(é_primo = (Q i : 2 <= i < k : n % i <> 0)) e 2 <= k < n
o que, por simples manipulações da segunda proposição, implica
(é_primo = (Q i : 2 <= i < k : n % i <> 0)) e 2 <= k + 1 <= n
pelo que o segundo termo da CI se verifica apesar do progresso (que incrementa k, recorda-se).  Depois da acção, e antes do progresso, desejar-se-ia que
(é_primo = (Q i : 2 <= i < k + 1 : n % i <> 0)) e 2 <= k + 1 <= n
para que a CI fosse obtida por simples aplicação do progresso.  Mas
é_primo = (Q i : 2 <= i < k + 1 : n % i <> 0)
é o mesmo que
é_primo = ((Q i : 2 <= i < k : n % i <> 0) e n % k <> 0)
mas então a condição invariante é recuperada se a acção for
é_primo = (é_primo && n % k != 0);
onde os parênteses são dispensáveis dadas as regras de precedência dos operadores em C++ (Secção 2.5.6, Tabela Precedência de operadores).

Escrevendo agora o ciclo completo tem-se:

// PC': n > 1
int k = 2;
é_primo = true;
// CI: (é_primo = (Q i : 2 <= i < k : n % i <> 0)) e 2 <= k <= n
while(k != n) {
    é_primo = é_primo && n % k != 0;
    k++;
}
// CO': é_primo = (Q i : 1 < i < n : n % i <> 0)
Reforço da guarda
A observação atenta deste ciclo revela que a variável é_primo, se alguma se tornar falsa, nunca mais deixará de o ser, pelo que o ciclo poderia terminar antecipadamente.  Ou seja, o ciclo só deveria continuar enquanto é_primo e k <> n.  Será que esta nova guarda G: é_primo e k <> n reforçada é mesmo apropriada?

Em primeiro lugar é necessário demonstrar que, quando o ciclo termina, se atinge a CO'.  Ou seja, CI e ~ G => CO'?  Neste caso

CI e ~ G: (é_primo = (Q i : 2 <= i < k : n % i <> 0)) e 2 <= k <= n e (~ é_primo ou k = n)
Mas, se ~ é_primo é V, então ~ (Q i : 2 <= i < k : n % i <> 0) é verdadeira, ou seja, (E i : 2 <= i < k : n % i = 0) é verdadeira, pelo que (E i : 2 <= i < n : n % i = 0) também o é (simplesmente se acrescentaram termos à disjunção) e portanto (Q i : 2 <= i < n : n % i <> 0) é falsa.  Ou seja, CO' é verdadeira!  O caso em que k = n é idêntico ao caso sem reforço da guarda.  Logo, a CO' é de facto atingida *.

Finalmente, é necessário verificar de novo a acção.   No início do passo tem-se que quer a CI quer a G são verdadeiras, ou seja:

(é_primo = (Q i : 2 <= i < k : n % i <> 0)) e 2 <= k <= n e é_primo e k <> n
ou seja,
(Q i : 2 <= i < k : n % i <> 0) e 2 <= k < n
o que, por simples manipulações da segunda proposição, implica
(Q i : 2 <= i < k : n % i <> 0) e 2 <= k + 1 <= n
pelo que o segundo termo da CI se verifica apesar do progresso (que incrementa k, recorda-se).  Depois da acção, e antes do progresso, desejar-se-ia que
(é_primo = (Q i : 2 <= i < k + 1 : n % i <> 0)) e 2 <= k + 1 <= n
para que a CI fosse obtida por simples aplicação do progresso.  Mas
é_primo = (Q i : 2 <= i < k + 1 : n % i <> 0)
é o mesmo que
é_primo = ((Q i : 2 <= i < k : n % i <> 0) e n % k <> 0)
donde, como (Q i : 2 <= i < k : n % i <> 0) é verdadeira
é_primo = n % k <> 0
Mas então a condição invariante é recuperada se a acção for simplesmente
é_primo = n % k != 0;
ou seja
// PC': n > 1
int k = 2;
é_primo = true;
// CI: (é_primo = (Q i : 2 <= i < k : n % i <> 0)) e 2 <= k <= n
while(é_primo && k != n) {
    é_primo = n % k != 0;
    k++;
}
// CO': é_primo = (Q i : 1 < i < n : n % i <> 0)
Outra forma de perceber a alteração da acção passa por perceber que, sendo a G sempre verdadeira no passo do ciclo, a variável é_primo tem aí sempre o valor V, pelo que a acção antiga tinha uma conjunção com a veracidade.  Como V e P é o mesmo que P, pois V é o elemento neutro da conjunção, a conjunção pode ser eliminada.

* Se não lhe pareceu claro lembre-se que (A ou B) => C é o mesmo que A => C e B => C.  Lembre-se ainda que A e (B ou C) é o mesmo que (A e B) ou (A e C).

Simplificações finais
Convertendo para a instrução for e inserindo no código entretanto desenvolvido, tem-se:
// PC: n >= 0
// CO: é_primo = ((Q i : 2 <= i < n : n % i <> 0) e n > 1)
bool éPrimo(int n)
{
    bool é_primo;

    if(n <= 1)
        é_primo = false;
    else {
        // PC': n > 1
        // CO': é_primo = (Q i : 1 < i < n : n % i <> 0)

        // CI: (é_primo = (Q i : 2 <= i < k : n % i <> 0)) e 2 <= k <= n
        é_primo = true;
        for(k = 2; é_primo && k != n; k++)
            é_primo = n % k != 0;
    }
    return é_primo;
}

Mas uma observação atenta da função revela que ainda pode ser simplificada (do ponto de vista da sua escrita) para
// PC: n >= 0
// CO: devolve valor lógico de ((Q i : 2 <= i < n : n % i <> 0) e n > 1)
bool éPrimo(int n)
{
    if(n <= 1)
        return false;

    // PC': n > 1
    // CO': é_primo = (Q i : 1 < i < n : n % i <> 0)

    // CI: (é_primo = (Q i : 2 <= i < k : n % i <> 0)) e 2 <= k <= n
    bool é_primo = true;
    for(k = 2; é_primo && k != n; k++)
        é_primo = n % k != 0;
    return é_primo;
}

ou mesmo
// PC: n >= 0
// CO: devolve valor lógico de ((Q i : 2 <= i < n : n % i <> 0) e n > 1)
bool éPrimo(int n)
{
    if(n <= 1)
        return false;

    // PC': n > 1
    // CO': devolve o valor lógico de (Q i : 1 < i < n : n % i <> 0)

    for(int k = 2; k != n; k++)
        if(n % k == 0)
            return false;
    return true;
}

Este último formato é muito comum em programas escritos em C ou C++, embora o seu estilo seja no mínimo discutível.

Ainda outro exemplo

Suponha-se que se pretende desenvolver 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 (usando passagem de argumentos por referência), sem que se possa fazer uso dos operadores *, / e % do C++.  A estrutura do procedimento é (ver Secção 4.3.1, O resto da divisão):
void divisãoInteira(int dividendo, int divisor, int& q, int& r)
{
    // PC: dividendo >= 0 e divisor > 0
    // CO: 0 <= r < divisor e dividendo = q divisor + r
}
Repare que a CO é a definição de divisão inteira!  I.e., o quociente multiplicado pelo divisor e somado do resto tem de resultar no dividendo, e o resto tem de ser não negativo e menor que o divisor (senão não estaria completa a divisão!).

Como é evidente a divisão tem de ser conseguida através de um ciclo.  Qual a sua CI?  Neste caso ver-se-á que a solução passa por factorizar a CO.  Mas antes de olhar para o desenvolvimento que se segue, experimente resolver o problema por si.

Neste caso a CO é a conjunção de três proposições

CO: r < divisor e dividendo = q divisor + r e 0 <= r
pelo que o método da factorização da CO pode ser utilizado.  Mas quais das proposições usar para ~ G e quais usar para CI?  Um pouco de experimentação e alguns falhanços levam a que se perceba que a ~ G deve corresponder à primeira proposição, ou seja
G: r >= divisor
CI: dividendo = q divisor + r e 0 <= r
Dada esta escolha, qual a forma mais simples de inicializar o ciclo?  É evidente que é fazendo
r = dividendo;
q = 0;
pois as PC garantem que dividendo é não negativo.

Que progresso utilizar?  Note-se que, no início do passo do ciclo se tem CI e G, pelo que

dividendo = q divisor + r e 0 <= r e r >= divisor
ou seja
dividendo = q divisor + r e r >= divisor
Decrementar r certamente conduziria à tarminação do ciclo, mas que fazer a q para recuperar o invariante?  É óbvio que q só pode variar de valores inteiros, pelo que r deve variar de múltiplos de divisor.  Como se pretende que o ciclo termine, deve-se fazer o valor de r diminui.  A forma mais simples é subtrair-lhe o valor de divisor.  Manipulando um pouco a expressão acima
dividendo = (q + 1) divisor + r - divisor e r - divisor >= 0
Ou seja, o progresso a utilizar deve ser
r -= divisor;
e a acção
q++;
pelo que o procedimento fica
// PC: dividendo >= 0 e divisor > 0
// CO: 0 <= r < divisor e dividendo = q divisor + r
void divisãoInteira(int dividendo, int divisor, int& q, int& r)
{
    // CI: dividendo = q divisor + r e 0 <= r
    for(q = 0, r = dividendo; r >= divisor; r -= divisor)
        q++;
}

4.3.3  Exercícios

Escreva programas para testar todas as funções e procedimentos desenvolvidos.

1.  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.

2.a)  Desenvolva um programa que escreva no ecrã todos os números primos entre 2 e n (inclusivé), sendo n dado pelo utilizador.

2.b)  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: 

Introduza a altura do quadrado: 4
****
*  *
*  *
****
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: 8
********
**    **
* *  * *
*  **  *
*  **  *
* *  * *
**    **
********
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 um conjunto de caracteres: qwe*98*8wer*we112rwq
Contei 3 asteriscos.
5.a)  Desenvolva uma função que calcule, duma forma iterative, o valor da sequência de Fibonacci num determinado mês, passado como argumento.  Que condição invariante deverá usar?

5.b)  Escreva uma função que calcule a multiplicação inteira de dois números recorrendo apenas aos operadores aritméticos + e -.

6.  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'.

7.  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.

8.  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.

4.4  Referências

[1]  Aurélio Buarque de Holanda Ferreira, "Novo Dicionário da Língua Portuguesa", 2ª edição, Editora Nova Fronteira, S.A., Rio de Janeiro, 1986.

[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]. *

[5]  Edsger Dijkstra, "A Discipline of Programming", Prentice Hall, 1976. *

[6]  Bjarne Stroustrup, "The C++ Programming Language", terceira edição, Addison-Wesley, Reading, Massachusetts, 1998.

* Existe na biblioteca do ISCTE.