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:
    int z;
    A(const char c = ' ', const int n = 1);
    A(const string& s, const int n = 0);
    int f1();
    int f2(const char);

  private:
    string x;
    char f3();
};

...

int main()
{
    const int i = 1;
    A meu_a('a', 3);
    vector<char> v(1);
    v[0] = 'X';
    ...
}

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

 V   A a;

No primeiro construtor de A todos os parâmetros têm valores por omissão dos argumentos respectivos.  Ou seja, o primeiro construtor funciona como um construtor por omissão da classe.

O segundo construtor de A tem como parâmetros uma string e um int, tendo este valor 0 (zero) por omissão.

O vector definido na função main tem apenas um elemento (com índice 0).

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?

 F  char c = meu_a.x[2];

x é uma matriz membro privada da classe A.

i é uma constante, pelo que o seu valor não pode ser alterado.

A única função f1() que existe é membro de instância da classe A, pelo que apenas pode ser invocada através de uma instância dessa classe.

z é uma variável membro pública da classe A e f2() uma função membro pública da classe A que devolve um inteiro.

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   "ige" = x;

A atribuição realiza-se no sentido inverso, isto é, atribui-se o que está do lado direito ao que está do lado esquerdo. Neste caso, o que está no lado esquerdo é um valor literal, pelo que não se lhe pode atribuir nada (na realidade é uma expressão do tipo const char[4], ou seja, uma matriz de quatro caracteres constantes).

A função f3() é uma função membro da classe A que devolve um char.

1.4  Suponha o seguinte:

A::A(const char c, const int n) : z(n) {
    x += c;
}
A::A(const string& s, const int n) : x(s) {
    z = n == 0 ? s.size() : n;
}
int A::f1() {
    int n = x.size();
    return n - z;
}
int main() {
    A a("exame",3), b;
    cout << a.f1() << "   " << b.f1() << endl;
}

 V    2   0
 F    5   1
 F    5   0
 F    2   1

A construção de a é feita pelo segundo construtor.  A cadeia de caracteres x é inicializada com "exame".  Como o  parâmetro n toma o valor 3, a variável z toma o valor 3.  Logo, a função f1() devolve 5 - 3, ou seja, 2.  A variável b é construída usando o primeiro construtor, pois é também o construtor por omissão.  O parâmetro c é inicializado com o valor ' ' e o parâmetro n com o valor 1.  A variável membro x é inicializada com o construtor por omissão, e por isso é inicialmente uma cadeia vazia.  Depois da execução do corpo do construtor essa variável passará a conter " " (um só espaço).  A variável membro z é inicializada com 1.  Logo, a função f1() devolve 1 - 1, ou seja, 0.

Questão 2

Considere uma estação dos correios onde existem 3 postos de atendimento com correspondentes filas de espera (numeradas de 0 a 2): o primeiro posto trata da venda de selos e recepção de cartas, o segundo trata dos serviços telefónicos e o terceiro trata das encomendas.  Nesses postos de atendimento são atendidos utentes, cada um dos quais é identificado por um nome e tem um determinado assunto a tratar, correspondente a um dos postos (mas não forçosamente o correspondente à fila de espera em que se encontra, pois é frequente os utentes deste posto enganarem-se...).

2.1  Defina a classe Utente de modo a guardar:

1. O nome do utente.
2. O número do posto correspondente ao assunto que o utente pretende tratar.

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 os construtores da classe Utente.

[cotação: 0,5]

2.3  Defina as funções de inspecção do nome e posto de atendimento desejado para a classe Utente.

[cotação: 0,5]

2.4  Defina a classe FilaDeEspera que deve guardar a informação sobre um conjunto de utentes que irão ser atendidos.  Assume-se que, dadas as limitações de espaço da estação de correios, cada fila não pode ter mais do que 20 utentes.  Deve declarar os métodos necessários para:

1. Inserir um utente no fim da fila.
2. Retirar o utente na frente da fila.
3. Verificar se a fila está vazia.
4. Verificar se a fila está cheia.
5. Devolver o utente que vai ser atendido (o que está na frente da fila).
6. Mostrar todos os utentes na fila.

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: 2]

2.5  Defina o método da classe FilaDeEspera que retira um utente da fila de espera.

[cotação: 1,5]

2.6  Defina o método da classe FilaDeEspera que insere um utente na fila de espera.

[cotação: 1,5]

2.7  Escreva um programa que simule o funcionamento da estação de correios.  Admita que as filas de espera estão inicialmente vazias.  O programa deve gerar aleatoriamente (ao acaso) um conjunto de utentes que deverão ser distribuídos aleatoriamente pelas 3 filas de espera.  O número de utentes a gerar deve ser dado pelo utilizador do programa no seu início.  Os nomes dos utentes serão escolhidos aleatoriamente a partir da seguinte lista de possíveis nomes:

1. Manel
2. Zé
3. Jaquim
4. Tó
5. Quim

Para gerar números aleatórios deve-se usar a seguinte função: int aleatório(int n).  Esta função, que se assume estar definida algures, gera um número inteiro aleatório (ao acaso) entre 0 e n-1.

Depois de gerar os utentes e de os colocar nas filas de espera, o programa deve simular o atendimento a cada utente de cada fila.  Isto é, até que todas as filas de espera se encontrem vazias, deve ser atendido o utente da primeira fila de espera (se existir), em seguida o utente da segunda fila de espera (se existir) e depois o da terceira fila de espera (se existir).  Após cada sessão de atendimento (considera-se uma sessão de atendimento atender uma pessoa de cada uma das filas de espera), deve ser exibido no ecrã o estado das três filas de espera, i.e., os utentes por atender em cada fila.  A simulação termina quando todas as filas estiverem vazias.

Por exemplo:

Fila 0: Manel:0 Quim:1 Jaquim:0
Fila 1: Zé:1 Quim:1
Fila 2: Tó:0 Jaquim:2 Zé:2

Fila 0: Quim:1 Jaquim:0 Tó:0
Fila 1: Quim:1
Fila 2: Jaquim:2 Zé:2

[cotação: 1]

#include <iostream>
#include <string>
#include <cassert>
#include <cstdlib>

using namespace std;

int aleatorio(int const n) {
    return rand() % n;
}

class Utente {
  public:
    Utente();
    Utente(string const& nome, int const posto);

    string nome() const;
    int posto() const;

  private:
    string nome_;
    int posto_;
};

inline Utente::Utente()
    : nome_("Zé Ninguém"), posto_(0) {
}

inline Utente::Utente(string const& nome, int const posto)
    : nome_(nome), posto_(posto) {
    assert(posto >= 0);
}

inline string Utente::nome() const {
    return nome_;
}

inline int Utente::posto() const {
    return posto_;
}

class FilaDeEspera {
  public:
    static int const numero_maximo_de_utentes = 20;

    FilaDeEspera();

    void insere(Utente const& u);
    void retira();

    bool vazia() const;
    bool cheia() const;

    Utente proximo() const;

    void mostra() const;

  private:
    Utente utentes[numero_maximo_de_utentes];
    int entra, sai, numero_de_utentes;
};

inline FilaDeEspera::FilaDeEspera()
    : entra(0), sai(0), numero_de_utentes(0) {
}

void FilaDeEspera::insere(Utente const& u)
{
    assert(!cheia());

    utentes[entra++] = u;
    if(entra == numero_maximo_de_utentes)
        entra = 0;
    ++numero_de_utentes;
}

void FilaDeEspera::retira()
{
    assert(!vazia());

    if(++sai == numero_maximo_de_utentes)
        sai = 0;
    --numero_de_utentes;
}

inline bool FilaDeEspera::vazia() const {
    return numero_de_utentes == 0;
}

inline bool FilaDeEspera::cheia() const {
    return numero_de_utentes == numero_maximo_de_utentes;
}

inline Utente FilaDeEspera::proximo() const {
    assert(!vazia());

    return utentes[sai];
}

void FilaDeEspera::mostra() const
{
    if(!vazia())
    {
        for(int i = 0; i != numero_de_utentes; ++i)
            cout << " "
                 << utentes[(sai + i) % numero_maximo_de_utentes].nome()
                 << ":"
                 << utentes[(sai + i) % numero_maximo_de_utentes].posto();
    }
    cout << endl;
}

int main()
{
    FilaDeEspera f[3];
    string const nomes[] = {"Manel", "Zé", "Jaquim", "Tó", "Quim"};

    cout << "Número de utentes a gerar: ";
    int n_utentes;
    cin >> n_utentes;

    for(int i = 0; i != n_utentes; ++i)
        f[aleatorio(3)].insere(Utente(nomes[aleatorio(5)], aleatorio(3)));

    for(int i = 0; i != 3; ++i) {
        cout << "Fila " << i << ":";
        f[i].mostra();
    }
    cin.get();

    while(n_utentes != 0) {
        for(int i = 0; i != 3; ++i) {
            if(!f[i].vazia()) {
                if(f[i].proximo().posto() == i)
                    --n_utentes;
                else
                    f[f[i].proximo().posto()].insere(f[i].proximo());
                f[i].retira();
            }
        }
        for(int i = 0; i != 3; ++i) {
            cout << "Fila " << i << ":";
            f[i].mostra();
        }
        cin.get();
    }
}

Defina completamente uma classe (Polinómio) que permita manipular polinómios (pode assumir que a ordem máxima é 20).  Deve declarar a classe e definir os seguintes métodos

1. void Polinómio::inserir(const double x, const int n) que permite inserir um termo de ordem n no polinómio.

Tenha em atenção que se for inserido um elemento de ordem igual a outro já existente, este deve ser somado ao existente.
2. void Polinómio::mostra() const que permite visualizar no ecrã uma variável do tipo Polinómio no seguinte formato:

    2×x^0 + -2.1×x^1 + 0.3×x^2 + 4.5×x^3

Deve ainda sobrecarregar o operador += que permite somar um polinómio a outro.  Recorda-se que a soma de dois polinómios consiste num polinómio cujos termos são a soma dos termos de igual ordem dos polinónios somados.

Esta classe deve suportar as seguintes instruções:

Polinómio p;   // define um polinómio que contém o valor 0

p.mostra();
// Escreve no ecrã o seguinte: 0×x^0

p.insere(3.0, 0);
p.insere(4.0, 2);
p.mostra();

// Aparece no ecrã: 3×x^0 + 0×x^1 + 4×x^2

Polinómio q;

q.insere(2.0, 1);
q.insere(-2.0, 2);
q.insere(1.0, 3 );

q.mostra();

// Aparece no ecrã: 0×x^0 + 2×x^1 + -2×x^2 + 1×x^3

p += q;

r.mostra();

// Aparece no ecrã: 3*x^0 + 2*x^1 + 2*x^2 + 1*x^3

// Solução usando vectores (sem necessidade de limite no número de termos):
class Polinomio
{
  public:
    typedef vector<double>::size_type Tamanho;

    Polinomio();
    void insere(double const x, Tamanho const n);
    void mostra() const;
    Polinomio& operator += (Polinomio const& p);

  private:
    vector<double> coeficientes;
};

Polinomio::Polinomio()
    : coeficientes(1)
{
}

void Polinomio::insere(double const x, Tamanho const n)
{
    if(n >= coeficientes.size())
        coeficientes.resize(n + 1);

    coeficientes[n] += x;
}

void Polinomio::mostra() const
{
    for(Tamanho i = 0; i != coeficientes.size(); ++i) {
        cout << coeficientes[i] << "*x^" << i;
        if(i == coeficientes.size - 1)
            cout << endl;
        else
            cout << " + ";
    }
}

Polinomio& Polinomio::operator += (Polinomio const& p)
{
    if(p.coeficientes.size() > coeficientes.size())
        coeficientes.resize(p.coeficientes.size());

    for(Tamanho i = 0; i != p.coeficientes.size(); ++i)
        coeficientes[i] += p.coeficientes[i];

    return *this;
}

// Solução usando matrizes
class Polinomio
{
  public:
    static int const potencia_maxima = 21;

    Polinomio();
    void insere(double const x, int const n);
    void mostra() const;
    Polinomio& operator += (Polinomio const& p);

  private:
    double coeficientes[potencia_maxima];
    int numero_elementos;
};

Polinomio::Polinomio()
    : numero_elementos(1)
{
    for(int i = 0; i != potencia_maxima; ++i)
        coeficientes[i] = 0.0;
}

void Polinomio::insere(double const x, int const n)
{
    assert(n >= 0 && n <= potencia_maxima);
    if(n >= numero_elementos)
        numero_elementos = n + 1;

    coeficientes[n] += x;
}

void Polinomio::mostra() const
{
    for(int i = 0; i != numero_elementos; ++i) {
        cout << coeficientes[i] << "*x^" << i;
        if(i == numero_elementos - 1)
            cout << endl;
        else
            cout << " + ";
    }
}

Polinomio& Polinomio::operator += (Polinomio const& p) {
    if(p.numero_elementos > numero_elementos)
        numero_elementos = p.numero_elementos;

    for(int i = 0; i != p.numero_elementos; i++)
        coeficientes[i] += p.coeficientes[i];

    return *this;
}

Considere a função double norma(const double v[], const int n) que devolve a norma de um vector.  A norma de um vector é a raiz quadrada da soma dos quadrados das suas coordenadas.

4.1  Dada a pré-condição n > 0, 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]

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

[cotação: 1]

double norma( const double m[], cont int n ) {
    double soma = 0.0;
    for(int i = 0; i != n; ++i)
        soma += m[i] * m[i];
    return sqrt(soma);
}

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.
 
// PC: n > 0
// é evidente que a PC implica
// 0 = (S j : 0 <= j < 0 : m[j] × m[j]) e 0 <= 0 <= n, ou seja
// 0 = 0 e 0 <= n, ou seja
// n >= 0
// que é a pré-condição mais fraca que garante que as instruções
double soma = 0.0;
int i = 0;
// levam à veracidade de
// CI: soma = (Sj : 0 <= j < i : m[j]*m[j]) e 0 <= i <= n.
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: soma = (S j : 0 <= j < i : m[j] × m[j]) e 0 <= i <= n e i <> n, ou seja,
// soma = (S j : 0 <= j < i : m[j] × m[j]) e 0 <= i < n
soma += m[i] * m[i];
++i;
// implica CI: soma = (S j : 0 <= j < i : m[j] × 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]*m[j]) e 0 <= i < n
soma += m[i] * m[i];
// soma = (S j : 0 <= j < i : m[j] × m[j]) + m[j] × m[j] e 0 <= i < n, ou seja,
// soma = (S j : 0 <= j < i + 1 : m[j] × m[j]) e 0 <= i < n
++i;
// soma = (S j : 0 <= j < i : m[j] × m[j]) e 0 <= i - 1 < n, ou seja,
// soma = (S j : 0 <= j < i : m[j] × m[j]) e 1 <= i < n + 1, ou seja,
// soma = (S j : 0 <= j < i : m[j] × m[j]) e 1 <= i <= n
// que implica CI: soma = (S j : 0 <= j < i : m[j] × m[j]) e 0 <= i <= n
 

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: soma = (S j : 0 <= j < i : m[j] × m[j]) e 0 <= i <= n e i = n, ou seja,
// soma = (S j : 0 <= j < n : m[j] × m[j]) e 0 <= n <= ne i = n, ou seja, dada a PC,
// soma = (S j : 0 <= j < n : m[j] × m[j]) e V e i = n, que implica
// CO: soma = (S j : 0 <= j < n : m[j] × m[j])

Questão 5

De uma forma simplificada, "um algoritmo é um método de resolução de um dado problema, expresso em linguagem natural".
Explicite brevemente as principais características de um algoritmo.

[cotação: 1]

Ver Folhas teóricas, Secção 1.3 (Algoritmos: resolvendo problemas).