4  Controlo do fluxo dos programas

Quase todas as resoluções de problemas envolvem tomadas de decisões e repetições.  Dificilmente se consegue encontrar um algoritmo interessante que não envolva, quando lido em português, as palavras 'se' e 'enquanto', correspondendo aos conceitos de selecção ou alternativa e de iteração ou repetição.  Neste capítulo estudar-se-ão os mecanismos que a linguagem C++ fornece para suportar esses conceitos e discutir-se-ão metodologias de resolução de problemas usando esses mecanismos.

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

Suponha-se que se pretendia desenvolver uma função para calcular o valor absoluto de um inteiro.  O "esqueleto" da função pode ser o que se segue

/*
   Esta função devolve o valor absoluto do argumento.
   PC: (sem restrições)
   CO: absoluto = |x|, ou seja, absoluto >= 0 e (absoluto = -x ou absoluto = x)
*/
int absoluto(int x)
{
    ...
}

A resolução deste problema requer que sejam tomadas acções diferentes consoante o valor de x seja positivo ou negativo (ou nulo).  São portanto fundamentais as chamadas instruções de selecção ou alternativa.

4.1.1  As instruções if e if else

if(x < 0)  // 1
    x = 0; // 2
else       // 3
    x = 1; // 4
...        // 5

Como a instrução na linha 2 só é executada se x < 0, diz-se que x < 0 é a sua guarda, normalmente representada por G.  De igual modo, a guarda da instrução na linha 4 é x >= 0.  A guarda da instrução controlada após o else está implícita, podendo ser obtida por negação da guarda do if: ¬(x < 0) é equivalente a x >= 0.  Assim, numa instrução de selecção pode-se sempre inverter a ordem das instruções controladas desde que se negue a condição.  Por exemplo,

if(x < 0)
    // G₁: x < 0
    x = 0;
else
    // G₂: x >= 0
    x = 1;

if(x >= 0)
    // G₂: x >= 0
    x = 1;
else
    // G₁: x < 0
    x = 0;

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.  Uma instrução condicional é sempre equivalente a uma instrução de selecção em que a instrução após o else é uma instrução nula (a instrução nula corresponde em C++ a um simples terminador ;).  Ou seja, o exemplo anterior é equivalente a:

if(x < 0)  // 1
    x = 0; // 2a
else       // 2b
    ;      // 2c
...        // 3

int x, y;
...
if(x > y) {
    int t = x;
    x = y;
    y = t;
}

Instruções alternativas encadeadas

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;
}

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;

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;

Guardas em instruções alternativas encadeadas

if(a < minimo)
    // G₁: a < mínimo
    cout << a << " menor que mínimo." << endl;
else if(a <= maximo)
    // G₂: mínimo <= a e a <= máximo
    cout << a << " entre mínimo e máximo." << endl;
else
    // G₃: mínimo <= a e máximo < a
    cout << a << " maior que máximo." << endl;

As n guardas de uma instrução de selecção, construída com n - 1 instruções if encadeadas, podem ser obtidas a partir das condições de cada um dos if como se segue:

if(C₁)
    // G₁: C₁
    ...
else if(C₂)
    // G₂: ¬G₁ e C₂ (ou seja, ¬C₁eC₂)
    ...
else if(C₃)
    // G₃: ¬G₁ e ¬G₂ e C₃ (ou seja, ¬C₁ e ¬C₂eC₁)
    ...
...
else if(C_n-1)
    // G_n-1: ¬G₁ e ... e ¬G_n-2eC_n-1 (ou seja, ¬C₁e ... e ¬C_n-2eC_n-1)
    ...
else
    // G_n: ¬G₁ e ... e ¬G_n-2e ¬G_n-1 (ou seja, ¬C₁e ... e ¬C_n-1)
    ...

Influência de pré-condições

// PC: mínimo < máximo
if(a < minimo)
    // G₁: a < mínimo
    cout << a << " menor que mínimo." << endl;
else if(a <= maximo)
    // G₂: mínimo <= a e a <= máximo
    cout << a << " entre mínimo e máximo." << endl;
else
    // G₃: máximo < a
    cout << a << " maior que máximo." << endl;

4.1.2  Problemas comuns

if(m == 0)
    if(n == 0)
        cout << "m e n são zero." << endl;
else
    cout << "m não é zero." << endl;

if(m == 0) {
    if(n == 0)
        cout << "m e n são zero." << endl;
} else
    cout << "m não é zero." << endl;

Um outro erro frequente corresponde a colocar um ; logo após a condição do if ou logo após o else.  Por exemplo, a intenção do programador do troço de código

if(x < 0);
    x = 0;

if(x < 0)
    ; // instrução nula: não faz nada.
x = 0;

4.1.3  Desenvolvimento de instruções alternativas

Asserções

Note-se que nas asserções cada variável pertence a um determinado conjunto.  Para as variáveis C++, esse conjunto é determinado pelo tipo da variável indicado na sua definição (e.g., int x; significa que x pertence ao conjunto dos inteiros entre -2^n-1 e 2^n-1 - 1, se os int tiverem n bits).  Para as variáveis matemáticas, esse conjunto deveria, em rigor, ser indicado explicitamente.  Neste texto, no entanto, admite-se que as variáveis matemáticas pertencem ao conjunto dos inteiros, salvo onde for explicitamente indicado outro conjunto ou onde o conjunto seja fácil de inferir pelo contexto da asserção.  Finalmente, nas asserções é normal assumir que as variável C++ não têm limitações (e.g., admite-se que uma variável int pode guardar qualquer inteiro).  Embora isso não seja verdade, permite resolver um grande número de problemas sem que se introduzam demasiados detalhes nas demonstrações.

Em cada ponto de um programa existe um determinado conjunto de variáveis, cada uma das quais pode tomar determinados valores, consoante o seu tipo.  Ao conjunto de todos os possíveis valores de todas as variáveis existentes num dado ponto de um programa chama-se o espaço de estados nesse ponto.  Ao conjunto dos valores das variáveis existentes num determinado ponto do programa num determinado instante de tempo chama-se o estado de um programa.  Assim, o estado de um programa é um elemento do espaço de estados.

Dedução de asserções

++n;

// n >= 0
++n;

// n >= 0
++n;
// n >= 1

A demonstração informal da correcção de um pedaço de código pode, portanto, ser feita recorrendo a asserções.  Suponha-se que se pretende demonstrar que o código

int t = x;
x = y;
y = t;

// x = y e y = x

// x = x e y = y

// x = x e y = y
int t = x;
x = y;
y = t;
// x = y e y = x

// x = x e y = y
int t = x;
// x = x e y = yet = x
x = y;
// x = y e y = yet = x
y = t;
// x = y e y = x (e t = x)

Predicados mais fortes e mais fracos

Dedução da pré-condição mais fraca de uma atribuição

// PC = ???
x = expressão;
// CO

Por exemplo, suponha-se que se pretendia saber qual a PC mais fraca para a qual a instrução de atribuição x = -x; conduz à CO x >= 0.  Aplicando o método descrito a

// PC = ???
x = -x;
// CO: x >= 0

// PC: -x >= 0, ou seja, x <= 0
x = -x;
// CO: x >= 0

Voltando ao exemplo da troca de valores de duas variáveis

int t = x;
x = y;
y = t;
// x = y e y = x

int t = x;
x = y;
// x = y e t = x
y = t;
// x = y e y = x

int t = x;
// y = y e t = x
x = y;
// x = y e t = x
y = t;
// x = y e y = x

// y = y e x = x
int t = x;
// y = y e t = x
x = y;
// x = y e t = x
y = t;
// x = y e y = x

Em geral este método não conduz exactamente à PC escrita inicialmente.  Suponha-se que se pretendia demonstrar que

// PC: x < 0
x = -x;
// x >= 0

// PC: x < 0
// -x >= 0 ou seja, x <= 0
x = -x;
// x >= 0

Asserções em instruções de selecção

if(x > y) {
    int t = x;
    x = y;
    y = t;
}

// PC: x = x ey = y
if(x > y) {
    int t = x;
    x = y;
    y = t;
}
// CO: x <= y e ((x = x e y = y) ou (x = y e y = x))

Será que a instrução condicional conduz forçosamente da PC à CO?  É necessário demonstrá-lo.

É conveniente começar por converter a instrução condicional na instrução de selecção equivalente e, simultaneamente, explicitar as guardas das instruções controladas:

// PC: x = xey = y
if(x > y) {
    // G₁: x > y
    int t = x;
    x = y;
    y = t;
} else
    // G₂: x <= y
    ; // instrução nula!
// ??

// PC: x = xey = y
if(x > y) {
    // x > y ex = x e y = y
    int t = x;
    x = y;
    y = t;
} else
    // x <= y ex = x e y = y
    ;
// ??

// PC: x = xey = y
if(x > y) {
    // x > y ex = x e y = y
    int t = x;
    // t > y ex = x e y = y e t = x
    x = y;
    // t > x ex = y e y = y et = x
    y = t;
    // y > x ex = y e y = x (e t = x)
} else
    // x <= y ex = x e y = y
    ;
    // x <= y ex = x e y = y, a instrução nula não afecta as asserções...
// ??

// y > x e x = y e y = x
// x <= y e x = y e y = x

// PC: x = xey = y
if(x > y) {
    int t = x;
    x = y;
    y = t;
    // x <= y e x = y e y = x
} else
    ;
    // x <= y ex = x e y = y
// ??

// PC: x = xe y = y
if(x > y) {
    int t = x;
    x = y;
    y = t;
    // x <= y ex = y e y = x
} else
    ;
    // x <= y ex = x e y = y
// (x <= y e x = y e y = x) ou (x <= yex = x e y = y)
// ou seja,
// x <= y e ((x = y e y = x) ou (x = xey = y))

Mais uma vez seria possível partir dos objectivos durante a demonstração.  Neste caso começa por se observar que a CO tem de ser válida no final de qualquer das instruções controladas pela instrução de selecção:

// PC: x = xey = y
if(x > y) {
    // G₁: x > y
    int t = x;
    x = y;
    y = t;
    // x <= y e ((x = y e y = x) ou (x = x e y = y))
} else
    // G₂: x <= y
    ;
    // x <= y e ((x = y e y = x) ou (x = x e y = y))
// CO: x <= y e ((x = y e y = x) ou (x = x e y = y))

// PC: x = xey = y
if(x > y) {
    // G₁: x > y
    // y <= x e ((y = y e x = x) ou (y = x e x = y))
    int t = x;
    // y <= t e ((y = y e t = x) ou (y = x e t = y))
    x = y;
    // x <= t e ((x = y e t = x) ou (x = x e t = y))
    y = t;
    // x <= y e ((x = y e y = x) ou (x = x e y = y))
} else
    // G₂: x <= y
    // x <= y e ((x = y e y = x) ou (x = x e y = y))
    ;
    // x <= y e ((x = y e y = x) ou (x = x e y = y))
// CO: x <= y e ((x = y e y = x) ou (x = x e y = y))

// PC: x = xey = y
if(x > y) {
    // G₁: x > y
    // y <= x e ((y = y e x = x) ou (y = x e x = y))
    int t = x;
    x = y;
    y = t;
} else
    // G₂: x <= y
    // x <= y e ((x = y e y = x) ou (x = x e y = y))
    ;
// CO: x <= y e ((x = y e y = x) ou (x = x e y = y))

1. PC e G₁ implica y <= xe ((y = y e x = x) ou (y = x e x = y)) e que
2. PC e G₂ implica x <= ye ((y = x e x = y) ou (y = y e x = x))),

Em geral, portanto, para demonstrar a correcção de uma instrução de selecção (com n alternativas, ou seja, com n instruções controladas)

// PC
if(C₁)
    // G₁: C₁
    instrução₁
else if(C₂)
    // G₂: ¬G₁e C₂
    instrução₂
else if(C₃)
    // G₃: ¬G₁ e ¬G₂ e C₃
    instrução₃
...
else if(C_n-1)
    // G_n-1: ¬G₁ e ... e ¬G_n-2eC_n-1
    instrução_n-1
else
    // G_n: ¬G₁ e ... e ¬G_n-1
    instrução_n
// CO

• Demonstração directa (partindo da PC):
1. Para cada instrução controlada instrução_i (com i de 1 a n), deduz-se a respectiva CO_i admitindo que a pré-condição PC da instrução de selecção e a guarda G_i da instrução controlada são ambas verdadeiras.  Ou seja, deduz-se CO_i tal que:
// PC e G_i
instrução_i
// CO_i
2. Demonstra-se que CO₁ ou CO₂ou ... ou CO_n implicaCO.  Ou, o que é o mesmo, que (CO₁ implicaCO) e ... e (CO_n implica CO).
• Demonstração inversa (partindo da CO):
1. Para cada instrução controlada instrução_i (com i de 1 a n), determina-se a pré-condição mais fraca PC_i que leva forçosamente à CO da instrução de selecção.  Ou seja, determina-se a PC_i mais fraca tal que:
// PC_i
instrução_i
// CO
2. Demonstra-se que PC e G_i implicaPC_i (com i de 1 a n).

Desenvolvimento

Regresse-se ao problema inicial, da escrita de uma função para calcular o valor absoluto de um valor inteiro.  O objectivo é, portanto, preencher o corpo da função com "esqueleto"

/*
   Esta função devolve o valor absoluto do argumento.
   PC: V (sem restrições)
   CO: absoluto = |x|, ou seja, absoluto >= 0 e (absoluto = -x ou absoluto = x)
*/
int absoluto(int x)
{
    ...
}

Para simplificar o desenvolvimento, pode-se começar o corpo pela definição de uma variável local para guardar o resultado e terminar com a devolução do seu valor, o que permite escrever as asserções principais da função em termos do valor desta variável *:

/*
   Esta função devolve o valor absoluto do argumento.
   PC: V
   CO: absoluto = |x|, ou seja, absoluto >= 0 e (absoluto = -x ou absoluto = x)
*/
int absoluto(int x)
{
    int r;
    // PC': V
    ...
    // CO': r >= 0 e (r = -x ou r = x)
    return r;
}

O desenvolvimento usado será baseado nos objectivos.  Este é um princípio importante da programação [4]: a programação deve ser orientada pelos objectivos.  É certo que a pré-condição afecta a solução de qualquer problema, mas os problemas são essencialmente determinados pela condição objectivo.  De resto, com se pode verificar depois de alguma prática, mais inspiração para a resolução de um problema pode ser obtida por análise da condição objectivo do que por análise da pré-condição.  Por exemplo, é comum  não haver qualquer pré-condição na especificação de um problema, donde nesses casos só a condição objectivo poderá ser usada como fonte de inspiração.

* Note-se que a semântica de uma instrução de retorno é muito semelhante à de uma instrução de atribuição, nomeadamente a PC mais fraca pode ser obtida por substituição, na CO da função,do nome da função pela expressão usada na instrução de retorno.  Assim, a PC mais fraca da instrução return r; que leva a

CO: absoluto = |x|, ou seja, absoluto >= 0 e (absoluto = -xouabsoluto = x)

CO: r = |x|, ou seja, r >= 0 e (r = -x ou r = x).

Primeiro passo: escolha das instruções controladas

Segundo passo: determinação das pré-condições mais fracas

// ??
r = -x;
// CO': r >= 0 e (r = -x ou r = x)

// -x >= 0 e (-x = -x ou -x = x) ou seja, x <= 0 e (V ou x = 0), ou seja, x <= 0
r = -x;
// CO': r >= 0 e (r = -x ou r = x)

A mesma verificação pode ser feita para a segunda instrução

// ??
r = x;
// CO': r >= 0 e (r = -x ou r = x)

// x >= 0 e (x = -xoux = x) ou seja, x >= 0 e (x = 0 ou V), ou seja, x >= 0
r = x;
// CO': r >= 0 e (r = -x ou r = x)

Note-se que, até agora, se determinou o seguinte corpo para a função:

/*
   Esta função devolve o valor absoluto do argumento.
   PC: V
   CO: absoluto = |x|, ou seja, absoluto >= 0 e (absoluto = -x ou absoluto = x)
*/
int absoluto(int x)
{
    int r;
    // PC': V
    if(C₁)
        // G₁: ??
        // PC₁: x <= 0
        r = -x;
    else
        // G₂: ??
        // PC₂: x >= 0
        r = x;
    // CO': r >= 0 e (r = -x ou r = x)
    return r;
}

Terceiro passo: determinação das guardas

/*
   Esta função devolve o valor absoluto do argumento.
   PC: V
   CO: absoluto = |x|, ou seja, absoluto >= 0 e (absoluto = -x ou absoluto = x)
*/
int absoluto(int x)
{
    int r;
    // PC': V
    if(C₁)
        // G₁: x <= 0
        r = -x;
    else
        // G₂: x >= 0
        r = x;
    // CO': r >= 0 e (r = -x ou r = x)
    return r;
}

Quarto passo: verificação das guardas

Neste caso a PC' não impõe qualquer restrição, ou seja PC': V.  Logo, tem de se verificar se V implicaG₁ouG₂.  Neste caso G₁ ouG₂ é x <= 0 ou x <= 0, ou seja, V.  Como V implica V, o problema está quase resolvido.

Quinto passo: escrita das instruções de selecção (escolha das condições)

/*
   Esta função devolve o valor absoluto do argumento.
   PC: V
   CO: absoluto = |x|, ou seja, absoluto >= 0 e (absoluto = -x ou absoluto = x)
*/
int absoluto(int x)
{
    int r;
    // PC': V
    if(x <= 0)
        // G₁: x <= 0
        r = -x;
    else
        // G₂: x > 0
        r = x;
    // CO': r >= 0 e (r = -x ou r = x)
    return r;
}

Alterando a solução

/*
   Esta função devolve o valor absoluto do argumento.
   PC: V
   CO: absoluto = |x|, ou seja, absoluto >= 0 e (absoluto = -x ou absoluto = x)
*/
int absoluto(int x)
{
}

/*
   Esta função devolve o valor absoluto do argumento.
   PC: V
   CO: absoluto = |x|, ou seja, absoluto >= 0 e (absoluto = -x ou absoluto = x)
*/
int absoluto(int x)
{
    x = 1;
    return 1;
}

/*
   Esta função devolve o valor absoluto do argumento.
   PC: V
   CO: absoluto = |x|, ou seja, absoluto >= 0 e (absoluto = -x ou absoluto = x)
*/
int absoluto(const int x)
{
    int r;
    if(x <= 0)
        r = -x;
    else
        r = x;
    return r;
}

/*
   Esta função devolve o valor absoluto do argumento.
   PC: V
   CO: absoluto = |x|, ou seja, absoluto >= 0 e (absoluto = -x ou absoluto = x)
*/
int absoluto(const int x)
{
    if(x <= 0)
        return -x;
    else
        return x;
}

/*
   Esta função devolve o valor absoluto do argumento.
   PC: V
   CO: absoluto = |x|, ou seja, absoluto >= 0 e (absoluto = -x ou absoluto = x)
*/
int absoluto(const int x)
{
    if(x <= 0)
        return -x;
    return x;
}

O método

1. Determina-se n instruções instrução_i (com i de 1 a n) que pareçam poder levar à veracidade da CO.  Tipicamente estas instruções são obtidas por análise da CO.
2. Determina-se as pré-condições mais fracas PC_i de cada uma dessas instruções de modo que conduzam à CO.
3. Determina-se uma guarda G_i para cada alternativa i de modo que PC e G_i implique PC_i.  Se o problema não tiver pré-condições (ou seja, PC: V), então pode-se fazer G_i = PC_i.  Note-se que uma guarda G_i = F resolve sempre o problema, embora seja tão forte que nunca leve à execução da instrução respectiva...  Por isso deve-se sempre escolher a guarda o mais fraca possível.
4. Verifica-se se, em todas as circunstâncias, pelo menos uma das guardas G_i encontradas é verdadeira.  Isto é, verifica-se se PCimplicaG₁ou ... ou G_n.  Se isso não acontecer, é necessário acrescentar mais instruções controladas às encontradas no ponto 1.  Para o fazer, identifica-se que casos ficaram por cobrir analisando as guardas já encontradas e a PC.

1. Determina-se os n casos possíveis interessantes, restritos àqueles que verificam a PC, que cobrem todas as hipóteses.  Cada caso possível corresponde a uma guarda G_i.  A verificação da PC tem de implicar a verificação de pelo menos uma das guardas, ou seja, PC implica G₁ou ... ou G_n.  Ou ainda, PCimplica (E i: 1 <= i <= n : G_i).
2. Para cada alternativa i, encontra-se uma instrução instrução_i tal que
// PC e G_i
instrução_i
// CO_i
// CO
ou seja, tal que, se a pré-condição PC e a guarda G_i forem verdadeiras, então a instrução leve forçosamente à veracidade da condição objectivo CO.

Discussão

1. Forçam à especificação rigorosa do problema, e portanto à sua compreensão profunda.
2. O desenvolvimento é acompanhado da demonstração de correcção, o que reduz consideravelmente a probabilidade de erros.
3. Não são descurados aparentes pormenores que, na realidade, podem dar origem a erros graves e difíceis de corrigir.

Para se verificar na prática a importância da especificação cuidada do problema, tente-se resolver o seguinte problema:

Escreva uma função que, dados dois argumentos do tipo int, devolva o booleano verdadeiro se o primeiro for múltiplo do segundo e falso no caso contrário.

A abordagem típica do programador é considerar que um número n é múltiplo de outro m se o resto da divisão de n por m for zero e passar ao código:

bool éMúltiplo(int m, int n)
{
    if(m % n == 0)
        return true;
    else
        return false;
}

Floating exception (core dumped)

Neste ponto o leitor deve parar de ler e tentar resolver o problema.

Chamado o programador original da função, este observa que não há múltiplos de zero, e portanto tipicamente corrige a função para

bool éMúltiplo(int m, int n)
{
    if(n != 0)
        if(m % n == 0)
            return true;
        else
            return false;
    else
        return false;
}

bool éMúltiplo(int m, int n)
{
    if(n != 0)
        if(m % n == 0)
            return true;
        else
            return false;
    else
        if(m == 0)
            return true;
        else
            return false;
}

Depois, o programador olha para o código e acha-o demasiado complicado: para quê as instruções de selecção se uma simples instrução de retorno basta?

Neste ponto o leitor deve parar de ler e tentar resolver o problema com uma única instrução de retorno.

Basta devolver o resultado duma expressão booleana que reflita os casos em que m é múltiplo de n:

bool éMúltiplo(int m, int n)
{
    return (m % n == 0 && n != 0) || (m == 0 && n == 0);
}

bool éMúltiplo(int m, int n)
{
    return (n != 0 && m % n == 0) || (m == 0 && n == 0);
}

Outro exemplo

void limita(int& x, int mínimo, int máximo)

Como habitualmente, começa por se escrever a especificação do procedimento, onde x é uma variável matemática usada para representar o valor inicial da variável C++ x:

/*
   Este procedimento limita x ao intervalo [mínimo, máximo].
   PC: mínimo <= máximo e x = x
   CO: (x = xex >= mínimo e x <= máximo) ou (x = mínimo e x <= mínimo) ou
      (x = máximoex >= máximo)
*/
void limita(int& x, int mínimo, int máximo)
{
}

;  // para manter x com o valor inicial x.

x = mínimo;

x = máximo;

// PC₁: (x = x e x >= mínimo e x <= máximo) ou (x = mínimoex <= mínimo) ou
       (x = máximo e x >= máximo)
;  // para manter x com o valor inicial x.

// PC₂: (mínimo = x e x >= mínimo e x <= máximo) ou (mínimo = mínimoex <= mínimo) ou
       (mínimo = máximo e x >= máximo)
// ou seja:
// PC₂: (mínimo = x e x >= mínimo e x <= máximo) ou x <= mínimoou
       (mínimo = máximo e x >= máximo)
x = mínimo;

// PC₃: (máximo = x e x >= mínimo e x <= máximo) ou (máximo = mínimoex <= mínimo) ou
       (máximo = máximo e x >= máximo)
// ou seja:
// PC₃: (máximo = x e x >= mínimo e x <= máximo) ou (máximo = mínimoex <= mínimo) ou
       x >= máximo
x = máximo;

A determinação das guardas faz-se de modo a que PCeG_i implique PC_i.

No primeiro caso tem-se da PC que x = x, pelo que a guarda mais fraca é:

// G₁: (x >= mínimo e x <= máximo) ou (x = mínimo) ou (x =máximo)
// ou seja:
// G₁: x >= mínimoex <= máximo

No segundo caso, pelas mesmas razões, tem-se que:

// G₂: (mínimo = x e x <= máximo) oux <= mínimo ou
       (mínimo = máximo e x >= máximo)
// ou seja:
// G₂: mínimo = x ou x <= mínimo ou (mínimo = máximo e x >= máximo)
// ou seja:
// G₂: x <= mínimoou (mínimo = máximo e x >= máximo)

Da mesma forma se obtém:

// G₃: (máximo = mínimo e x <= máximo) oux >= máximo

Ou seja, a estrutura da instrução de selecção é (trocando a ordem das instruções de modo a que a instrução nula fique em último lugar):

if(C₁)
    // G₂: x <= mínimo ou (mínimo = máximoex >= máximo)
    x = mínimo;
else if(C₂)
    // G₃: (máximo = mínimo e x <= máximo) oux >= máximo
    x = máximo;
else
    // G₁: x >= mínimo e x <= máximo
    ;

if(C₁)
    // G₂: x <= mínimo
    x = mínimo;
else if(C₂)
    // G₃: x >= máximo
    x = máximo;
else
    // G₁: x >= mínimo e x <= máximo
    ;

if(C₁)
    // G₂: x < mínimo
    x = mínimo;
else if(C₂)
    // G₃: x > máximo
    x = máximo;
else
    // G₁: x >= mínimo e x <= máximo
    ;

Assim, as condições das instruções if são:

if(x < mínimo)
    // G₂: x < mínimo
    x = mínimo;
else if(x > máximo)
    // G₃: x > máximo
    x = máximo;
else
    // G₁: x >= mínimo e x <= máximo
    ;

/*
   Este procedimento limita x ao intervalo [mínimo, máximo].
   PC: mínimo <= máximo e x = x
   CO: (x = xex >= mínimo e x <= máximo) ou (x = mínimo e x <= mínimo) ou
      (x = máximoex >= máximo)
*/
void limita(int& x, int mínimo, int máximo)
{
    if(x < mínimo)
        // G₂: x < mínimo
        x = mínimo;
    else if(x > máximo)
        // G₃: x > máximo
        x = máximo;
    /*
    else
        // G₁: x >= mínimo e x <= máximo
        ;
    */
}

/*
   Este procedimento limita x ao intervalo [mínimo, máximo].
   PC: mínimo <= máximo e x = x
   CO: (x = xex >= mínimo e x <= máximo) ou (x = mínimo e x <= mínimo) ou
      (x = máximoex >= máximo)
*/
void limita(int& x, int mínimo, int máximo)
{
    if(x < mínimo)
        x = mínimo;
    else if(x > máximo)
        x = máximo;
}

4.1.4  O operador ?:

/*
   Esta função devolve o valor absoluto do argumento.
   PC: V
   CO: absoluto = |x|, ou seja, absoluto >= 0 e (absoluto = -x ou absoluto = x)
*/
int absoluto(const int x)
{
    if(x <= 0)
        return -x;
    return x;
}

/*
   Esta função devolve o valor absoluto do argumento.
   PC: V
   CO: absoluto = |x|, ou seja, absoluto >= 0 e (absoluto = -x ou absoluto = x)
*/
int absoluto(const int x)
{
    return x <= 0? -x : x;
}

condição ? expressão₁ : expressão₂

4.1.5  A instrução switch

// CO: surgiu no ecrã a versão por extenso de dígito.
// PC: 0 <= dígito < 10
void escreveDígitoPorExtenso(int dígito)
{
    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
        cout << "nove";
 }

// CO: surgiu no ecrã a versão por extenso de dígito.
// PC: 0 <= dígito < 10
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;
      default:
        cout << "nove";
        break;
    }
}

É possível agrupar várias alternativas:

switch(valor) {
  case 1:
  case 2:
  case 3:
    cout "1, 2, ou 3";
    break;
  ...
}

// CO: surgiu no ecrã a versão por extenso de dígito.
// PC: 0 <= dígito < 10
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";
      default:
        cout << "nove";
    }
}

seteoitonove

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

// PC: 0 <= valore valor < 10000.
// CO: surgiu no ecrã a ordem de grandeza de valor.
void escreveGrandeza(double x)
{
    if(x < 10)
        cout << "unidades";
    else if(x < 100)
        cout << "dezenas";
    else if(x < 1000)
        cout << "centenas";
    else
        cout << "milhares";
}

// PC: 0 <= valore valor < 10000.
// CO: surgiu no ecrã a ordem de grandeza de valor.
void escreveGrandeza(double x)
{
    if(x >= 1000)
        cout << "milhares";
    else if(x >= 100)
        cout << "centenas";
    else if(x >= 10)
        cout << "dezenas";
    else
        cout << "unidades";
}

No caso da instrução de selecção switch a ordem é irrelevante desde que todos os conjuntos de instruções tenham o respectivo break.

4.1.6  Exercícios

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.

O número introduzido foi trinta e cinco.

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

Introduza um conjunto de zeros e uns:
10010011001101
CCBAABA?

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

O conhecimento da sintaxe e da semântica das instruções de iteração do C++ não é suficiente para o desenvolvimento de bom código que as utilize.  Por um lado, o desenvolvimento de bom código C++ obriga à demonstração formal ou informal do seu correcto funcionamento.  Por outro lado, o desenvolvimento de ciclos não é uma tarefa fácil, sobretudo para o principiante.  Assim, na Secção 4.3 apresenta-se um método de demonstração da correcção de ciclos e faz-se uma pequena introdução à metodologia de Dijkstra, que fundamenta e disciplina a construção de ciclos (sem no entanto a mecanizar).

* O adjectivo "recursivo" é um neologismo informático que ainda não consta nos dicionários.  Foi construído por analogia com o adjectivo "iterativo" e tem essencialmente o mesmo significado que "recorrente".  De acordo com [1], iterar significa "tornar a fazer (...) repetir (...)" enquanto recorrer significa "tornar a correr (...)".  Recursão e iteração 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

while(expressão_booleana)
    instrução_controlada

À 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

Exemplo

// PC: n >= 0
// CO: o ecrã contém uma linha adicional com os inteiros de 0 a n exclusivé separados por espaços.
void escreveInteiros(const int n)     // 1
{                               // 2
    int i = 0;                  // 3
    while(i != n) {             // 4
        cout << i << ' ';       // 5
        ++i;                    // 6
    }                           // 7
    cout << endl;               // 8
}                               // 9

Seguindo o fluxograma, 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 depois a verificar a condição (volta a A.).
3. Se a condição for falsa, o ciclo termina.

4.2.2  Variantes do ciclo while: for e do while

inic
while(G) {
    acção
    prog
}

O C++ possui uma outra instrução de iteração, a instrução for, que permite escrever abreviadamente este tipo de ciclos:

for(inic; G; prog)
    acção

O procedimento escreveInteiros() desenvolvido acima pode portanto ser reescrito como:

// PC: n >= 0
// CO: o ecrã contém uma linha adicional com os inteiros de 0 a n exclusivé separados por espaços.
void escreveInteiros(const int n)  // 1
{                                  // 2
    for(int i = 0; i != n; ++i)    // 3
        cout << i << ' ';          // 4
    cout << endl;                  // 5
}

Quaisquer das expressões no cabeçalho de uma instrução for (inic, G e prog) pode ser omitida.  A omissão da guarda G é equivalente à utilização de uma guarda sempre verdadeira, gerando por isso um ciclo infinito, ou laço (loop).  Ou seja, escrever

for(inic; ; prog)
    acção

for(inic; true; prog)
    acção

Este tipo de ciclos só é verdadeiramente interessante se passo contiver alguma instrução return ou break (ver abaixo) que obrigue o ciclo a terminar alguma vez.

Um outro tipo de ciclo em C++ corresponde à instrução dowhile.  A sintaxe desta instrução é:

do
    instrução_controlada
while(expressão_booleana);

Tal como no caso da instrução while, à instrução controlada pela instrução dowhile chama-se passo e à condição que a controla guarda G.  A execução da instrução de iteração do while pode ser representada pelo seguinte fluxograma:

Note-se que, ao contrário do que se passa com a instrução while, durante a execução de uma instrução dowhile o passo é executado sempre pelo menos uma vez.

Exemplo com for

for(int i = 0; i != 10; ++i)
    cout << i << endl;

for(int i = 0; i != 10; ++i)
    cout << '*';
cout << endl; // para terminar a linha.

int i = 0;
for(; i != 10; ++i)
    cout << i << endl;
cout << "O valor final é " << i << endl;

0
1
2
3
4
5
6
7
8
9
O valor final é 10

Exemplo com do while

cout << "Introduza valor (0 a 10): ";
cin >> n;
while(n < 0 || n > 10) {
    cout << "Incorrecto, introduza de novo (0 a 10): ";
    cin >> n;
}

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);

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.

Equivalências entre instruções de iteração

Embora sejam válidas em geral, estas equivalências não são verdadeiras se as instruções controladas incluirem as instruções return, break, continue, ou goto (ver abaixo).  Também há diferença quanto ao âmbito de variáveis definidas nestas instruções.

4.2.3  Exemplo simples

#include <iostream>
using namespace std;

// Escreve um triângulo oco de asteriscos com a altura passada como argumento:
// PC: altura >= 0
// CO: o ecrã contém altura linhas adicionais representando um
// triângulo rectângulo oco de asteriscos.
void escreveTriânguloOco(const 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ânguloOco(a);
}

4.2.4  return, break, continue, e goto em ciclos

// PC: n >= 0
// CO: éPrimo = ((Qi : 2 <= i < n : n ÷ i <> 0) e n > 1)
bool éPrimo(const int n)
{
    if(n <= 1)
        return false;

    for(k = 2; k != n; ++k)
        if(n % k == 0)
            // Se se encontrou um divisor >= 2 e < n, então n não é primo
            // e pode-se retornar imediatamente:
            return false;
    return true;
}

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.  Desaconselha-se vivamente a sua utilização.

A instrução break serve para terminar abruptamente a instrução while, for, do while, ou switch mais interior dentro da qual se encontre (ou seja, se existirem duas dessas instruções encadeadas, uma instrução de break termina apenas a instrução interior), continuando a execução na instrução subsequente.

A instrução continue é semelhante à instrução break, mas serve para começar antecipadamente a próxima iteração do ciclo (apenas no caso das instruções while, for e do while).

Às instruções break e continue aplicam-se as recomendações feitas quanto à utilização da instrução return dentro de ciclos: usar pouco e com cuidado.

Exemplo

cout << "Introduza valor (0 a 10): ";
cin >> n;
while(n < 0 || n > 10) {
    cout << "Incorrecto, introduza de novo (0 a 10): ";
    cin >> n;
}

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);

cout << "Introduza valor (0 a 10): ";
do {
    cin >> n;
    if(n >= 0 || n <= 10)
        break;
    cout << "Incorrecto, introduza de novo (0 a 10): ";
} while(n < 0 || n > 10);

cout << "Introduza valor (0 a 10): ";
do {
    cin >> n;
    if(n >= 0 || n <= 10)
        break;
    cout << "Incorrecto, introduza de novo (0 a 10): ";
} while(true);

cout << "Introduza valor (0 a 10): ";
while(true) {
    cin >> n;
    if(n >= 0 || n <= 10)
        break;
    cout << "Incorrecto, introduza de novo (0 a 10): ";
}

* Noutras linguagens existe uma construção loop para este efeito, que pode ser simulada em C++ recorrendo ao pré-processador (ver capítulos posteriores):

#define loop while(true)

loop {
    cout << "Introduza valor (0 a 10): ";
    cin >> n;
    if(0 <= n && n <= 10)
        break;
    cout << "Incorrecto! ";
}

4.2.5  Problemas comuns

for(int i = 0; i <= 10; ++i)
    cout << '*';

Outro problema comum corresponde a colocar um ; após o cabeçalho de um ciclo.  Por exemplo:

int i = 0;
while(i != 10);
{
    cout << '*';
    ++i;
}

for(int i = 0; i != 10; ++i);
    cout << '*';

4.3  Asserções com quantificadores

A escrita de asserções para problemas um pouco mais complicados que os vistos até aqui requer a utilização de quantificadores.  Quantificadores são formas matemáticas abreviadas de escrever expressões que envolvem a repetição de uma dada operação.  Exemplos são os quantificadores aritméticos somatório e produto, e os quantificadores lógicos universal ("qualquer que seja") e existencial ("existe pelo menos um").

Apresentam-se aqui algumas notas sobre os quantificadores que são mais úteis para a construção de asserções acerca do estado dos programas.  A notação utilizada encontra-se resumida no Apêndice A.

Os quantificadores escrever-se-ão sempre da seguinte forma:

(X v : predicado(v) : expressão(v))

• X indica a operação realizada: S para a soma (somatórios), P para o produto ("produtórios" ou "piatórios"), Q para a conjunção e ("qualquer que seja"), e E para a disjunção ou ("existe pelo menos um").
• v é uma variável muda, que tem significado apenas dentro do quantificador, e que se assume normalmente pertencer ao conjunto dos inteiros.  Se pertencer a outro conjunto tal pode ser indicado explicitamente:
(Q x real : |x| >= 2^½ : x² - 2 >= 0)
• predicado(v) é um predicado envolvendo a variável muda v e que define implicitamente o conjunto de valores de v para os quais deve ser realizada a operação.
• expressão(v) é uma expressão envolvendo a variável v e que deve ter um resultado aritmético (no caso dos quantificadores aritméticos) e lógico (no caso dos quantificadores lógicos).  I.e., no caso dos quantificadores lógicos "qualquer que seja" e "existe pelo menos um", essa expressão deve ser um predicado.

4.3.1  Somas

Por exemplo, é um facto conhecido que o somatório do primeiros n inteiros não negativos (S i : 0 <= i < n : i) tem valor n (n - 1) / 2 se n > 0.  Que acontece se n <= 0?  Neste caso é evidente que a variável muda i não pode tomar quaisquer valores, e portanto o resultado é a soma de zero (0) termos.  A soma de zero termos é zero (0), por ser esse o elemento neutro da soma.  Logo, (S i : 0 <= i < n : i) = 0 se n <= 0.  Em geral, (S i : m <= i < n : expressão(i)) = 0 se n <= m.

Se se pretender desenvolver uma função que calcule a soma dos n primeiros números ímpares positivos (sendo n um parâmetro da função), pode-se começar por escrever o seu cabeçalho bem como a PC e a CO, como habitual:

// PC: n >= 0
// CO: somaÍmpares = (S i : 0 <= i < n : 2 i + 1)
int somaÍmpares(const int n)
{
    ...
}

4.3.2  Produtos

Por exemplo, a definição de factorial é n! = (P i : 1 <= i <= n : i ) se n >= 0.

O produto de zero termos é um (1), por ser esse o elemento neutro da multiplicação.  Ou seja, (P i : m <= i < n : expressão(i)) = 1 se n <= m.

Se se pretender desenvolver uma função que calcule o factorial de n (sendo n um parâmetro da função), pode-se começar por escrever o seu cabeçalho bem como a PC e a CO:

// PC: n >= 0
// CO: factorial = n! = (P  i : 1 <= i <= n : i)
int factorial(const int n)
{
    ...
}

4.3.3  Conjunções e o quantificador universal

A conjunção de zero termos tem valor V (verdadeiro), por ser esse o elemento neutro da conjunção.  Ou seja, (Qi : m <= i < n : predicado(i)) = V se n <= m *.

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, é:

primo(n) = (Q i : 2 <= i < n : n ÷ i <> 0), se n >= 2, e
primo(n) = F, se 0 <= n < 2,

primo(n) = ((Q i : 2 <= i < n : n ÷ i <> 0) e n >= 2) para n >= 0

Se se pretender desenvolver uma função (agora em C++) que devolva 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, pode-se começar por escrever o seu cabeçalho bem como a PC e a CO:

// PC: n >= 0
// CO: éPrimo = ((Qi : 2 <= i < n : n ÷ i <> 0) e n >= 2)
bool éPrimo(const int n)
{
    ...
}

* A afirmação "todos os marcianos têm cabeça" é verdadeira, pois não existem marcianos.  Esta propriedade é menos intuitiva que no caso dos quantificadores soma e produto, mas é importante.

4.3.4  Disjunções e o quantificador existencial

A disjunção de zero termos tem valor F (falso), por ser esse o elemento neutro da disjunção.  Ou seja, (Ei : m <= i < n : predicado(i)) = F se n <= m *.

Este quantificador está estreitamente relacionado com o quantificador universal.  É sempre verdade que ¬(Q i : m <= i < n : predicado(i)) = (Ei : m <= i < n : ¬predicado(i)), ou seja, se não é verdade que para qualquer i o predicado predicado(i) é verdadeiro, então existe pelo menos um i para o qual o predicado predicado(i) é falso.  Aplicado à definição de número primo acima, tem-se ¬primo(n) = ¬(Qi : 2 <= i < n : n ÷ i <> 0) = (Ei : 2 <= 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 pretender desenvolver uma função que devolva o valor lógico verdadeiro quando existir um número primo entre m e n exclusivé (sendo m e n parâmetros da função, com m não negativo), e falso no caso contrário, pode-se começar por escrever o seu cabeçalho bem como a PC e a CO:

// PC: m >= 0
// CO: existePrimoNoIntervalo = (E i : m <= i < n : primo(i))
bool existePrimoNoIntervalo(const int m, const int n)
{
    ...
}

* A afirmação "existe pelo menos um marciano com cabeça" é falsa, pois não existem marcianos.

4.3.5  Contagens

Este quantificador é extremamente útil quando é necessário especificar condições em que o número de ordem é fundamental.  Se se pretender desenvolver uma função que devolva o n-ésimo número primo (sendo n parâmetro da função), pode-se começar por escrever o seu cabeçalho bem como a PC e a CO:

// PC: n >= 1
// CO: primo(primo) e (N i : 0 <= i < primo : primo(i)) = n - 1
int primo(const int n)
{
    ...
}

O resto da divisão

* A definição de resto pode ser generalizada para englobar valores negativos de m e n.  Em qualquer dos casos tem de existir um quociente q tal que m = q × n + r.  Mas o intervalo onde r se encontra varia:

0 <= r < n se m >= 0 e n > 0 (neste caso q >= 0)
0 <= r < -n se m >= 0 e n < 0 (neste caso q <= 0)
-n < r <= 0 se m <= 0 e n > 0 (neste caso q <= 0)
n < r <= 0 se m <= 0 e n < 0 (neste caso q >= 0)

4.4  Desenvolvimento de ciclos

Suponha-se que se pretende desenvolver uma função para calcular a potência n de x, isto é, uma função que, sendo x e n os seus dois parâmetros, devolva xⁿ.  A sua estrutura básica é portanto:

double potência(double x, int n)
{
    ...
}

double potência(double x, int n)
{
    int i = 1;    // usada para contar o número de x já incluidos no produto.
    double r = x; // usada para acumular os produtos de x.
    while(i <= n) {
        r *= x;   // o mesmo que r = r * x;
        ++i;      // o mesmo que i = i + 1;
    }
    return r;
}

double potência(double x, int n)
{
    int i = 1;    // usada para contar o número de x já incluidos no produto.
    double r = x; // usada para acumular os produtos de x.
    while(i < n) {
        r *= x;   // o mesmo que r = r * x;
        ++i;      // o mesmo que i = i + 1;
    }
    return r;
}

double potência(double x, int n)
{
    int i = 0;      // usada para contar o número de x já incluidos no produto.
    double r = 1.0; // usada para acumular os produtos de x.
    while(i < n) {
         r *= x;   // o mesmo que r = r * x;
         ++i;      // o mesmo que i = i + 1;
    }
    return r;
}

Os vários problemas que surgiram ao longo desde desenvolvimento atribulado deveram-se a que:

1. O problema não foi bem especificado através da escrita da PC e da CO.  Em particular a PC deveria estabelecer claramente se a função deve saber lidar com expoentes negativos ou não.
2. O desenvolvimento foi feito "ao sabor da pena", duma forma pouco disciplinada.

// PC: n >= 0
// CO: potência = xⁿ
double potência(const double x, const int n)
{
    int i = 0;      // usada para contar o número de x já incluidos no produto.
    double r = 1.0; // usada para acumular os produtos de x.
    while(i < n) {
         r *= x;   // o mesmo que r = r * x;
         ++i;      // o mesmo que i = i + 1;
    }
    return r;
}

Qual das guardas será preferível?  A primeira, que em caso de engano por parte do programador utilizador da função devolve um valor errado, ou a segunda, que nesse caso entra num ciclo infinito, não chegando a terminar?  A verdade é que é preferível a segunda, pois o programador  utilizador mais facilmente se apercebe do erro e o corrige em tempo útil *.  Com a segunda guarda o problema pode só ser detectado demasiado tarde.  Assim, a nova versão da função será:

// PC: n >= 0
// CO: potência = xⁿ
double potência(const double x, const int n)
{
    int i = 0;      // usada para contar o número de x já incluidos no produto.
    double r = 1.0; // usada para acumular os produtos de x.
    while(i != n) {
        r *= x;   // o mesmo que r = r * x;
        ++i;      // o mesmo que i = i + 1;
    }
    return r;
}

É possível certamente desenvolver código C++ "ao sabor da pena", mas é importante que seja desenvolvido correctamente.  Significa isto que, para ciclos mais simples ou conhecidos, o programador desenvolve-os rapidamente, sem grandes preocupações.  Mas para ciclos mais complicados o programador deve ter especial atenção à sua correcção.  Das duas uma, ou os desenvolve primeiro e depois demonstra a sua correcção, ou usa uma metodologia de desenvolvimento que garanta a sua correcção.  As próximas secções lidam com estes dois problemas: o da demonstração de correcção de ciclos e o de metodologias de desenvolvimento de ciclos.  Antes, porém, é fundamental apresentar a noção de invariante um ciclo.

Em alguns casos, porém, a utilização desta metodologia não é prática, uma vez que requer um arsenal considerável de modelos: é o caso de ciclos que envolvam leituras do teclado e/ou escritas no ecrã.  Nesses casos a metodologia continua aplicável, como é óbvio, embora seja vulgar que as asserções sejam escritas com muito menos formalismo.

*  Note-se que na realidade o ciclo não é infinito, pois os int são limitados e incrementações sucessivas levarão o valor do contador ao limite superior dos int.  O que acontece depois depende do compilador, sistema operativo e máquina em que o programa foi compilado e executado.  Normalmente o que acontece é que uma incrementação feita ao contador quando o seu valor já atingiu o limite superior dos int leva o valor a "dar a volta" aos inteiros, passando para o limite inferior dos int.  Incrementações posteriores levarão o contador até zero, pelo que em rigor o ciclo não é infinito...  Mas demora muito tempo a executar, pelo menos, o que mantém a validade do argumento usado para justificar a fraqueza das guardas.

4.4.1  Noção de invariante

// PC: n >= 0
// CO: potência = xⁿ
double potência(const double x, const int n)
{
    int i = 0;      // usada para contar o número de x já incluidos no produto.
    double r = 1.0; // usada para acumular os produtos de x.
ponto 1, depois da inicialização do ciclo, i.e., depois da inicialização das variáveis nele envolvidas.
    while(i != n) {
ponto 2, depois de se verificar que a guarda é verdadeira.
        r *= x;     // o mesmo que r = r * x;
ponto 3, depois de acumular mais uma multiplicação de x em r.
        ++i;      // o mesmo que i = i + 1;
ponto 4, depois de incrementar o contador do número de x já incluidos no produto r.
    }
ponto 5, depois de se verificar que a guarda é falsa, imediatamente antes do retorno.
    return r;
}

É fácil verificar que há uma condição relacionando x, r, n e i que se verifica em todos os pontos do ciclo com excepção do ponto 3.  I.e., que se verifica depois da inicialização, antes do passo, depois do passo, e no final do ciclo.  A relação é r = xⁱ e 0 <= i <= n.  Esta relação diz algo razoavelmente óbvio: em cada instante (excepto no ponto 3) o acumulador possui a potência i do valor em x, tendo i um valor entre 0 e n.  Esta condição, por ser verdadeira ao longo de todo o ciclo (excepto a meio do passo, no ponto 3), diz-se uma "invariante" do ciclo.

As condições invariantes são centrais na demonstração da correcção de ciclos e durante o desenvolvimento disciplinado de ciclos, como se verá nas próximas secções.

Em geral, para um ciclo da forma

inic
while(G)
    passo

1. for verdadeira logo após a inicialização do ciclo (inic);
2. for verdadeira imediatamente antes do passo (passo);
3. for verdadeira imediatamente após o passo; e
4. for verdadeira depois de terminado o ciclo.

Note-se que se incluiram asserções adicionais.  Antes da inicialização assume-se que a pré-condição (PC) do ciclo se verifica, e no final do ciclo pretende-se que se verifique a sua condição objectivo (CO).  Além disso, depois da decisão do ciclo, em que se verifica a veracidade da guarda, sabe-se que a guarda (G) é verdadeira antes de executar o passo e falsa (ou seja, verdadeira a sua negação ¬G) depois de terminado o ciclo.  Ou seja, antes do passo sabe-se que CI e G é uma asserção verdadeira e no final do ciclo sabe-se que CI e ¬G é também uma asserção verdadeira.

Note-se que, no caso da função potência(), a condição objectivo do ciclo é diferente da condição objectivo da função, pois refere-se à variável r, que será posteriormente devolvida pela função.  I.e.:

// PC: n >= 0
// CO: potência = xⁿ
double potência(const double x, const int n)
{
    // PC: n >= 0
    int i = 0;      // usada para contar o número de x já incluidos no produto.
    double r = 1.0; // usada para acumular os produtos de x.
    while(i != n) {
        r *= x;   // o mesmo que r = r * x;
        ++i;      // o mesmo que i = i + 1;
    }
    // CO': r = xⁿ
    return r;
}

Demonstração de invariância

Para que a asserção CI possa ser invariante tem de ser verdadeira depois da inicialização (ver fluxograma).  I.e., assumindo que a PC do ciclo se verifica, então a inicialização inic tem de conduzir forçosamente à veracidade da asserção CI.  É necessário portanto demonstrar que:

// PC
inic
// implica CI

// PC: n >= 0
int i = 0;
double r = 1.0;
// CI: r = xⁱe 0 <= i <= n

CI: 1,0 = x⁰ e 0 <= 0 <= n, ou seja
CI: 1,0 = 1,0 e 0 <= 0 e 0 <= n, ou seja
CI: V e V e 0 <= n, ou seja
CI: 0 <= n, que é garantidamente verdadeira dada a PC, ou seja
CI: V

// CI e G
passo
// implica CI

Para o caso dado, é necessário demonstrar que:

// CI e G: r = xⁱ e 0 <= i <= n ei <> n, ou seja, simplificando
// r = xⁱ e 0 <= i < n
r *= x;   // o mesmo que r = r * x;
++i;      // o mesmo que i = i + 1;
// CI: r = xⁱe 0 <= i <= n

// r = xⁱ⁺¹e 0 <= i + 1 <= n, ou seja
// r = xⁱ × xe -1 <= i <= n - 1, ou seja
// r = xⁱ × xe -1 <= i < n
++i;      // o mesmo que i = i + 1;
// CI: r = xⁱe 0 <= i <= n

r = xⁱ × x e -1 <= i < n

// r × x = xⁱ × x e -1 <= i < n, ou seja, eliminando x de ambos os lados da igualdade,
// r = xⁱ e -1 <= i < n
r *= x;   // o mesmo que r = r * x;
// r = xⁱ × xe -1 <= i < n

CI e G: r = xⁱe 0 <= i < n
implica r = xⁱ e -1 <= i < n

Em resumo, para provar a invariância de uma asserção CI é necessário:

1. Mostrar que, admitindo a veracidade da PC antes da inicialização, a asserção CI é verdadeira depois da inicialização inic.  Ou seja:
// PC
inic
// implica CI
2. Mostrar que, se CI for verdadeira no início do passo numa qualquer iteração do ciclo, então também o será depois do passo nessa mesma iteração.  Ou seja:
// CI e G
passo
// implica CI
sendo a demonstração feita, comummente, do fim para o princípio, deduzindo as pré-condições mais fracas de cada instrução do passo.

4.4.2  Correcção de ciclos

Correcção parcial

CI e ¬G implica CO

CI e ¬G: r = xⁱe 0 <= i <= n e i = n é o mesmo que
r = xⁱ e i = n , ou seja
r = xⁿ e i = n , que implica naturalmente
CO': r = xⁿ

1. encontrar uma asserção CI apropriada (note-se que a asserção V é trivialmente invariante de qualquer ciclo e não ajuda nada na demonstração de correcção parcial: é necessário que a CI seja rica em informação);
2. demonstrar que essa asserção CI é de facto uma invariante do ciclo (ver Secção anterior); e
3. demonstrar que CI e ¬G implica CO.

Correcção total

// PC: n >= 0
// CO: potência = xⁿ
double potência(const double x, const int n)
{
    // PC: n >= 0
    int i = 0;
    double r = 1.0;
    while(i != n)
        ; // instrução vazia!
    // CO': r = xⁿ
    return r;
}

A demonstração formal de terminação de um ciclo ao fim de um número finito de iterações faz-se usando o conceito de "função de limitação" (bound functions) [4], que não será abordado neste texto.  Neste contexto será suficiente a demonstração informal desse facto.  Por exemplo, na versão original da função potência()

// PC: n >= 0
// CO: potência = xⁿ
double potência(const double x, const int n)
{
    // PC: n >= 0
    int i = 0;      // usada para contar o número de x já incluidos no produto.
    double r = 1.0; // usada para acumular os produtos de x.
    while(i != n) {
        r *= x;   // o mesmo que r = r * x;
        ++i;      // o mesmo que i = i + 1;
    }
    // CO': r = xⁿ
    return r;
}

O passo é, tipicamente, dividido em duas partes: a acção e o progresso.  I.e., os ciclos têm tipicamente a seguinte forma:

inic
while(G) {
    acção
    prog
}

No caso do ciclo da função potência() a acção e o progresso são:

r *= x;   // acção
++i;      // prog

Resumo

// PC
inic
while(G) {
    acção
    prog
}
// CO

1. encontrar uma asserção CI apropriada (note-se que a asserção V é trivialmente invariante de qualquer ciclo e não ajuda nada na demonstração de correcção parcial: é necessário que a CI seja rica em informação);
2. demonstrar que essa asserção CI é de facto uma invariante do ciclo:
1. mostrar que, admitindo a veracidade da PC antes da inicialização, a asserção CI é verdadeira depois da inicialização inic, ou seja:
// PC
inic
// implica CI; e
2. mostrar que, se CI for verdadeira no início do passo numa qualquer iteração do ciclo, então também o será depois do passo nessa mesma iteração, ou seja:
// CI e G
passo
// implica CI;
3. demonstrar que CI e ¬G implica CO; e
4. demonstrar que o ciclo termina sempre ao fim de um número finito de iterações, para o que se raciocina normalmente em termos da inicialização inic, da guarda G e do progresso prog.

4.4.3  Melhorando a função potência()

// PC: n >= 0 oux <> 0
// CO: potência = xⁿ
double potência(const double x, const int n)
{
    ...
}

// PC: n >= 0 oux <> 0
// CO: potência = xⁿ
double potência(const double x, const int n)
{
    const int exp = n < 0 ? -n : n;
    int i = 0;      // usada para contar o número de x já incluidos no produto.
    double r = 1.0; // usada para acumular os produtos de x.
    while(i != exp) {
        r *= x;   // o mesmo que r = r * x;
        ++i;      // o mesmo que i = i + 1;
    }
    return n < 0 ? 1.0 / r : r;
}

// PC: n >= 0 oux <> 0
// CO: potência = xⁿ
double potência(const double x, const int n)
{
    const int exp = n < 0 ? -n : n;
    double r = 1.0;
    for(int i = 0; i != exp; ++i)
        r *= x;   // o mesmo que r = r * x;
    return n < 0 ? 1.0 / r : r;
}

4.4.4  Metodologia de Dijkstra

1. Especificar o problema sem margem para ambiguidades: definir a PC e a CO.
2. Tentar perceber se um ciclo é, de facto, necessário.  Este passo é muitas vezes descurado, com consequências infelizes, como se verá.
3. Olhando para a CO, determinar uma CI para o ciclo.  A CI escolhida é uma versão enfraquecida da guarda.
4. Escolher uma guarda G tal que CI e ¬G implica CO.
5. Escolher uma inicialização inic de modo a garantir a veracidade da CI logo no início do ciclo, assumindo portanto que a sua PC se verifica.
6. Escolher o passo do ciclo de modo a que a CI se mantenha verdadeira (i.e., de modo a garantir que é de facto invariante).  É muito importante que a escolha do passo garanta a terminação do ciclo: o passo é usualmente dividido num progresso prog e numa acção acção, sendo o progresso que garante a terminação do ciclo e a acção que garante que, apesar do progresso, a CI se mantém válida.

Definição da pré-condição e da condição objectivo

A definição destas condições, no caso de uma função ou procedimento, funciona como um contrato com o programador utilizador da função ou procedimento: "se o programador utilizador desta função (procedimento) respeitar a PC, o programador fabricante desta função (procedimento) garante que depois de executada(o) a CO é verdadeira".

Se se pretender escrever uma função int somaQuadrados(const int n) que some os quadrados dos primeiros n inteiros não-negativos, então a estrutura da função, com a PC e a CO, poderá ser:

// PC: n >= 0
// CO: somaQuadrados = (S k : 0 <= k < n : k²)
int somaQuadrados(const int n)
{
    int resultado = ???;

    // CO': somaQuadrados = (S k : 0 <= k < n : k²)
    return resultado;
}

Se se pretender escrever uma função int raiz(const int x) que, assumindo que x é não-negativo, devolva o maior inteiro menor ou igual à raiz quadrada de x, então a estrutura da função, com a PC e a CO, poderá ser:

// PC: x >= 0
// CO: 0 <= raizInteira <= x^½ < raizInteira + 1, ou seja,
// 0 <= raizInteiraeraizInteira² <= x < (raizInteira + 1)²
int raizInteira(const int x)
{
    int r = ???;

    // CO': 0 <=r e r² <= x < (r + 1)²
    return r;
}

(Determinando se um ciclo é necessário

Determinação da condição invariante e da guarda

Por enfraquecimento entende-se a obtenção de uma condição invariante CI tal que, de entre todas as combinações de valores das variáveis que a tornam verdadeira, contenha todas as combinações de valores de variáveis que tornam verdadeira a CO.  Ou seja, o conjunto dos estados do programa que verificam a CI deve conter o conjunto dos estados do programa que verificam a CO.  Ou ainda, CO implica CI.

Apresentar-se-ão aqui apenas dois dos vários possíveis métodos para obter a CI por enfraquecimento da CO:

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.  A negação da guarda ¬G é depois escolhida de modo a que CI e ¬G impliqueCO, o que normalmente é conseguido escolhendo para ¬G o predicado que afirma que a variável introduzida tem exactamente o valor da constante que substituiu.
2. Se a CO corresponde à conjunção de várias proposições, escolher parte delas para a CI e outra parte para a negação da guarda ¬G.  Por exemplo, se CO: C₀ e C₁ eC_m-1, então poder-se-ia escolher CI: C₀eC₁e ... C_m-2 e ¬G: C_m-1, por exemplo.  A este método chama-se factorização da CO.

Substituição de uma constante por uma variável

Voltando à função somaQuadrados(), é evidente que o corpo da função pode consistir num ciclo cuja condição objectivo já foi apresentada:

CO': resultado = (S k: 0 <= k < n : k²).

CI: resultado = (S k: 0 <= k < i : k²) e 0 <= i <= n.

Em rigor, a escolha feita para CI não corresponde ao simples enfraquecimento da CO'.  Na verdade, a introdução de uma nova variável é feita em duas etapas, que normalmente se omitem.  O primeiro passo obriga a uma reformulação da CO' de modo a reflectir a existência da nova variável.  Substitui-se a constante pela nova variável, mas força-se também a nova variável a tomar o valor da constante que substituiu, acrescentando para tal uma conjunção à CO'

CO'': resultado = (S k: 0 <= k < i : k²) ei = n,

A CI é obtida da nova CO'' por enfraquecimento do termo que fixa o valor da variável i, que na CI é deixada mais "livre" que na CO''.  A CI obtida é de facto mais fraca que a CO'', pois aceita mais possíveis valores para a variável resultado do que a CO'', que só aceita o resultado final pretendido.  Os valores aceites para essa variável pela CI correspondem a valores intermédios durante o cálculo.  Neste caso correspondem a todas as possíveis somas de quadrados de inteiros positivos: desde a soma com zero termos até à soma com os n termos pretendidos.

A escolha da guarda também é simples.  Basta escolher para negação da guarda ¬G a conjunção que se acrescentou à CO' para se obter a CO''.  Dessa forma tem-se forçosamente que (CI e ¬G)equivaleCO''implica CO', como pretendido.

A escolha da G pode também ser feita observando que no final do ciclo a guarda será forçosamente falsa e a CI verdadeira (i.e., que CI e ¬G), e que pretende, nessa altura, que a CO' do ciclo seja verdadeira.  Ou seja, sabe-se que no final do ciclo

resultado = (S k: 0 <= k < i: k²) e 0 <= i <= n e ¬G

CO': resultado = (S k: 0 <= k < n : k²).

¬G: i = n,
ou seja,
G: i <> n

Factorização da condição objectivo

Voltando à função raiz(), é evidente que o corpo da função pode consistir num ciclo cuja condição objectivo já foi apresentada:

CO': 0 <= rer² <= x < (r + 1)²,

CO': 0 <= rer² <= xe x < (r + 1)².

G: (r + 1)² <= x,

CI: 0 <= rer² <= x.

Esta escolha de CI corresponde, mais uma vez, a enfraquecer a CO', pois a CI aceita mais possíveis valores para a variável r do que a CO', que só aceita o resultado final pretendido.

Escolha da inicialização

Função somaQuadrados()

CI: resultado = (S k: 0 <= k < i : k²) e 0 <= i <= n,

int resultado = 0;
int i = 0;

0 = (S k: 0 <= k < 0 : k²) e 0 <= 0 <= n,

Função raiz()

CI: 0 <= rer² <= x,

int r = 0;

0 <= 0 e 0 <= x,

Determinação do passo: progresso e acção

Função somaQuadrados()

G: i <> n

// CI eG: resultado = (S k : 0 <= k < i : k²) e 0 <= i <= ne i <> n,
// ou seja,
// resultado = (Sk : 0 <= k < i : k²) e 0 <= i < n
acção
++i; // i = i + 1;
// CI: resultado = (S k : 0 <= k < i : k²) e 0 <= i <= n

// resultado = (S k : 0 <= k < i + 1 : k²) e 0 <= i + 1 <= n,
// ou seja, extraíndo o último termo do somatório,
// resultado = (Sk : 0 <= k < i : k²) + i²e -1 <= i < n,
++i; // i = i + 1;
// CI: resultado = (S k : 0 <= k < i : k²) e 0 <= i <= n

// resultado = (S k : 0 <= k < i : k²) e 0 <= i < n
acção
// resultado = (Sk : 0 <= k < i : k²) + i²e -1 <= i < n

resultado += i * i;

// PC: n >= 0
// CO: somaQuadrados = (S k : 0 <= k < n : k²)
int somaQuadrados(const int n)
{
    int resultado = 0;
    int i = 0;

    // CI: resultado = (S k : 0 <= k < i : k²) e 0 <= i <= n
    while(i != n) {
        resultado += i * i;
        ++i;
    }

    return resultado;
}

// PC: n >= 0
// CO: somaQuadrados = (S k : 0 <= k < n : k²)
int somaQuadrados(const int n)
{
    int resultado = 0;

    // CI: resultado = (S k : 0 <= k < i : k²) e 0 <= i <= n
    for(int i = 0; i != n; ++i)
        resultado += i * i;

    return resultado;
}

Função raiz()

G: (r + 1)² <= x,

// CI eG: 0 <= r e r² <= xe (r + 1)² <= x,
acção
++r; // r = r + 1;
// CI: 0 <= rer² <= x

// CI eG: 0 <= r e r² <= xe (r + 1)² <= x,
acção
// 0 <= r + 1 e (r + 1)² <= x, ou seja,
// -1 <= re (r + 1)² <= x
++r; // r = r + 1;
// CI: 0 <= rer² <= x

// PC: x >= 0
// CO: 0 <= raizInteira <= x^½ < raizInteira + 1
int raizInteira(const int x)
{
    int r = 0;

    // CI: 0 <= r e r² <= x
    while((r + 1) * (r + 1) <= x)
        ++r;

    return r;
}