Aula 7

Resolução dos exercícios

Versão recursiva do factorial

Como n! = n (n - 1)!, e n! = 1 quando n = 0, a resolução é simplesmente:
// PC: n >= 0
// CO: devolve n!
int factorial(int n)
{
    if(n == 0)
        return 1;
    return n * factorial(n - 1);
}

Versão iterativa do factorial

Usando a metodologia usual:
// PC: n >= 0
// CO: f = (P k : 0 < k <= n : k)
// ou, o que é o mesmo
// CO: f = (P k : 1 <= k < n + 1 : k)
int factorial(int n)
{
    int f = 1;
    // CI: f = (P k : 0 < k <= i : k) e 1 <= i <= n + 1
    for(int i = 1; i != n + 1; i++)
        f *= i;
    return f;
}
ou, usando a mesma metodologia mas substituindo o limite inferior do produto,
// PC: n >= 0
// CO: f = (P k : 0 < k <= n : k)
int factorial(int n)
{
    int f = 1;
    // CI: f = (P k : i < k <= n : k) e 0 <= i <= n
    for(int i = n; i != 0; i--)
        f *= i;
    return f;
}
que se pode reescrever como
// PC: n >= 0 e n = n
// CO: f = (P k : 0 < k <= n : k)
int factorial(int n)
{
    int f = 1;
    // CI: f = (P k : n < k <= n : k) e 0 <= n <= n
    while(n != 0) {
        f *= n;
        n--;
    }
    return f;
}
reconhecendo que a variável n pode mudar de valor ao longo da função, uma vez que é um parâmetros passado por valor e não por referência.

Usando as características do operador de decrementação do C++, pode-se ainda escrever

// PC: n >= 0 e n = n
// CO: f = (P k : 0 < k <= n : k)
int factorial(int n)
{
    int f = 1;
    // CI: f = (P k : n < k <= n : k) e 0 <= n <= n
    while(n != 0)
        f *= n--;
    return f;
}
que é a forma mais típica de escrever este tipo de ciclos em C++ (embora talvez não seja a mais recomendável).

Divisão inteira

Ver definição da divisão inteira nas folhas teóricas.  A solução neste caso passa pelo factorização da CO.  Note-se que 0 <= resto < divisor é o mesmo que 0 <= resto e resto < divisor.
// PC: dividendo >= 0 e divisor > 0
// CO: quociente divisor + resto = dividendo e 0 <= resto < divisor
void divide(int dividendo, int divisor, int& quociente, int& resto)
{
    quociente = 0;
    resto = dividendo;
    // CI: quociente divisor + resto = dividendo e 0 <= resto
    while(resto >= divisor) {
        resto -= divisor;
        quociente++;
    }
}
ou seja
// PC: dividendo >= 0 e divisor > 0
// CO: quociente divisor + resto = dividendo e 0 <= resto < divisor
void divide(int dividendo, int divisor, int& quociente, int& resto)
{
    quociente = 0;
    // CI: quociente divisor + resto = dividendo e 0 <= resto
    for(resto = dividendo; resto >= divisor; resto -= divisor)
        quociente++;
}

Número primo

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

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

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

ou, reforçando a guarda e simplificando apropriadamente a acção:
// PC: n >= 0
// CO: devolve valor lógico de ((Q k : 2 <= k < n : n % k <> 0) e n > 1)
void éPrimo(int n)
{
    if(n <= 1)
        return false;

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

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

Uma versão alternativa comum em C++ (embora talvez pouco recomendável) é:
// PC: n >= 0
// CO: devolve valor lógico de ((Q k : 2 <= k < n : n % k <> 0) e n > 1)
bool éPrimo(int n)
{
    if(n <= 1)
        return false;

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

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

Escreve quadrado oco

void quadradoDeAsteriscos(int n)
{
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++)
            if(i == 0 || i == n - 1 || j == 0 || j == n - 1)
                cout << '*';
            else 
                cout << ' ';
        cout << endl;
    }
}
Saberá escrever a condição invariante de cada um dos ciclos?

Escreve quadrado oco com diagonais

void quadradoDeAsteriscosComDiagonais(int n)
{
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++)
            if(i == 0 || i == n - 1 || j == 0 || j == n - 1 ||
               i == j || j == n - 1 - i)
                cout << '*';
            else 
                cout << ' ';
        cout << endl;
    }
}
Saberá escrever a condição invariante de cada um dos ciclos?