Nome do aluno: _______________________________________________

Número do aluno:  ______________________

Assinatura do docente: ________________________________________

Nome do aluno: _______________________________________________

Número do aluno:  ______________________

Turma: ____________

Notas:

• Leia atentamente todo o enunciado (incluindo estas notas) antes de começar a prova.
• Este exame tem cinco (5) questões.
• Duração: 3:30h (três horas e trinta minutos).
• A prova deve ser efectuada sem consulta.
• Sobre a sua secretária só pode estar o enunciado e uma caneta (coloque pastas, roupa, etc. sobre a cadeira ao seu lado).
• Desligue o telemóvel.
• Deve responder a todas as questões no próprio enunciado, nos espaços reservados.
• Use as páginas em branco no final do enunciado para rascunho.
• Não destaque as folhas do enunciado (nem mesmo as de rascunho).
• Preencha o seu nome e número no recibo (não o destaque). Este ser-lhe-á entregue, assinado por um docente, depois da prova.
• Só um recibo assinado servirá de prova de que entregou a resolução deste enunciado.
• As cotações encontram-se abaixo de cada alínea (total de 20 valores).
• As notas serão afixadas até às 18:00h de sexta-feira dia 27 de Julho de 2001.
• A revisão de provas terá lugar das 9:30 às 11:00h de segunda-feira dia 30 de Julho de 2001 no gabinete 11.
• As orais realizar-se-ão das 9:30 às 12:30h de terça-feira dia 31 de Julho de 2001.  Os alunos interessados (nota superior ou igual a 8) deverão marcar a prova oral por correio electrónico até às 18h de dia 30 de Julho.
• Boa sorte.

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;

enum Tipo {valor1, valor2, valor3};

class A {
  public:
    A(int const n, Tipo const t = valor3);

    Tipo ft() const;
    int fi() const;

    void pt(Tipo const t);
    void pi(int const n);

    Tipo s;

  private:
    vector<Tipo> x;

    bool fp(Tipo const t) const;
};

...

int main()
{
    A const a(1);
    A b(2, valor2);
    bool e_verdade = false;
    ...
}

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

__  A c;
__  A c(3);
__  A c(1, "valor1");

[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?

__ int n = int(a.ft(valor1));
__ b.pt("valor2");
__ e_verdade = a.fp(valor3);
__ b.s = a.ft();

[cotação: 2]

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?

__  x.push_back(Tipo(0));
__  e_verdade = fp(valor1);

 [cotação: 1]
 
1.4  Suponha o seguinte código:

A::A(int const n, Tipo const t)
    : s(t) {
    x.push_back(t);
}

void f(A& a, Tipo t)
{
    a.s = t;
    t = valor3;
}

ostream& operator << (ostream& saída, Tipo const t) 
{
    string nomes[] = {"valor1", "valor2", "valor3"};
    return saída << nomes[t];
}

int main()
{
    A a(11);
    Tipo t = valor1;
    f(a, t);
    cout << a.s << " " << t << endl;
}

__  valor3 valor3
__  valor1 valor3
__  valor1 valor1
__  valor3 valor1

[cotação: 0,5]

Questão 2

Considere o processo de avaliação de um concurso de fotografia.  Pretende-se construir uma colecção de fotografias composta pelas fotografias finalistas.  O processo decorre da seguinte maneira: cada membro do júri tem de classificar três fotografias: a melhor com 3 pontos, a seguinte com 2 pontos e a última das três que considerou melhores com 1 ponto, podendo para além disso realizar as seguintes operações:

• Adicionar fotografias;
• Ver a lista de fotografias que compõe a colecção;
• Ver informação sobre uma dada fotografia;

Coloque asserções verificando as pré-condições nos métodos definidos.

2.1  Defina a classe Fotografia de modo a guardar:

1. A identificação da fotografia (cadeia de caracteres).
2. O nome do autor (cadeia de caracteres).
3. Se a fotografia é a cores ou a preto e branco.
4. A pontuação (número inteiro).

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 Fotografia.

[cotação: 0,5]

2.3  Defina as funções de inspecção da identificação da fotografia, do nome do autor, do tipo (cores ou preto e branco) e pontuação para a classe Fotografia, bem como o procedimento que exibe a informação sobre a fotografia no ecrã e o  procedimento que permite adicionar pontos à fotografia.

[cotação: 0,5]

2.4  Defina a classe Portfolio que deve guardar a colecção de fotografias.  Deve declarar os métodos necessários para:

1. Inserir uma fotografia na colecção.
2. Pontuar uma fotografia, dada a sua identificação e o número de pontos atribuído.
3. Verificar se o painel está vazio.
4. Verificar se uma fotografia existe na colecção, dada a sua identificação.
5. Devolver a fotografia, dada a sua identificação.
6. Eliminar as fotografias não premiadas.
7. Mostrar a colecção de fotografias.

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 Portfolio que pontua uma fotografia na colecção.  Este método tem como pré-condição a existência de uma fotografia com a identificação dada.

[cotação: 1]

2.6  Defina o método da classe Portfolio que elimina as fotografias não premiadas.  Admita que a classe Portfolio tem um método

    void ordenaPorPontuacao();

que ordena a colecção de Fotografias por ordem decrescente da pontuação.

[cotação: 1]

2.7  Considere a classe Avaliador que representa uma membro do júri:

class Avaliador {
  public:
    Avaliador(string const& nome);

    /// Devolve o nome do avaliador.
    string const& nome() const;

    int númeroDeFotografiasAvaliadas() const;

    void registaAvaliaçãoDeFotografia();

  private:
    string nome_;
    int número_de_fotografias_avaliadas;
};

class Júri {
  public:
    /// Construtor.  Os avaliadores do júri construído devem votar
    ///  número_de_votos_por_avaliador vezes.
    Júri(int const número_de_votos_por_avaliador);

    /// Insere novo avaliador no júri.
    void regista(Avaliador const& novo_avaliador);

    /// Regista que um dado avaliador avaliou uma fotografia.
    void registaAvaliaçãoDeFotografiaPor(string const& nome_do_avaliador);

    /// Indica se um dado avaliador faz parte do júri.
    bool inclui(string const& nome_do_avaliador) const;

    /// Devolve o número de fotografias avaliadas por um dado avaliador.
    int númeroDeFotografiasAvaliadasPor(string const& nome_do_avaliador) const;

    /// Indica se a votação do júri está completa, i.e., se todos os avaliadores
    /// votaram o número requerido de vezes.
    bool votaçãoCompleta() const;

    /// Mostra os avaliadores do júri.
    void mostra() const;

  private:
 
 
 
 
 
 

};

• void registaAvaliaçãoDeFotografiaPor(string const& nome_do_avaliador);
  Este método tem como pré-condição que nome_do_avaliador é o nome de um avaliador do júri.
• bool votaçãoCompleta() const;

[cotação: 1,5]

2.8  Escreva um programa que utilize as classes anteriores para simular o processo de avaliação do concurso de fotografia.  Este programa deve inicialmente construir um júri com um número de avaliadores dado pelo utilizador do programa.  Para cada avaliador deve ser perguntado o seu nome.  Tenha em atenção que se for introduzido um nome de um avaliador já existente no painel, o programa deve pedir um outro nome.  Em seguida, o programa deve mostrar o menu:

1 - Adiciona uma fotografia
2 - Pontua uma fotografia
3 - Mostra informação sobre uma fotografia
4 - Listagem das fotografias

0 - Terminar

Opção:

[cotação: 1]

Questão 3

O Mastermind é um jogo em que participam dois jogadores.  Um escolhe uma sequência quatro peões de determinadas cores e outro tem como objectivo descobrir a sequência de cores que o primeiro escolheu.  O nosso objectivo é ajudar o segundo a descobrir a sequência de cores escolhida.

Defina uma classe GeradorDeSequências que permita gerar todas as sequências de tamanho n possíveis.

Deve declarar a classe e definir os seguintes métodos:

1. GeradorDeSequencias::GeradorDeSequencias(istream& entrada) que permite ler as cores.
   
   Formato do ficheiro
   
    número_de_cores
    cor1
    ...
    cor número_de_cores
   
2. void GeradorDeSequencias::gera(int n) const que permite gerar e visualizar no ecrã todas as sequências de tamanho n.

ifstream entrada("cores.dat");
GeradorDeSequencias g(entrada);   // define um gerador que irá ler as cores e probabilidades a
                                  // partir do canal entrada que está associado ao ficheiro "cores.dat"

g.gera(2);

Sendo o conteúdo do ficheiro "dicionario.dic"

    3
    vermelho
    azul
    verde

// Aparece no ecrã:
//     vermelho vermelho
//     vermelho azul
//     vermelho verde
//     azul vermelho
//     azul azul
//     azul verde
//     verde vermelho
//     verde azul
//     verde verde

 

 

g.gera(3);

// Aparece no ecrã:
//     vermelho vermelho vermelho
//     vermelho vermelho azul
//     ...
//     verde verde verde
 

Começando com a sequência 

0000

para obtermos uma nova sequência, alteramos o dígito na última posição para o valor seguinte

0001

e assim sucessivamente até

0009

Nesta altura o dígito na última posição atingiu o valor máximo, pelo que volta a tomar o valor mínimo (0) e o da posição anterior para o valor seguinte

0010

O processo repete-se até alcançarmos o valor máximo (9) para os dígitos em todas as posições.

9999

[cotação: 3,5]

Questão 4

Considere a função

bool sinalDiferente(int const v1, int const v2) {

    assert(v1 != 0);
    assert(v2 != 0);

    return v1 < 0 and v2 > 0 or v1 > 0 and v2 < 0;
}

Pretende-se que a função int localDaPrimeiraPassagemPorZero(vector<int> const& v); devolva o índice do primeiro elemento do par onde ocorre a passagem por zero. Por exemplo, se o tivermos o vector

    1 3 -2 -4 5

Temos duas passagens por zero (3, -2) e (-4, 5), cujos locais são, respectivamente, 1 e 3.

4.1  Sendo a pré-condição (PC)

PC: 2 <= v.size() e (Q i : 0 <= i < v.size() : v[i] <> 0) e (E i : 0 <= i < v.size() - 1: sinalDiferente(v[i], v[i + 1]))

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]

4.2  Defina completamente a função indicada.

[cotação: 1]

4.3  Prove que o ciclo está correcto verificando que:

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.
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
3. Se a guarda G for falsa e a CI for verdadeira, então a CO é verdadeira, i.e.:
   // CI e ¬G implica CO.

Questão 5

Explique sucintamente o que são a abordagem descendente e ascendente à resolução de problemas. Diferencie-as e explique quais as vantagens de as usar em conjunto.

[cotação: 1]