Resolução dos Exercícios da Aula 8

Exercícios

Em todos os exercícios, depois de desenvolvido o ciclo correspondente, tente determinar a CI correspondente.

1.  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 o lado do quadrado: 4

****
*  *
*  *
****

É necessário que o procedimento se comporte razoavelmente mesmo para alturas de 1 e 2 asteriscos.

R:

#include <iostream>

using namespace std;

// PC: n >= 0
void escreveQuadradoOcoDeAsteriscos(const int n)
{
    // CI: já foram escritas linha linhas do quadrado.
    for(int linha = 0; linha != n; ++linha) {
        // CI: já foram escritas coluna colunas da linha linha do quadrado.
        for(int coluna = 0; coluna != n; ++coluna)
            if(linha == 0 || linha == n - 1 ||
               coluna == 0 || coluna == n - 1)
                cout << '*';
            else
                cout << ' ';
        cout << endl;
    }
}

int main()
{
    cout << "Introduza um inteiro não-negativo: ";
    int n;
    cin >> n;

    for(int i = 0; i != n + 1; ++i) {
        cout << "Quadrado oco com " << i << " asteriscos de altura:"
             << endl;
        escreveQuadradoOcoDeAsteriscos(i);
    }
}

2.  Desenvolva um programa que calcule e mostre o máximo de um conjunto de n números introduzidos pelo utilizador (o valor n também é introduzido pelo utilizador e assume-se positivo).

R:

#include <iostream>

using namespace std;

int main()
{
    cout << "Introduza um inteiro positivo: ";
    int n;
    cin >> n;

    // PC: n > 0
    int máximo;
    cin >> máximo;
    // CI: foram lidos i números e máximo é o maior deles.
    for(int i = 1; i != n; ++i) {
        int v;
        cin >> v;
        if(v > máximo)
            máximo = v;
    }
    cout << "O maior foi " << máximo << '.' << endl;
}

3.  Considere a seguinte função:
f(x) = (x + 2)½ se x >= -2
f(x) = x2 + 1 se x < -2
Desenvolva um programa que construa uma tabela dos valores da função para valores de x de a a b com saltos de h (todos dados pelo utilizador).  Utilize a função sqrt() para o cálculo da raíz quadrada (deve acrescentar #include <cmath> no início do programa).

R:

#include <iostream>
#include <cmath>

using namespace std;

double f(double x)
{
    if(x >= -2)
        return sqrt(x + 2.0);
    else
        return x * x + 1;
}

void troca(double& a, double& b)
{
    double t = a;
    a = b;
    b = t;
}

int main()
{
    cout << "Introduza os limites e o salto (se disser zero ponho 1...): ";
    double a, b, h;
    cin >> a >> b >> h;

    if(a > b)
        troca(a, b);
    if(h < 0.0)
        h = -h;
    else if(h == 0.0)
        h = 1.0;

    // CI: Tabelados todos os valores de a a x (exclusive) de h em h.
    for(double x = a; x <= b; x += h)
        cout << "f(" << x << ") = " << f(x) << endl;
}

4.  Utilize a metodologia de Dijkstra para desenvolver uma função que verifique se existe algum múltiplo de k nos inteiros entre m e n.  Assuma que n >= m >= 0 e que k > 0.

R:
Primeiro passo: escrever o esqueleto da função incluindo a PC e a CO.

// PC: k > 0 e n >= m >= 0
// CO: háMúltiploEntre = (E j : m <= j <= n : j ÷ k = 0)
bool háMúltiploEntre(const int k, const int m, const int n)
{
    bool há;
    ...
    // CO': há = (E j : m <= j <= n : j ÷ k = 0)
    return há;
}
O passo seguinte passa por identificar a necessidade de um ciclo.  Neste caso assume-se que um ciclo é necessário (mas ver próxima resposta).

Em seguida enfraquece-se a CO' de modo a obter a CI.  Neste caso pode-se simplesmente substituir o limite superior do quantificador (constante n) por uma nova variável C++ i introduzida para o efeito:

CI: há = (Ej : m <= j <= i : j ÷ k = 0) e m <= i <= n
Como guarda escolhe-se simplesmente i <> n, de modo a que CI e ¬G implicaCO.

O passo seguinte é escolher a inicialização do ciclo.  A forma mais simples de verificar a CI é fazendo:

há = false;
i = m - 1;
pois dessa forma o quantificador tem zero termos e portanto valor F.

Em seguida há que escolher o progresso.  Neste caso pode-se optar pela simples incrementação de i:

++i;
Falta escolher uma acção que garanta a invariância da CI apesar do progresso.  O passo pode-se escrever:
// Aqui assume-se que CI e G, ou seja, há = (Ej : m <= j <= i : j ÷ k = 0) e m <= i <= n ei <> n ou ainda,
// há = (Ej : m <= j <= i : j ÷ k = 0) e m <= i < n
acção
++i;
// Aqui pretende-se que CI seja verdadeira, ou seja, há = (E j : m <= j <= i : j ÷ k = 0) em <= i <= n
Partindo dos objectivos, podemos obter a condição mais fraca a impor antes do progresso para que depois dele a CI seja verdadeira.  Para isso substitui-se i por i + 1:
// há = (E j : m <= j <= i + 1 : j ÷ k = 0) e m <= i + 1 <= n, ou seja,
// há = ((Ej : m <= j <= i : j ÷ k = 0) ou (i + 1) ÷ k = 0) em - 1 <= i <= n - 1, ou seja,
// há = ((Ej : m <= j <= i : j ÷ k = 0) ou (i + 1) ÷ k = 0) em - 1 <= i < n.
++i;
// há = (Ej : m <= j <= i : j ÷ k = 0) e m <= i <= n
Agora há que escolher a acção de modo a que
// há = (E j : m <= j <= i : j ÷ k = 0) e m <= i < n
acção
// implica há = ((E j : m <= j <= i : j ÷ k = 0) ou (i + 1) ÷ k = 0) e m - 1 <= i < n.
É claro que o valor de i não necessita de ser afectado pela acção.  Mas o de há sim.  Em particular a variável há tem de passar a conter o valor que tinha antes da acção disjunto com (i + 1) ÷ k = 0.  Ou seja, a acção será:
há = há || (i + 1) % k == 0;
Pode-se verificar que é uma boa escolha obtendo a condição mais fraca a impor antes da acção.  Para isso substitui-se há por há ou (i + 1) ÷ k = 0:
// (háou (i + 1) ÷ k = 0) = ((E j : m <= j <= i : j ÷ k = 0) ou (i + 1) ÷ k = 0) e m - 1 <= i < n, ou seja
// há = (Ej : m <= j <= i : j ÷ k = 0) e m - 1 <= i < n.
há = há || (i + 1) % k == 0;
// há = ((Ej : m <= j <= i : j ÷ k = 0) ou (i + 1) ÷ k = 0) em - 1 <= i < n.
Como
// há = (E j : m <= j <= i : j ÷ k = 0) e m <= i < n
// implica há = (E j : m <= j <= i : j ÷ k = 0) e m - 1 <= i < n.
a invariância fica demonstrada.

Finalmente a demonstração de que o ciclo termina, i.e., que o ciclo está não só parcilmente correcto mas totalmente correcto, pode ser feita notando que i começa em m - 1 e é incrementado a cada passo, e portanto atingirá n ao fim de um número finito de passos (exactamente n - m + 1, recorde-se que a PC garante que n >= m).

A função completa fica então:

// PC: k > 0 e n >= m >= 0
// CO: háMúltiploEntre = (E j : m <= j <= n : j ÷ k = 0)
bool háMúltiploEntre(const int k, const int m, const int n)
{
    bool há = false;
    for(int i = m - 1; i != n; ++i)
        há = há || (i + 1) % k == 0;
    return há;
}
Uma simples mudança de variável permite-nos atrasar o valor de i de uma unidade:
// PC: k > 0 e n >= m >= 0
// CO: háMúltiploEntre = (E j : m <= j <= n : j ÷ k = 0)
bool háMúltiploEntre(const int k, const int m, const int n)
{
    bool há = false;
    for(int i = m; i != n + 1; ++i)
        há = há || i % k == 0;
    return há;
}
É óbvio que se alguma vez o valor de há se tornar V, nunca mais o deixará de ser, pelo que o ciclo pode ser abreviado, reforçando a guarda (a demonstração formal de que o ciclo continua correcto deixa-se a cargo do leitor).  Ou seja:
// PC: k > 0 e n >= m >= 0
// CO: háMúltiploEntre = (E j : m <= j <= n : j ÷ k = 0)
bool háMúltiploEntre(const int k, const int m, const int n)
{
    bool há = false;
    for(int i = m; !há && i != n + 1; ++i)
        há = há || i % k == 0;
    return há;
}
Esta versão pode ser simplificada observando que no início do passo, com esta guarda reforçada, a variável há toma sempre o valor F, pelo que a acção pode ser simplificada:
// PC: k > 0 e n >= m >= 0
// CO: háMúltiploEntre = (E j : m <= j <= n : j ÷ k = 0)
bool háMúltiploEntre(const int k, const int m, const int n)
{
    bool há = false;
    for(int i = m; !há && i != n + 1; ++i)
        há = i % k == 0;
    return há;
}
Finalmente, uma solução alternativa passa pelo terminar abrupto da função se se encontrar um múltiplo:
// PC: k > 0 e n >= m >= 0
// CO: háMúltiploEntre = (E j : m <= j <= n : j ÷ k = 0)
bool háMúltiploEntre(const int k, const int m, const int n)
{
    for(int i = m; i != n + 1; ++i)
        if(i % k == 0)
            return true;
    return false;
}
Haverá alguma forma mais simples de resolver este problema, sem que seja necessário recorrer a nenhum ciclo?

R:
Sim!  Basta que m ÷ k = 0 ou m / k <> n / k.  Ou seja, a função pode ser escrita como:

// PC: k > 0 e n >= m >= 0
// CO: háMúltiploEntre = (E j : m <= j <= n : j ÷ k = 0)
bool háMúltiploEntre(const int k, const int m, const int n)
{
    return m % k == 0 || m / k != n / k;
}
Um programa de teste seria
#include <iostream>

using namespace std;

// PC: k > 0 e n >= m >= 0
// CO: háMúltiploEntre = (E j : m <= j <= n : j ÷ k = 0)
bool háMúltiploEntre(const int k, const int m, const int n)
{
    for(int i = m; i != n + 1; ++i)
        if(i % k == 0)
            return true;
    return false;
}

// PC: k > 0 e n >= m >= 0
// CO: háMúltiploEntre = (E j : m <= j <= n : j ÷ k = 0)
bool háMúltiploEntreMelhor(const int k, const int m, const int n)
{
    return m % k == 0 || m / k != n / k;
}

void troca(int& a, int& b)
{
    int t = a;
    a = b;
    b = t;
}

int main()
{
    cout << "Introduza o valor (se disser zero ponho 1...) "
         << "e os dois limites:";
    int k, m, n;
    cin >> k >> m >> n;

    if(m > n)
        troca(m, n);
    if(k < 0)
        k = -k;
    else if(k == 0.0)
        k = 1;

    if(háMúltiploEntre(k, m, n))
        cout << "Há múltiplo." << endl;
    else
        cout << "Não há múltiplo." << endl;

    if(háMúltiploEntreMelhor(k, m, n))
        cout << "Há múltiplo." << endl;
    else
        cout << "Não há múltiplo." << endl;
}

5.a)  Desenvolva 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 inteiro não negativo que apenas é divisível por 1 e por si mesmo (excepto o inteiro 1, que se considera não-primo).  Demonstre a correcção do ciclo desenvolvido.

R:

#include <iostream>

using namespace std;

// PC: n >= 0
// CO: éPrimo = ((Q j : 2 <= j < n: n ÷ j <> 0) e n >= 2)
bool éPrimo(int n)
{
    if(n <= 1)
        return false;
    for(int i = 2; i * i <= n; ++i)
        if(n % i == 0)
            return false;
    return true;
}

int main()
{
    cout << "Introduza um inteiro não-negativo:" << endl;
    int n;
    cin >> n;

    for(int i = 0; i != n + 1; ++i)
        if(éPrimo(i))
            cout << i << endl;
}

A função começa por um instrução de retorno condicional que lida com os casos particulares que são os inteiros 0 e 1 (considerados não primos por convenção).  Após essa instrução é óbvio que n >= 2, pelo que se pode comentar o ciclo com as suas próprias PC' e CO':
// PC': n >= 2
for(int i = 2; i * i <= n; ++i)
    if(n % i == 0)
        return false;
return true;
// CO': éPrimo = (Q j : 2 <= j < n: n ÷ j <> 0)
Primeiro há que observar que se um determinado j for divisor de n, então existe um k tal que j × k = n.  Suponha-se que j é tal que j × j > n, ou seja, j > n½.  Então, como k = n / j, tem-se que k × k = (n × n) / (j × j) < n, ou seja, k < n½.  Portanto, se existir um j > n½ tal que n ÷ j = 0, então também existe um k  < n½ tal que n ÷ k = 0.  Isto significa que, para que n >= 2 seja primo, basta que não seja divisível por nenhum inteiro j >= 2 e j <= n½, não sendo necessário verificar os inteiros entre n½ exclusive e n exclusive.  Ou seja, a CO' pode ser reescrita como:
CO': éPrimo = (Q j : 2 <= j <= n½: n ÷ j <> 0)
Note-se que a expressão n½ não toma forçosamente valores inteiros.  Qual será, pois, o maior valor que j pode tomar para verificar 2 <= j <= n½?  Qual o maior inteiro k tal que k <= n½?  É o valor de k tal que k <= n½ e k + 1 > n½, ou seja n½ - 1 < k <= n½.  Existe apenas um k nestas circunstâncias, e é o inteiro que se obtém truncando a parte decimal de n½.  A CO' pode ser reescrita em termos da constante k:
CO': éPrimo = (Q j : 2 <= j <= k: n ÷ j <> 0)
que, como a variável j toma valores inteiros, pode ser reescrita como
CO': éPrimo = (Q j : 2 <= j e j < k + 1 : n ÷ j <> 0)
A CI do ciclo aparenta ser, embora seja necessário demonstrá-lo.
CI: (Q j : 2 <= jej < i: n ÷ j <> 0) e 2 <= i <= k + 1
Uma vez que a função termina sempre numa de duas possíveis instruções de retorno, é conveniente verificar que condições têm de se impor antes dessas instruções para que levem à condição objectivo.  Para a primeira instrução de retorno (no passo do ciclo) a pré-condição mais fraca é:
// F = (Qj : 2 <= j < k + 1 : n ÷ j <> 0), ou seja,
// (E j : 2 <= j < k + 1 : n ÷ j = 0)
return false;
// CO': éPrimo = (Q j : 2 <= j < k + 1 : n ÷ j <> 0)
Para a segunda instrução de retorno, no final do ciclo, a pré-condição mais fraca é:
// V = (Qj : 2 <= j < k + 1 : n ÷ j <> 0), ou seja,
// (Q j : 2 <= j < k + 1 : n ÷ j <> 0)
return true;
// CO': éPrimo = (Q j : 2 <= j < k + 1 : n ÷ j <> 0)
A guarda do ciclo é G: i × i <= n, que é o mesmo que i <= n½, pelo que quando o ciclo termina normalmente (i.e., sem retornar durante o passo) tem-se:
CI e  ¬G: (Q j : 2 <= j e j < i: n ÷ j <> 0) e 2 <= i <= k + 1 e i > n½
ou seja
(Q j : 2 <= jej < i: n ÷ j <> 0) en½ < i <= k + 1
Como k <= n½, conclui-se que
(Q j : 2 <= jej < i: n ÷ j <> 0) ek < i <= k + 1
e portanto
(Q j : 2 <= jej < i: n ÷ j <> 0) ei = k + 1
que por sua vez implica que a pré-condição mais fraca da instrução de retorno se verifica.  Assim, se o ciclo terminar pelos seus meios normais (i.e., por a guarda se tornar falsa) a função devolve o valor correcto.  Intuitivamente, se o ciclo não pára a meio, então não se encontraram divisores para n e portanto n é um número primo.

Dentro do ciclo, e imediatamente antes do passo, tem-se:

CI e G: (Qj : 2 <= j e j < i: n ÷ j <> 0) e 2 <= i <= k + 1 ei <= n½
De n½ - 1 < k <= n½ tira-se que n½  < k + 1 <= n½ + 1, pelo que se conclui que i < k + 1, ou seja,
CI e G: (Qj : 2 <= j e j < i: n ÷ j <> 0) e 2 <= i < k + 1
Para que a CI seja de facto invariante, tem de ser verdadeira também depois do passo, ou seja:
// Aqui assume-se que CI e G: (Q j : 2 <= jej < i: n ÷ j <> 0) e 2 <= i < k + 1
if(n % i == 0)
    return false;
++i;
// Aqui pretende-se que CI: (Q j : 2 <= j e j < i: n ÷ j <> 0) e 2 <= i <= k + 1
Partindo dos objectivos, pode-se determinar qual a pré-condição mais fraca antes do progresso:
// (Q j : 2 <= j e j < i + 1 : n ÷ j <> 0) e 2 <= i + 1 <= k + 1, ou seja,
// (Q j : 2 <= j e j < i : n ÷ j <> 0) e n ÷ i <> 0 e 1 <= i < k + 1, ou seja,
++i;
// Aqui pretende-se que CI: (Q j : 2 <= j e j < i: n ÷ j <> 0) e 2 <= i <= k + 1
Assim, é claro que o progresso mantém a veracidade da CI desde que n ÷ i <> 0.  Caso n ÷ i = 0, como se sabe que (Qj : 2 <= j e j < i: n ÷ j <> 0) e 2 <= i < k + 1, conclui-se que (E j : 2 <= j < k + 1 : n ÷ j = 0).  Logo, a acção do ciclo leva à invariância da CI, se o ciclo continuar, ou ao terminar abrupto da função atingindo-se a CO.

Falta verificar que a CI é verdadeira depois da inicialização.  A inicialização limita-se a atribuir dois a i, pelo que a CI fica

(Q j : 2 <= jej < 2: n ÷ j <> 0) e 2 <= 2 <= k + 1
O quantificador universal, sem qualquer termo, toma o valor V, pelo que resta verificar se k + 1 >= 2.  Acontece que n½  < k + 1 <= n½ + 1, pelo que, como pela PC' n  >= 2, então n½ >= 2½ > 1.  Logo, k + 1 > 1 ou, o que é o mesmo, visto que k pertence aos inteiros, k + 1 >= 2.

O ciclo está, pois parcialmente correcto.  A correcção total pode ser demonstrada usando os argumentos usuais: o progresso do ciclo incrementa i, pelo que i crescerá fatalmente até atingir um valor tal que i > n½, se o ciclo não terminar antes devido a um retorno antecipado da função.  Assim, o ciclo termina sempre ao fim de um número finito de passos, e portanto está totalmente correcto.

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

R:
Ver alínea anterior.

6.  Desenvolva uma função que permita ao utilizador inserir caracteres sucessivos, terminando com o caractere '!', 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 (termine com '!'):
qwe*98*8wer*we112rwq!
Contei 3 asteriscos.
R:
#include <iostream>

using namespace std;

int main()
{
    cout << "Introduza um conjunto de caracteres (termine com '!'):"
         << endl;
    int n = 0;
    char c;
    // CI: n é o número de asteriscos nos caracteres já lidos.
    while(cin.get(c) && c != '!')
        if(c == '*')
            ++n;
    cout << "Contei " << n << " asterisco" << (n == 1 ? "" : "s") << '.'
         << endl;
}