ISCTE - IGE/ETI

Programação II /Programação Orientada por Objectos

Resolução do exame tipo

1998/1999, 2º semestre

Questão 1
Assinale com V (Verdadeiro) as expressões que estão correctas e com F (Falso) as que estão incorrectas.

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.

Qualquer alínea pode ter zero ou mais respostas correctas.  Cada resposta correctamente assinalada vale 0,5 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:

class X {
  public:
    X();
    ...
};

class A {
    int a;
    X* px;
  public:
    int ay;
    A(int);
    virtual void g() const {
        cout << "Execução de A::g(). ";
    }
    ...
};

class B : public A {
  public:
    int bx;
    B(int, int);
    void g() const {
        A::g();
        cout << "Execução de B::g(). ";
    }
    ...
};

int main() {
    ...
}

Questão 1.1
 Quais dos seguintes construtores inicializam correctamente todas as variáveis privadas da classe A?
 F  A::A(int aa) : a(aa), px(X) {}
A inicialização de a está correcta.  Mas a inicialização de px não.  Entre parênteses deveria estar uma expressão cujo resultado fosse do tipo X*, que é o tipo da variável membro px.  A expressão X está sintacticamente errada.  Corrigir para X() não ajuda muito, pois isso corresponde a invocar o contrutor da classe X, cujo resultado é um valor do tipo X, e não um X*.
 F  A::A(int aa) {a = aa; px = X;}
Neste caso o erro é o mesmo, embora durante uma atribuição (e não durante uma inicialização).
 V  A::A(int aa) : a(aa), px(new X) {}
A expressão new X tem como resultado o endereço duma nova variável dinâmica da classe X, pelo que neste caso a expressão usada para inicializar px tem o tipo correcto: X*.

[1.5 valores]

Questão 1.2
Dadas as seguintes declarações:
A* a = new A;
B b;
Quais das seguintes instruções são correctas?
 F  A->ay = 1;
A expressão está mal construída.  Antes do operador -> deveria estar uma extressão cujo resultado fosse um ponteiro para A.
 V  b.ay = 1;
É possível fazer a atribuição porque B deriva publicamente de A e ay é pública em A.
 F   b.a = 1;
A atribuição não é permitida por a ser privada na classe base pública A de B.
 V   b.bx = 1;
É possível fazer a atribuição porque bx é pública em B.

[2 valores]

Questão 1.3
 Para que apareça no ecrã exactamente
Execução de A::g(). Execução de B::g().
quais as instruções que é necessário executar?
 F  A::g(); B::g();
 F  A a; a.g(); B b; b.g();
 V  B b; b.g();
O procedimento membro g() é virtual na classe base (A) e é-lhe sobreposta uma especialização na classe derivada (B).  Essa especialização começa por invocar a versão original do procedimento.  Ou seja: [1.5 valor]
Questão 2
Considere o seguinte código:
template <typename Item>
class Pilha {
  public:
    Pilha();                    // construtor da classe.
    void põe(const Item& item); // coloca item no topo da pilha.
    void tira();                // retira o item do topo da pilha.
    Item topo() const;          // devolve o item no topo da pilha.
    bool vazia() const;         // devolve true sse a pilha estiver vazia.
    bool cheia() const;         // devolve true sse a pilha estiver cheia.
    int tamanho() const;        // devolve o número de itens na pilha.
  private:
    static const int limite = 100;
    Item itens[limite];
    int quantos;
};

enum Naipe {copas, paus, espadas, ouros};
enum Valor {duque, terno, quadra, quina, sena,
            manilha, oito, nove, dez, valete, dama, rei, ás};

class Carta {
    Naipe naipe_;
    Valor valor_;
  public:
    Carta(Naipe naipe, Valor valor);
    Carta();
    Naipe naipe() const;
    Valor valor() const;
};
operator > (const Carta& a, const Carta& b);

Questão 2.1
Defina o operador > para a classe Carta.  Pode assumir que as cartas são comparadas apenas pelo seu Valor.  A ordem de valores a usar é a da sueca (mas incluindo oitos, noves e dezes).  Ou seja: duque, terno, quadra, quina, sena, oito, nove, dez, dama, valete, rei, manilha, ás.
bool operator > (const Carta& a, const Carta& b) {
    int traduz[] = {1, 2, 3, 4, 5, 12, 6, 7, 8, 10, 9, 11, 13};
    return traduz[a.valor()] > traduz[b.valor()];
}
[3 valores]
Questão 2.2
Assuma que o construtor por omissão da classe Carta gera aleatoriamente um naipe e um valor para cada carta criada.  Crie um pequeno programa que crie 4 pilhas de 52 cartas, e um matriz com 4 inteiros chamada pontuações. De seguida o programa deve fazer um ciclo que desempilhe uma carta de cada pilha, compare os seus valores e some um ponto à pontuação respectiva, i.e., se o valor da carta tirada da primeira pilha for o maior, deve ser incrementado o valor de pontuações[0], etc.

No fim o programa deve escrever uma mensagem indicando quem venceu e porquê:

Venceu o jogador 2 com 16 cartas mais altas em 52 jogadas.
A solução pode ser obtida por uma abordagem descendente, dividindo os problemas em sub-problemas sucessivamente mais simples.  Note-se, no entanto, que o jogo, tal como implementado, é injusto em caso de empate.  Quem beneficia mais em média?
const int n_cartas = 52;

int main () {
    const int n_jogadores = 4;

    // Declaração de procedimentos auxiliares:
    void distribui(Pilha<Carta> pilhas[], int n_jogadores);
    void joga(Pilha<Carta> pilhas[], int pontuacoes[], int n_jogadores);
    void resultado(int pontuacoes[], int n_jogadores);

    Pilha<Carta> pilhas[n_jogadores];
    int pontuacoes[n_jogadores] = {};

    distribui(pilhas, n_jogadores);

    joga(pilhas, pontuacoes, n_jogadores);

    resultado(pontuacoes, n_jogadores);
}

void distribui(Pilha<Carta> pilhas[], int n_jogadores) {
    for (int i = 0; i != n_jogadores; ++i)
        for(int j = 0; j != n_cartas; ++j)
            pilhas[i].poe(Carta());
}

void joga(Pilha<Carta> pilhas[], int pontuacoes[], int n_jogadores) {
    // Declaração de procedimentos auxiliares:
    int ganhador(Pilha<Carta> pilhas[], int n_jogadores);
    int tira(Pilha<Carta> pilhas[], int n_jogadores);

    while(!pilhas[0].vazia()) {
        ++pontuacoes[ganhador(pilhas, n_jogadores)];
        tira(pilhas, n_jogadores);
    }
}

void resultado(int pontuacoes[], int n_jogadores) {
    int ganhador = 0;
    for(int i = 1; i != n_jogadores; ++i)
        if(pontuacoes[i] > pontuacoes[ganhador])
            ganhador = i;
    cout << "Venceu o jogador " << ganhador << " com "
         << pontuacoes[ganhador] << " cartas mais altas em "
         << n_cartas << " jogadas." << endl;
}

int ganhador(Pilha<Carta> pilhas[], int n_jogadores) {
    int ganhador = 0;
    for(int i = 1; i != n_jogadores; ++i)
        if(pilhas[i].topo() > pilhas[ganhador].topo())
            ganhador = i;
    return ganhador;
}

void tira(Pilha<Carta> pilhas[], int n_jogadores) {
    for(int i = 0; i != n_jogadores; ++i)
        pilhas[i].tira();
}

[2 valores]
Questão 3
Pretende-se modelar parte de um sistema de gestão de contas bancárias de um banco.  É necessário representar o conceito de conta.  Todas as contas possuem um saldo (em escudos) e uma taxa de juro, e permitem creditar, debitar, ver o saldo, alterar a taxa de juro e calcular o juro (para simplificar o juro pode ser calculado simplesmente como o produto da taxa de juro pelo saldo).

Existem apenas dois tipos concretos de conta: à ordem e a prazo.

Nas contas a prazo só é possível levantar a totalidade do saldo, não podendo ser feitos quaisquer débitos de partes do saldo.  Nestas contas só podem ser efectuados créditos superiores ou iguais a 100 000$.

As contas à ordem devem guardar informação sobre o limite mínimo a que a conta pode chegar.  Este limite pode ser um número negativo, admitindo-se nesse caso que o cliente tem alguma margem de crédito.  As contas à ordem não devem permitir débitos que reduzam o saldo para além do limite mínimo.  Por exemplo, se o limite de crédito para determinada conta à ordem é de -20 000$ e o saldo é de 100 000$ deve ser permitido um débito até 120 000$, mas nunca um débito superior a esse valor.

As contas a prazo devem inicializar a taxa de juro, por omissão, com o valor 0,03 (3%) e as contas à ordem com o valor 0,01 (1%).

As funções de crédito e débito devem devolver o valor o valor efectivamente creditado ou debitado.  Por exemplo, se uma conta à ordem tiver um saldo de 50 000$ e limite de saldo de -10 000$, uma tentativa de debitar 100 000$ (através da invocação da função apropriada) terá como resultado um débito de 60 000$, valor esse que deve ser devolvido pela função respectiva.  Uma tentativa de débito de 1$ de uma conta a prazo com saldo de 200 000$ resultará num débito de 200 000$, sendo este o valor devolvido pela função respectiva.  Uma tentativa de crédito de 5 000$ numa conta a prazo resultará num crédito de 0$, sendo este o valor devolvido pela função respectiva.

Defina totalmente a classe abstracta Conta que representa aquilo que é comum a todas as contas.

Assume-se que os montantes são representados por inteiros (escudos).  Note-se que se optou por não colocar o saldo na classe base.  Experimente colocar e verificará que a solução fica mais complicada.

class Conta {
public:
    // Construtor:
    Conta(double taxa_de_juro = 0.0);

    // Funções e procedimentos (não virtuais) para manipulação de taxas de
    // juro e cálculo de juros:
    double taxaDeJuro() const;
    void taxaDeJuro(double taxa_de_juro);
    int juro() const;

    // Funções e procedimentos puramente virtuais, a serem definidos pelas
    // classes concretas derivadas.
    virtual int debita(int debito) = 0;
    virtual int credita(int credito) = 0;
    virtual int saldo() const = 0;

private:
    double taxa_de_juro_;
};

inline Conta::Conta(double taxa_de_juro) : taxa_de_juro_(taxa_de_juro) {
    assert(taxa_de_juro >= 0.0);
}

inline double Conta::taxaDeJuro() const {
    return taxa_de_juro_;
}

inline void Conta::taxaDeJuro(double taxa_de_juro) {
    assert(taxa_de_juro >= 0.0);
    taxa_de_juro_ = taxa_de_juro;
}

inline int Conta::juro() const {
    // Arredonda-se eliminando casas decimais.  Pode ser melhorado.
    return int(taxaDeJuro() * saldo());
}

[2 valores]

Defina totalmente as classes ContaÀOrdem e ContaAPrazo.

class ContaAOrdem : public Conta {
public:
    ContaAOrdem(int saldo = 0, int limite = 0, double taxa_de_juro = 0.01);

    int debita(int debito);
    int credita(int credito);
    int saldo() const;

private:
    int saldo_;
    int limite_;
};

// Note-se que se permite um saldo inicial inferior ao limite!  Isso significa
// que é preciso cuidado ao calcular os debitos!
inline ContaAOrdem::ContaAOrdem(int saldo, int limite, double taxa_de_juro)
    : Conta(taxa_de_juro), saldo_(saldo), limite_(limite) {
}

inline int ContaAOrdem::debita(int debito) {
    assert(debito >= 0);

    if(saldo_ - debito < limite_) {
        // Verifique o que aconteceria sem este teste se tentasse retirar 50 a
        // uma conta com saldo 0 e limite 10...
        if(saldo_ <= limite_)
            return 0;

        int debito_efectivo = saldo_ - limite_;
        saldo_ = limite_;
        return debito_efectivo;
    }
    saldo_ -= debito;
    return debito;
}

inline int ContaAOrdem::credita(int credito) {
    saldo_ += credito;
    return credito;
}

inline int ContaAOrdem::saldo() const {
    return saldo_;
}
 

class ContaAPrazo : public Conta {
public:
    static const int minimo_credito = 100000;
    ContaAPrazo(int saldo = 0, double taxa_de_juro = 0.03);

    int debita(int debito);
    int credita(int credito);
    int saldo() const;

private:
    int saldo_;
};

inline ContaAPrazo::ContaAPrazo(int saldo, double taxa_de_juro)
    : Conta(taxa_de_juro), saldo_(saldo) {
    // Não faz sentido abrir uma conta a prazo em dívida!
    assert(saldo >= 0);
}

inline int ContaAPrazo::debita(int debito) {
    assert(debito >= 0);

    if(debito < saldo_)
        return 0;

    int debito_efectivo = saldo_;
    saldo_ = 0;
    return debito_efectivo;
}

inline int ContaAPrazo::credita(int credito) {
    if(credito < minimo_credito)
        return 0;

    saldo_ += credito;
    return credito;
}

inline int ContaAPrazo::saldo() const {
    return saldo_;
}

[4 valores]
Questão 4
Implemente um procedimento void ordena(int m[], int n) que ordene uma matriz m contendo n inteiros usando uma das possíveis versões do algoritmo de ordenação por permutação ou bolha (bubble sort).

Veja qualquer livro sobre programação.

[2 valores]

Questão 5
Dada a declaração:
struct Nó {
    typedef int Item;

    // Não existe ponteiro para o nó anterior.
    Nó *seguinte;           // ponteiro para o nó seguinte.
    Item item;              // guarda o item propriamente dito.
};

implemente uma função void remove(Nó*& primeiro, Nó*& ultimo, Nó* no) que deve remover um nó da lista simplesmente ligada e sem guardas com o endereço do primeiro nó dado por primeiro e o endereço do último nó dado por último.  O parâmetro nó contém o endereço do nó a remover.  Os ponteiros primeiro e último, para o primeiro e último elemento respectivamente, devem ser alterados se necessário.

Tenha em atenção que a estrutura Nó não tem ponteiro para o nó anterior (lista simplesmente ligada) e que os nós endereçados por primeiro e último não são guardas, i.e., contêm informação útil.

void remove(Nó*& primeiro, Nó*& último, Nó* nó) {
    // PC: nó faz parte da lista simplesmente ligada.  Por isso não se verifica se a lista está vazia.

    // Como não há guardas, é necessário verificar os casos particulares:
    if(nó == primeiro) {
        primeiro = primeiro->seguinte;
        if(primeiro == 0)
            // Era o único!
            último = 0;
    } else {
        Nó* anterior = primeiro;

        // Como por hipótese o nó faz parte da lista, não vale a pena usar uma guarda mais forte:
        while(anterior->seguinte != nó)
            anterior = anterior->seguinte;

        anterior->seguinte = nó->seguinte;

        if(último == nó)
            último = anterior;
    }
    delete nó;
}

[2 valores]
Questão 6
Explique sucintamente em que circunstâncias deve ser utilizada herança privada e quais as consequências da utilização desse tipo de herança.

Herança privada deve ser usada quando se quer definir uma nova classe por alteração da interface duma classe já existente.  Quando se usa herança privada a relação entre a classe derivada e a classe base não é uma relação é um, ao contrário do que acontece com a herança pública.  Poder-se-ia talvez dizer que a herança privada representa uma relação funciona como mas...  Outra consequência da herança privada é que todos os membros da classe base se tornam privados da classe derivada, a não ser que esta os publicite através duma declaração de utilização na parte pública da classe.

[2 valores]