Questão 1

Deve preencher todos os espaços indicados por um sublinhado (___) com V ou F. Qualquer espaço não preenchido será considerado como uma resposta errada.

Em geral as alíneas podem ter zero ou mais respostas correctas.  Cada resposta correctamente assinalada vale 0,5 valores.

Nas alíneas em que apenas uma resposta está correcta (se existirem estão assinaladas no texto), responder com mais ou menos do que um V anula a cotação.  A resposta correcta corresponde à cotação completa.  Qualquer outra resposta corresponde a zero valores.

Em todos os casos em que não é explicitamente referida a localização de uma instrução, considere que esta é dada na função main() do programa seguinte:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class A {
  public:
    A(string const& p, int const n = 1);

    string f1() const;
    int soma() const;

    void p1(string const& c);
    void p2(int const n);

    string s;

  private:
    vector<int> x;

    bool f2(int const n) const;
};

A::A(string const& p, int const n)
    : s(p) {
    x.push_back(n);
}

...

int main()
{
    const A a("um", 1);
    A b("dois", 2);
    ...
}

1.1  Admita que qualquer uma destas instruções é dada na função main() imediatamente após a definição da variável b.  Quais das seguintes instruções estão correctas?

 F   A c;

Não existe um construtor por omissão porque foi declarado um construtor que tem de ser invocado com um ou dois argumentos.

Todas as classes dispõem de um construtor por cópia fornecido automaticamente pela linguagem (excepto se fornecido explicitamente pelo programador ou em alguns casos em que não é possível copiar os membros, e.g., se existirem membros que são referências ou constantes).

 [cotação: 1,5]

1.2  Admita que qualquer uma destas instruções é dada na função main() do programa acima. Quais das seguintes instruções estão correctas?

 V  char c = a.s[1];

A variável membro s é pública e como é do tipo string é indexável.

O procedimento membro p1() não foi declarado como const, pelo que o compilador assume que pode alterar a instância implícita, que neste caso é uma constante.  Assim o compilador proíbe a sua invocação.

A função membro f2() é privada.

Não existe qualquer função f1() visível.

1.3  Assuma que as seguintes instruções são dadas dentro de uma função ou procedimento membro da classe A e que não são declaradas quaisquer variáveis ou constantes dentro dessa função ou procedimento (que não tem quaisquer parâmetros).  Quais das seguintes instruções estão correctas?

 F   x = 0;

A variável membro x é do tipo vector, pelo que não se lhe pode atribuir um valor inteiro.

A função membro f2() devolve um valor booleano, pelo que não se lhe pode atribuir um outro valor.  Note-se que a expressão estaria correcta se a função devolvesse uma referência para um booleano.

1.4  Suponha o seguinte:

void A::p2(int const n) {
    x.push_back(n);
}

int A::soma() const {
    int total = 0;
    for(vector<int>::size_type i = 0; i != x.size(); ++i)
        total += x[i];
    return total;
}

void f(A const& a, unsigned int& n)
{
    if(a.s.length() > n) {
        n += a.s.length();
        return;
    }
    n = a.soma();
}

int main()
{
    A a("uns", 11);

    a.p2(1);
    unsigned int b = 2;
    f(a, b);
    cout << b;

    a.p2(101);
    f(a, b);
    cout << " " << b << endl;
}

 F    2   2
 F    5   2
 V    5   113
 F    2   113

 [cotação: 0,5]

Na construção de a, a cadeia de caracteres s é inicializada com "uns" e o valor inteiro 11 é colocado na posição 0 do vector x.  A instrução a.p2(1) acrescenta ao vector x o valor 1 (posição 1).  A seguir o inteiro sem sinal b é inicializado com o valor 2.  A chamada à função f() faz com que b (passado por referência) tome o valor 5, pois o tamanho de s (3) é maior que n (neste caso, 2).  Em seguida, a instrução a.p2(101) acrescenta ao vector x o inteiro 101 (posição 2). A nova chamada de f() modifica o valor de b para 113, pois agora o tamanho de s é menor que n (5), pelo que n toma o valor da soma dos elementos do vector (11 + 1 + 101).

Considere a organização de uma conferência internacional.  Pretende-se para esta conferência construir um painel com as bandeiras de todos os países intervenientes.  Cada bandeira é identificada pelo nome do país e pelas suas dimensões reais (largura × altura).

2.1  Defina a classe Bandeira de modo a guardar:

1. O nome do país (cadeia de caracteres).
2. A altura (número decimal).
3. A largura (número decimal).

Indique claramente quais dos métodos da classe não alteram a instância implícita.

Não é necessário nesta questão definir qualquer um dos métodos (funções ou procedimentos membro) da classe.

[cotação: 1]

2.2  Defina o construtor da classe Bandeira.

[cotação: 0,5]

2.3  Defina as funções de inspecção do nome do país, da largura e da altura da bandeira para a classe Bandeira, bem como a função que devolve a área da bandeira.

[cotação: 0,5]

2.4  Defina a classe Painel que deve guardar a colecção de bandeiras que o compõem.  Dado que a sala reservada para o acontecimento dispõe de um número de lugares limitado, definiu-se como número máximo de países participantes 30.  Deve declarar os métodos necessários para:

1. Inserir uma bandeira no painel.
2. Retirar uma bandeira no painel, dado o nome do país.
3. Verificar se o painel está vazio.
4. Verificar se o painel está completo (cheio).
5. Verificar se a bandeira de um dado país existe no painel.
6. Devolver a bandeira, dado o nome do país.
7. Devolver a área (mínima) do painel (calculada somando as áreas de todas as bandeiras).
8. Mostrar painel (usando apenas os nomes dos países).

Não é necessário nesta questão definir qualquer um dos métodos.  Coloque comentários indicando claramente para que serve cada uma das variáveis membro que definir.

[cotação: 1,5]

2.5  Defina o método da classe Painel que insere uma bandeira no painel.  Deve inserir mesmo que já exista no painel uma bandeira para o mesmo país.

[cotação: 0,5]

2.6  Defina o método da classe Painel que retira uma bandeira do painel.  Se não existir no painel uma bandeira do país indicado, não faz nada.  Se existirem duas ou mais bandeiras para esse país, deve retirar a última que foi colocada na colecção.

[cotação: 1,5]

2.7  Defina o método da classe Painel que mostra os países do painel no ecrã.  Todas as linha mostradas devem ter exactamente o mesmo número de países, excepto num caso descrito mais à frente.  Devem ser mostrados tantos países por linha quantos possível, mas nunca menos de 2 nem mais de 5.  Se a única solução for mostrar apenas um país por linha, devem-se mostrar exactamente 5 países por linha com excepção da última linha.

Exemplos:

Se o número de países participantes for:

• 1 país
Portugal
• 2 países
Portugal Espanha
• 3 países
Portugal Espanha França
• 4 países
Portugal Espanha França Itália
• 5 países
Portugal Espanha França Itália Holanda
• 6 países
Portugal Espanha França
Itália Holanda Alemanha
• 7 países (caso em que a única solução é 1)
Portugal Espanha França Itália Holanda
Alemanha Bélgica
• 8 países
Portugal Espanha França Itália
Holanda Alemanha Bélgica Grécia
• 9 países
Portugal Espanha França
Itália Holanda Alemanha
Bélgica Grécia Dinamarca
• 11 países (caso em que a única solução é 1)
Portugal Espanha França Itália Holanda
Alemanha Bélgica Grécia Dinamarca Burquina-Faso
EUA

2.8  Escreva um programa que utiliza a classe Painel para simular o painel deste evento internacional.  Este programa deve inicialmente construir um painel com n bandeiras, n dado pelo utilizador do programa.  Para cada bandeira deve ser perguntado ao utilizador qual o nome do país, a altura e a largura da bandeira.  Tenha em atenção que se for introduzido um nome de um país já introduzido no painel, o programa deve pedir um outro nome de país, uma nova altura e largura da bandeira.  Ou seja, no final devem existir as n bandeiras inicialmente previstas pelo utilizador.  Em seguida, o programa deve mostrar o painel no ecrã.  Por fim, deve mostrar a área do painel.

[cotação: 0,5]

Apresenta-se a solução completa:

#include <iostream>
#include <string>
#include <vector>
#include <cassert>

using namespace std;

class Bandeira {
  public:
    Bandeira(string const& nome_do_pais = "",
             double const altura = 0.0, double const largura = 0.0);

    string const& nomeDoPais() const;
    double altura() const;
    double largura() const;

    double area() const;

  private:
    string nome_do_pais;
    double altura_;
    double largura_;
};

inline Bandeira::Bandeira(string const& nome_do_pais,
                          double const altura, double const largura)
    : nome_do_pais(nome_do_pais),
      altura_(altura), largura_(largura) {
}

inline string const& Bandeira::nomeDoPais() const {
    return nome_do_pais;
}

inline double Bandeira::altura() const {
    return altura_;
}

inline double Bandeira::largura() const {
    return largura_;
}

inline double Bandeira::area() const {
    return altura_ * largura_;
}

class Painel {
  public:
    void insere(Bandeira const& bandeira);
    void retira(string const& nome_do_pais);

    bool vazio() const;
    bool cheio() const;
    bool existe(string const& nome_do_pais) const;

    Bandeira const& bandeira(string const& nome_do_pais) const;

    double area() const;

    void mostra() const;
 

  private:
    static unsigned int const numero_maximo_de_paises = 30;

    vector<Bandeira> bandeiras;
};

inline void Painel::insere(Bandeira const& bandeira) {
    assert(!cheio());

    bandeiras.push_back(bandeira);
}

void Painel::retira(string const& nome_do_pais)
{
    vector<Bandeira>::size_type i = bandeiras.size();
    while(i != 0 && bandeiras[i - 1].nomeDoPais() != nome_do_pais)
        --i;
    if(i != 0) {
        /*
          Nota: não se pode simplesmente passar a última bandeira para o lugar
          vago, pois isso alteraria a ordem das bandeiras.  A partir desse instante
          seria impossível saber qual de duas bandeiras do mesmo país entrou em
          último lugar no painel!  Por isso tem mesmo de se usar a solução mais
          lenta...
        */
        for(; i != bandeiras.size(); ++i)
            bandeiras[i - 1] = bandeiras[i];
        bandeiras.pop_back();
    }
}

inline bool Painel::vazio() const {
    return bandeiras.size() == 0;
}

inline bool Painel::cheio() const {
    return bandeiras.size() == numero_maximo_de_paises;
}

bool Painel::existe(string const& nome_do_pais) const
{
    for(vector<Bandeira>::size_type i = 0; i != bandeiras.size(); ++i)
        if(bandeiras[i].nomeDoPais() == nome_do_pais)
            return true;
    return false;
}

Bandeira const& Painel::bandeira(string const& nome_do_pais) const
{
    for(vector<Bandeira>::size_type i = 0; i != bandeiras.size(); ++i)
        if(bandeiras[i].nomeDoPais() == nome_do_pais)
            return bandeiras[i];

    // Será a melhor forma de resolver o problema?
    assert(/* existe == */ false);
}

double Painel::area() const
{
    double area_total = 0.0;
    for(vector<Bandeira>::size_type i = 0; i != bandeiras.size(); ++i)
        area_total += bandeiras[i].area();

    return area_total;
}

void Painel::mostra() const
{
    vector<Bandeira>::size_type por_linha = 5;
    while(bandeiras.size() % por_linha != 0)
        --por_linha;
    if(por_linha == 1)
        por_linha = 5;

    for(vector<Bandeira>::size_type i = 0; i != bandeiras.size(); ++i) {
        if(i != 0)
            cout << (i % por_linha == 0 ? '\n' : ' ');
        cout << bandeiras[i].nomeDoPais();
    }
    cout << endl;
}

int main()
{
    Painel painel;

    cout << "Qual o número de países participantes? ";
    int numero_de_paises_participantes;
    cin >> numero_de_paises_participantes;

    for(int i = 0; i != numero_de_paises_participantes; ++i) {

        string nome_do_pais;
        do {
            cout << "Nome do país: ";
            cin >> nome_do_pais;
        } while(painel.existe(nome_do_pais));

        cout << "Altura: ";
        double altura;
        cin >> altura;

        cout << "Largura: ";
        double largura;
        cin >> largura;

        painel.insere(Bandeira(nome_do_pais, altura, largura));
    }
    cout << endl;

    painel.mostra();

    cout << "A área do painel é "
         << painel.area() << "." << endl;
}

Defina uma classe (MatrizBidimensional) que permita manipular matrizes bidimensionais de double (pode assumir que o número máximo de linhas e colunas é 20).  Deve declarar a classe e definir os seguintes métodos:

1. void MatrizBidimensional::lê() que permite ler os valores da matriz do teclado (organizados por linha).
2. void MatrizBidimensional::mostra() const que permite visualizar no ecrã uma variável do tipo MatrizBidimensional no seguinte formato (não se preocupe com alinhamentos!):

    2.3 1.4 3.9
    3.1 0.5 2.2
    6.7 7.3 4.1
    9.7 1.1 2.3
3. double& MatrizBidimensional::em(int const linha, int const coluna) que devolve uma referência para o elemento da matriz na posição indicada (aborta o programa se a posição for inválida).
4. double MatrizBidimensional::em(int const linha, int const coluna) const que devolve o valor do elemento da matriz na posição indicada (aborta o programa se a posição for inválida).

Defina um construtor adequado, que estabeleça o número de linhas e colunas da matriz (por omissão uma matriz tem dimensão 1 × 1).

Deve também definir o operador * que permite multiplicar duas matrizes.  Se o número de colunas da primeira matriz for diferente do número de linhas da segunda matriz o programa deve abortar.

Esta classe deve suportar as seguintes instruções:

MatrizBidimensional a(3,2);   // define uma matriz bidimensional com 3 linhas e quatro colunas

a.le();    // admita-se que foram introduzidos os números 2.0 3.2 1.0 1.1 3.0 4.1

a.mostra();

// Aparece no ecrã:
//     2 3.2
//     1 1.1
//     3 4.1

MatrizBidimensional b(2,1);

b.le();    // foram introduzidos os números 2.0 1.0
b.mostra();

// Aparece no ecrã:
//     2
//     1

MatrizBidimensional c = a * b;

c.mostra();
 
 

// Aparece no ecrã:
//     7.2
//     3.1
//     10.1

#include <iostream>
#include <cassert>

using namespace std;

class MatrizBidimensional {
  public:
    MatrizBidimensional(int const linhas = 1, int const colunas = 1);

    int linhas() const { return linhas_; }
    int colunas() const { return colunas_; }

    double em(int const linha, int const coluna) const;
    double& em(int const linha, int const coluna);

    void le();
    void mostra() const;

  private:
    static int const ordem_maxima = 20;

    int linhas_,colunas_;
    double elementos[ordem_maxima][ordem_maxima];
};

inline MatrizBidimensional::MatrizBidimensional(int const linhas,
                                                int const colunas)
    : linhas_(linhas), colunas_(colunas) {
    assert(linhas >= 0 && linhas <= ordem_maxima &&
           colunas >= 0 && colunas <= ordem_maxima);
}

inline double MatrizBidimensional::em(int const linha, int const coluna) const {
    assert(linha >= 0 && linha < linhas_ &&
           coluna >= 0 && coluna < colunas_);

    return elementos[linha][coluna];
}

inline double& MatrizBidimensional::em(int const linha, int const coluna) {
    assert(linha >= 0 && linha < linhas_ &&
           coluna >= 0 && coluna < colunas_);

    return elementos[linha][coluna];
}

void MatrizBidimensional::le()
{
    for(int i = 0; i != linhas(); ++i)
        for(int j = 0; j != colunas(); ++j)
            cin >> elementos[i][j];
}

void MatrizBidimensional::mostra() const
{
    for(int i = 0; i != linhas(); ++i) {
        for(int j = 0; j != colunas(); ++j) {
            if(j != 0)
                cout << ' ';
            cout << elementos[i][j];
        }
        cout << endl;
    }
}

MatrizBidimensional operator * (MatrizBidimensional const& a,
                                MatrizBidimensional const& b)
{
    assert(a.colunas() == b.linhas());

    MatrizBidimensional resultado(a.linhas(), b.colunas());;

    for(int i = 0; i != a.linhas(); ++i)
        for(int j = 0; j != b.colunas(); ++j) {
            resultado.em(i, j) = 0.0;
            for(int k = 0; k != a.colunas(); ++k)
                resultado.em(i, j) += a.em(i, k) * b.em(k, j);
        }

    return resultado;
}

int main()
{
    MatrizBidimensional a(3,2);

    a.le();

    a.mostra();

    // Aparece no ecrã:
    //     2 3.2
    //     1 1.1
    //     3 4.1

    MatrizBidimensional b(2,1);

    b.le();    // foram introduzidos os números 2.0 1.0
    b.mostra();

    // Aparece no ecrã:
    //      2
    //      1

    MatrizBidimensional c = a * b;

    c.mostra();

    // Aparece no ecrã:
    //      7.2
    //      3.1
    //      10.1
}

Considere a função int posicaoDe(int const m[], int const n, int const k) que devolve a posição do elemento da matriz m de dimensão n que tem o valor k.  O valor k existe sempre na matriz m.

4.1  Dada a pré-condição n > 0 e (E j : 0 <= j < n : m[j] = k), indique a condição objectivo (CO), a condição invariante (CI) e a guarda (G) do ciclo necessário à construção desta função.

[cotação: 0,5]

O enunciado é ambíguo.  E se existir mais do que um elemento com o valor procurado?  Resolveu-se que seria sempre devolvida a posição do primeiro.

CO: 0 <= posicao_de < n e m[posicao_de] = k e (Q j : 0 <= j < posicao_de : m[j] <> k)
CI: 0 <= posicao_de < n e (Q j : 0 <= j < posicao_de : m[j] <> k)
G: m[posicao_de] <> k

[cotação: 1]

int posicaoDe(int const m[], int const n, int const k)
{
    int posicao_de = 0;
    while(m[posicao_de] != k)
        ++posicao_de;
    return posicao_de;
}

1. Se a PC for verdadeira, então a CI também é verdadeira após a inicialização das variáveis e antes da primeira iteração do ciclo, i.e.:
// PC
init
// implica CI.

// n > 0 e (Ej : 0 <= j < n : m[j] = k)
int posicao_de = 0;
// CI: 0 <= posicao_de < n e (Q j : 0 <= j < posicao_de : m[j] <> k), ou seja,
// CI: 0 <= 0 < n e (Q j : 0 <= j < 0 : m[j] <> k), ou seja,
// CI: 0 < ne V, ou seja, dada a PC,
// CI: V
 

2. Se a guarda G e a CI  do ciclo forem verdadeiras no início de um passo, então a CI também é verdadeira no fim desse passo, i.e.:
// G e CI
passo
// implica CI

// CI e G: 0 <= posicao_de < n e (Q j : 0 <= j < posicao_de : m[j] <> k) em[posicao_de] <> k, ou seja,
// CI e G: 0 <= posicao_de < n e (Q j : 0 <= j < posicao_de + 1 : m[j] <> k)
++posicao_de;
// implica CI: 0 <= posicao_de < n e (Qj : 0 <= j < posicao_de : m[j] <> k)

A demonstração pode ser feita duma forma directa, deduzindo as asserções verdadeiras após cada instrução:

// CI e G: 0 <= posicao_de < n e (Qj : 0 <= j < posicao_de + 1 : m[j] <> k)

Mas , sendo (Qj : 0 <= j < posicao_de + 1 : m[j] <> k) verdadeiro, então posicao_de < n - 1, pois de outra forma o valor k não existiria na matriz, o que é contraditório com a PC da função.  Tem-se então:

// CI e G: 0 <= posicao_de < n - 1 e (Q j : 0 <= j < posicao_de + 1 : m[j] <> k)
++posicao_de;
// 0 <= posicao_de - 1 < n - 1 e (Q j : 0 <= j < posicao_de : m[j] <> k)
// 1 <= posicao_de < n e (Q j : 0 <= j < posicao_de : m[j] <> k)
// que implicaCI: 0 <= posicao_de < n e (Qj : 0 <= j < posicao_de : m[j] <> k)
 

3. Se a guarda G for falsa e a CI for verdadeira, então a CO é verdadeira, i.e.:
// CI e ¬G implica CO.

CI e ¬G: 0 <= posicao_de < n e (Q j : 0 <= j < posicao_de : m[j] <> k) e m[posicao_de] = k, ou seja,
CO

4.4  Usando a função anterior, defina uma função int posicaoDeOuN(int const m[], int const n, int const k) que devolve a posição do elemento da matriz m de dimensão n + 1 que tem o valor k. Neste problema, k pode não existir na matriz m. Se k não ocorrer em m, a função devolve n.  Note que neste caso a pré-condição é n >= 0 e que a matriz tem n + 1 elementos.  Ou seja, a matriz tem n elementos mais um elemento extra que pode ser preechido em qualquer altura, com qualquer valor. Use essa posição para que a resolução deste problema possa ser realizada usando a função definida na alínea 4.2.

[cotação: 0,5]

inline int posicaoDeOuN(int const m[], int const n, int const k) {
    m[n] = k;
    return posicaoDe(m, n + 1, k);
}

Diferencie membros de classe de membros de instância.  Como declarar membros de classe?  Qual a sua utilidade?

[cotação: 1]

Ver Folhas Teóricas, Secção 6.4.5 (Membros de classe).