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

using namespace std;

class A {
  public:
    int z;
    A(const int a = 0, const int b = 1);
    int f();

  private:
    int x;
};

...

int main()
{
    int i = 1, j = 2;
    A meu_a(10);
    const A teu_a(10);
    vector<int> v(2);
    v[0] = v[1] = 10;
    ...
}

 V  A a(v[0], v[1]);
 V  A a;
 F  A a(v[2]);

O vector v só tem dois elementos, de índices 0 e 1.  Não existe elemento de índice 2!

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  meu_a.z = 1;

A variável membro z é pública.

A variável membro x é privada.

A variável membro z é pública, mas é membro de uma constante (teu_a), pelo que o seu valor não pode ser alterado!

A função membro f() não foi declarada como const, pelo que o compilador assume que altera a instância implícita, que neste caso é uma constante.  Assim, o compilador proíbe a invocação de f().

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  a.x = 1;

Não exite qualquer variável a visível!

 [cotação: 1]

1.4  Suponha a seguinte função:

int umaFuncao(int x)
{
    if(x < 0)
        return 0;
    for(int i = 0; i != x; ++i) {
        int z;
        z += x;
    }
    return z;
}

 F o código da função está correcto?

A variável z só é visível até ao fecho do bloco em que foi definida, pelo que não é visível na instrução de retorno.

Questão 2

2.1  Dada a declaração da estrutura Aluno:

struct Aluno {
    Aluno(const string& nome, int nota)
        : nome(nome), nota(nota) {
    }
    string nome;
    int nota;
};

• Inserir informação sobre um aluno na pauta (a informação consiste no seu nome e nota, na forma de uma instância de Aluno).  Se o nome do aluno já existir na pauta substitui a informação guardada.  Se a pauta estiver cheia e o nome do aluno não constar já na pauta aborta o programa, i.e. executa a instrução exit(1);.  Não devolve nada.
• Remover da pauta informação sobre um aluno dado o seu nome.  Se não existir na pauta o nome indicado aborta o programa.  Não devolve nada.
• Procurar um aluno na pauta dado o seu nome.  Devolve true se o nome constar na pauta e false no caso contrário.
• Devolver informação sobre um aluno existente dado o seu nome.  Devolve uma cópia da informação sobre um aluno.  Se o nome não constar na pauta aborta o programa.
• Verificar se a pauta está cheia.  Devolve true se a pauta já contiver o limite de informação sobre 100 alunos e false no caso contrário.
• Verificar se a pauta está vazia.  Devolve true se a pauta não contiver informação sobre nenhum aluno.
• Mostrar a pauta no ecrã.  Não devolve nada.

1. Caso lhe pareça necessário declare também um construtor apropriado para a classe Pauta.
2. Nenhuma das funções ou procedimentos atrás indicados, com excepção do último, escreve quaisquer dados no ecrã.
3. Todas as funções ou procedimentos membro que não alteram a instância implícita devem indicá-lo explicitamente.
4. Todos os parâmetros que não são alterados dentro da função ou procedimento que os usa devem ser indicados explicitamente.
5. A definição da classe Pauta deve conter a declaração das funções e procedimentos membro e a definição das variáveis membro.
6. Não é necessário nesta alínea definir quaisquer funções ou procedimentos membro da classe.

// Solução usando vectores (sem necessidade de limite no número de alunos):
class Pauta {
  public:
    static const int número_máximo_de_alunos = 100;

    // Não é necessário construtor: o C++ fornece um construtor automaticamente que invoca o
    // construtor por omissão do vector de alunos (que constrói um vector vazio, como pretendido).
    void insere(const Aluno& aluno);
    void remove(const string& nome);
    bool existe(const string& nome) const;
    Aluno aluno(const string& nome) const;
    bool cheia() const;
    bool vazia() const;
    void mostra() const;

  private:
    vector<Aluno> alunos;
}

// Solução usando matrizes clássicas do C++ (obriga a alterar a estrutura Aluno de modo a ter
// construtor por omissão):

struct Aluno {
    Aluno(const string& nome = "", int nota = 20)
        : nome(nome), nota(nota) {
    }
    string nome;
    int nota;
};

class Pauta {
  public:
    static const int número_máximo_de_alunos = 100;

    // Neste caso é necessário construtor para inicializar o contador de alunos na
    // pauta (número_de_alunos):
    Pauta();
    void insere(const Aluno& aluno);
    void remove(const string& nome);
    bool existe(const string& nome) const;
    Aluno aluno(const string& nome) const;
    bool cheia() const;
    bool vazia() const;
    void mostra() const;

  private:
     Aluno alunos[número_máximo_de_alunos];
     int número_de_alunos;
}

Notas:

1. Não é necessário repetir a declaração da classe Pauta ou definir qualquer um dos seus métodos nesta alínea.
2. Considere que toda a classe Pauta já se encontra correctamente definida no mesmo ficheiro e que já estão incluídos os ficheiros de cabeçalho das bibliotecas necessárias ao funcionamento do programa (os #include).
3. Assuma que todos os nomes de alunos são compostos apenas por uma palavra.

int main()
{
    Pauta pauta;

    for(int i = 0; i != 10; ++i) {
        cout << "Introduza nome e nota: ";
        string nome;
        int nota;
        cin >> nome >> nota;
        if(pauta.existe(nome))
            cout << "Esse nome já existe!  Ignorado!" << endl;
        else
            pauta.insere(Aluno(nome, nota));
    }
    pauta.mostra();
}

Suponha uma classe ConjuntoInt para representar conjuntos de inteiros

class ConjuntoInt {
  public:
    void insere(const int n);       // insere o inteiro n no conjunto (se já pertencer ao
                                    // conjunto não faz nada).
    void remove(const int n);       // remove o inteiro n do conjunto (se não pertencer
                                    // ao conjunto não faz nada).
    bool existe(const int n) const; // devolve true se o inteiro n pertencer ao conjunto.

  private:
    vector<int> elementos;          // guarda os elementos do conjunto, sendo o seu
                                    // tamanho (elementos.size()) o número de
                                    // elementos no conjunto, ou seja, o seu cardinal.
};

inline void ConjuntoInt::insere(const int n) {
    if(!existe(n))
        elementos.push_back(n);
}

bool ConjuntoInt::existe(const int n) const
{
    // vector<int>::size_type é um tipo inteiro (provavelmente unsigned int).
    for(vector<int>::size_type i = 0; i != elementos.size(); ++i)
        if(elementos[i] == n)
            return true;
    return false;
}

inline void ConjuntoInt::remove(const int n) {
    ...
}

ConjuntoInt c; // c = {}

c.insere(2);   // c = {2}
c.insere(3);   // c = {2, 3}
c.insere(2);   // c = {2, 3}
c.remove(2);   // c = {3}
if(!c.existe(2))
    cout << "O 2 não está no conjunto!" << endl;

O 2 não está no conjunto!

 [cotação: 3,5]

inline void ConjuntoInt::remove(const int n) {
    for(vector<int>::size_type i = 0; i != elementos.size(); ++i)
        if(elementos[i] == n) {
            elementos[i] = elementos[elementos.size() - 1];
            elementos.pop_back();
            // ou elementos.resize(elementos.size() - 1);
            return;
        }
}

Suponha a função double soma(const double m[], const int n) que devolve a soma dos valores existentes numa matriz m de double com n elementos:

double soma(const double m[], const int n)
{
    double soma = 0.0;
    int i = 0;
    while(i != n) {
        soma += m[i];
        ++i;
    }
    return soma;
}

[cotação: 1,5]

PC: n >= 0
CO: soma = (Sj : 0 <= j < n : m[j])
CI:  soma = (S j : 0 <= j < i : m[j]) e 0 <= i <= n

• 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.
 
// PC: n >= 0
double soma = 0.0;
int i = 0;
// CI:  soma = (S j : 0 <= j < i : m[j]) e 0 <= i <= n, ou seja
// CI:  0 = (S j : 0 <= j < 0 : m[j]) e 0 <= 0 <= n, ou seja
// CI:  0 = 0 e 0 <= n, ou seja, dada a PC,
// CI:  V
• 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 eG: soma = (S j : 0 <= j < i : m[j]) e 0 <= i <= nei <> n, ou seja,
// CI eG: soma = (S j : 0 <= j < i : m[j]) e 0 <= i < n
soma += m[i];
++i;
// implica CI: soma = (S j : 0 <= j < i : m[j]) e 0 <= i <= n

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

// CI e G: soma = (S j : 0 <= j < i : m[j]) e 0 <= i < n
soma += m[i];
// soma = (S j : 0 <= j < i : m[j]) + m[i] e 0 <= i < n, ou seja,
// soma = (S j : 0 <= j < i + 1 : m[j]) e 0 <= i < n
++i;
// soma = (S j : 0 <= j < i : m[j]) e 0 <= i - 1 < n, ou seja,
// soma = (S j : 0 <= j < i : m[j]) e 1 <= i < n + 1, ou seja,
// soma = (S j : 0 <= j < i : m[j]) e 1 <= i <= n
// que implicaCI: soma = (S j : 0 <= j < i : m[j]) e 0 <= i <= n
 

• 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: soma = (S j : 0 <= j < i : m[j]) e 0 <= i <= n ei = n, ou seja
soma = (S j : 0 <= j < n : m[j]) e 0 <= n <= n e i = n, ou seja,
soma = (S j : 0 <= j < n : m[j]) e V ei = n, que implica
CO:  soma = (S j : 0 <= j < n : m[j])

Questão 5

Explique brevemente o que é a abordagem descendente à resolução de problemas e quais as suas vantagens.

[cotação: 2]

Esta abordagem consiste dividir o problema a resolver em sub-problemas mais simples, que por sua vez são abordados da mesma forma, dividindo-os em sub-sub-problemas mais simples, e assim sucessivamente até que os problemas a resolver são triviais e de tradução directa para a linguagem de programação em uso (e.g., C++).  A cada resolução de um problema faz-se corresponder uma função ou procedimento, pelo que a solução do problema global tem a forma de uma função ou procedimento que invoca as funções ou procedimentos que resolvem os seus sub-problemas, e assim sucessivamente, numa hierarquia de funções e procedimentos, cada um com um objectivo bem definido.

As vantagens principais desta abordagem são:

• Facilidade a resolução do problema, pois em cada momento o programador só se preocupa com o problema em causa e sua divisão em sub-problemas mais simples, sem se preocupar ainda em como resolverá esses sub-problemas, o que reduz a quantidade de informação com que tem de lidar.
• Leva a uma modularização natural da solução em funções e procedimentos, com as vantagens daí decorrentes em termos de detecção de erros, depuração, manutenção, etc.