1: #include <iostream.h>
2: template <class T> class Poligono // T: int, double, etc.
3: { private:
4: const int numMaxPontos;
5: int numActualPontos;
6: T *xx, *yy;
7: public:
8: void Poligono(int numMaxPontos)
9: { this->numMaxPontos = numMaxPontos; numActualPontos = 0;
10: xx = new T [numMaxPontos]; yy = new T [numMaxPontos];
11: }
12: ~Poligono() { delete [] xx; delete [] yy; }
13: Poligono & adicionaPonto(T x, T y)
14: { xx[numActualPontos] = x; yy[numActualPontos] = y; return *this; }
15: void imprime() const
16: { for (int i = 0; i < numActualPontos; i++)
a. cout << "(" << xx[i] << "," << yy[i] << ")\n";
17: }
18: };
19: main()
20: { Poligono<int> p(4);
21: p.adicionaPonto(1,1).adicionaPonto(2,2).adicionaPonto(3,3);
22: p.imprime();
23: return 0;
24: }
Identifique claramente e corrija os erros contidos neste programa
(para cada erro, basta indicar a linha que contém o erro, descrever o
erro e rescrever a linha corrigida).
Apresente ainda os resultados da execução do programa corrigido.
Resolução
linha 8: O construtor não pode devolver void; correcção: Poligono(...)
linha 8 e 9: Para um membro dado constante tem se fornecer um inicializador
de membro; correcção: Poligono(int numMaxPontos) : numMaxPontos(numMaxPontos)
linha 14: O membro dado numActualPontos tem que ser incrementado.
correcção: yy[numActualPontos++] = y;
linha 14: Deve-se fazer um teste ao valor de numActualPontos para que não
ultrapasse o numMaxPontos; correcção:
if (numActualPontos < numMaxPontos) { xx[...]=...; yy[...]=...; ...}
O programa corrigido produziria o seguinte resultado:
(1,1) (2,2) (3,3)2.
Adicione a esta classe um membro-função público ContainsChain</tt> que recebe como parâmetro uma referência a outra cadeia, por exemplo c2</tt>, e retorna true</tt> no caso da instância de Chain sobre a qual o membro-função é invocado conter c2 como sub-cadeia e false</tt> no caso contrário.
Resolução
template<class T>
bool Chain<T>::ContainsChain(const Chain<T> & C2) const
{
ChainNode<T> * current=first, * current2=C2.first;
if(!current2) return true;
while(current)
{
// procura o 1o. elemento
while(current)
{
if(current->data==current2->data) break;
current=current->link;
}
if(!current) return false;
// ja' encontrou uma ocorrencia do 1o. elemento de C2
// e os outros?
current=current->link; current2=current2->link;
while(current && current2)
{
if(current->data!=current2->data) break;
current=current->link; current2=current2->link;
}
if(!current && current2) return false;
if(!current2) return true;
// afinal a ocorrencia detectada do 1o. elemento nao era a
// correcta. Vamos procurar outra: re-inicializar a procura
// do 1o. elemento de C2!
current2=C2.first;
}
return false;
}
3.
Resolução
template <class T>
class BinaryTree {
public:
bool isSearchTree() const {return isSearchTree(root, NULL, NULL); }
private:
bool isSearchTree(BinaryTreeNode<T> *t, T *min, T *max) const;
};
// função auxiliar:
// - Verifica se a sub-árvore com raíz no nó "t" é uma árvore binária e,
// adicionalmente, todos os valores se encontram compreendidos entre
// o valor de um nó "min" e o valor de um nó "max" (inclusivé).
// - Se "min" for NULL, considera-se que não há limite mínimo (ou que
// é -infinito).
// - Se "max" for NULL, considera-se que não há limite máximo (ou que
// é +infinito).
template <class T>
bool BinaryTree<T>::isSearchTree(BinaryTreeNode<T> *t,
T *min, T *max) const {
if (!t) return true; // empty tree
if (min && t->data < *min) return false; // not a search tree
if (max && t->data > *max) return false; // not a search tree
return isSearchTree(t->left, min, t) && isSearchTree(t->right, t, max);
}
4.alvo branco claro branco alvo claro claro alvo escuro negro negro escuroDiz-se que o dicionário tem a propriedade reflexiva se, sempre que o termo t1 está na lista de sinónimos do termo t2, então o termo t2 está na lista de sinónimos do termo t1. Por exemplo, o dicionário apresentado acima não tem a propriedade reflexiva porque "claro" está na lista de sinónimos de "branco", mas o inverso não se verifica. No entanto, o programa apenas tem de indicar se o dicionário tem ou não a propriedade reflexiva, não tendo que o justificar.
Diga que estruturas de dados e algoritmos estudados nesta disciplina (ou construídos a partir deles) seriam adequados para resolver este problema de forma eficiente e apresente uma breve justificação das escolhas efectuadas. Indique, justificando, qual seria a complexidade temporal e espacial desse programa.
Resolução
a) Algoritmo
Tirando partido do facto de o ficheiro de entrada se encontrar
ordenado por ordem alfabética dos termos, pode-se seguir um algoritmo
baseado nas seguintes ideias principais:
- os dados são lidos sequencialmente do ficheiro de entrada;
- para cada par (termo, sinónimo) lido do ficheiro de entrada, em que
"sinónimo" é um sinónimo que se encontra na lista de sinónimos do
termo "termo",
- se "sinónimo" > "termo", insere-se o par (termo, sinónimo) num
conjunto auxiliar (inicialmente vazio), onde ficará à espera que
apareça o par inverso;
- se "sinónimo" < "termo",
- verifica-se se o par inverso (sinónimo, termo) foi previamente
inserido no conjunto auxiliar;
- em caso afirmativo (quer dizer que a propriedade reflexiva está
a ser obedecida), extrai-se esse par
inverso do conjunto auxiliar, pois não vai mais ser preciso;
- em caso negativo, conlui-se que a propriedade reflexiva está a
ser violada e termina-se o processo;
- se no final ainda existir algum par no conjunto auxiliar (quer dizer
que os pares inversos não foram encontrados), conclui-se que não se
verifica a propriedade reflexiva.
b) Estruturas de dados
Em termos de estruturas de dados, pode-se usar uma tabela de hash para
armazenar o conjunto auxiliar.
Para saber rapidamente, no fim do algoritmo, se o conjunto auxiliar
está vazio, pode-se manter um contador do nº de elementos guardados em
cada momento na tabela de "hash", que é incrementada a cada inserção e
decrementado a cada eliminação.
Cada elemento na tabela de "hash" é um par (termo, sinónimo).
A chave é o próprio par.
c) Complexidade temporal
Seja:
m - nº de palavras existentes no ficheiro de entrada (cada palavra é um
termo ou um sinónimo)
n - nº de linhas (termos) no ficheiro de entrada
p - nº de pares (termo, sinónimo)
Verifica-se que p=m-n.
No exemplo do enunciado, tem-se n=5, m=12, p=7.
d) Complexidade espacial
O maior espaço é gasto com o conjunto auxiliar. No pior caso, se todos os
pares (termo, sinónimo) forem inseridos no conjunto auxiliar, o espaço
gasto será de ordem O(p) ou O(m-n), já que p=m-n.