2616

LINGUAGENS DE PROGRAMAÇÃO

Relatório  do 1º Teste Formativo

2000

1º Problema (4 Valores)

Alínea a)

A principal influência do FORTRAN nas demais linguagens, deriva do facto de ter sido a primeira linguagem de programação de alto nível. Antes do FORTRAN a programação tinha de ser feita em ASSEMBLY. Assim enquanto a linguagem ASSEMBLY associava uma instrução simbólica directamente a uma instrução máquina do processador, o FORTRAN associava 1 expressão ou formula de base matemática (representada por 1 instrução FORTRAN) para um conjunto de instruções máquina.
Com uma menor influência surge também o facto de o FORTRAN ser uma linguagem de excelência para os cálculos numéricos e científicos. Assim esta linguagem veio contribuir para a construção de extensas bibliotecas de rotinas adaptadas ao cálculo científico. 
O FORTRAN influenciou igualmente as restantes linguagens devido aos seus problemas:

1.	É difícil escrever programas legíveis. É usual a aplicação de alguns truques difíceis de compreender.
2.	É difícil estruturar os programas de forma lógica.

Estes problemas resultam da necessidade de utilizar a instrução GOTO. Esta instrução provoca um salto da linha de execução corrente para outra secção do código. Os problemas surgem porque é muitas vezes necessário associar esta instrução à instrução IF, criando um salto condicional para outra secção do código. Torna-se pois necessário construir cursos de acção demasiado complicados para serem lembrados em detalhe. A instrução GOTO, utilizada desta forma, leva pois a programas ilegíveis. Assim, de forma indirecta, podemos considerar que o FORTRAN veio a incentivar o aparecimento de estruturas de controle baseadas em ciclos em outras linguagens e em posteriores versões do FORTRAN. O FORTRAN veio também clarificar os problemas da utilização abusiva do GOTO.

1º Problema 

Alínea b)
O FORTRAN77 é normalmente caracterizado por uma gestão de memória estática. Neste método a memória para os dados é reservada de forma estática para cada elemento. Este processo permite determinar em tempo de compilação quais os endereços de memória efectivos para cada variável. O Pascal, por outro lado, é uma linguagem que também apresenta gestão dinâmica de memória. Neste tipo de linguagens, uma variável declarada num dado bloco de código é local à execução desse bloco de código. O compilador utiliza normalmente uma pilha (ou stack) para armazenar as variáveis locais ao bloco de código em execução. Quando o controle do programa sai de dentro desse bloco de código, já não há necessidade de utilizar essa variável. Assim, a informação da variável é removida do topo do stack frame, podendo os l-value das variáveis locais desse módulo serem reutilizados e atribuídos a outras variáveis locais. 
É assim possível, em Pascal, ter subprogramas dentro de outros subprogramas, pois os nomes das variáveis não entraram em conflito (graças à gestão dinâmica de memória) com os nomes declarados dentro de outros subprogramas, ou blocos: a mesma variável tem diferentes l-value(s). Por outro lado, no FORTRAN77, os nomes são comuns: sempre que uma variável tem o mesmo nome, esta referência o mesmo endereço de memória (l-value). Esta característica impossibilita a recursividade e o conceito de blocos de código quando utilizamos exclusivamente gestão estática. 
NOTA:	A gestão estática possibilita a compilação separada. Esta característica foi desenvolvida nos programas em FORTRAN77: as variáveis recebem os seus l-value enquanto o(s) programas são lidos para memória, sendo os endereços para as variáveis apenas definidos durante a leitura do código para memória. Assim é possível efectuar a reserva de memória enquanto o programa é lido, podendo-se conjugar subprogramas distintos apenas quando estes são executados.

2º Problema (4 Valores)

Alínea a)

Após o aparecimento do FORTRAN, surge a necessidade de formalizar os conceitos por trás da sintaxe das linguagens de programação de alto nível. Para se poder efectuar esta formalização foi criada a notação BNF (de Backus-Naur Formalism, já estudado na cadeira de Programação da Universidade Aberta, capítulo 2 de [Martins97]). Enquanto notação, o BNF veio permitir a construção de regras gramaticais com uma notação rigorosa e formal. Esta notação foi utilizada na definição da sintaxe para uma nova linguagem: o ALGOL, e veio possibilitar a realização dos trabalhos teóricos que criaram a ciência da computação. Eis então as razões porque o ALGOL teve mais impacto que o FORTRAN nas restantes linguagens de programação. 

•	Permitiu formalizar (através da notação BNF) conceitos por trás da sintaxe das linguagens de programação de alto nível.
•	Cria a noção de bloco (BEGIN ... END, tal como no PASCAL) e a noção de procedimento.
•	Possibilidade de fazer validação de tipos.
•	Cria a noção de escopo lexical i.e. um dado nome (p. ex. uma variável ou procedimento, no caso do PASCAL) só é visível em determinados blocos.
•	Introdução das instruções de controlo de ciclos WHILE e DO.
•	Faz-se acompanhar por um compilador.

2º Problema (4 Valores)

Alínea b)

O PASCAL é uma linguagem que, tendo como objectivo o ensino da programação, oferece novas facilidades para estruturar dados. A principal dessas facilidades são os tipos de dados definidos pelo utilizador. Ao contrário desta abordagem, o ALGOL, ainda não estava próximo das linguagens mais recentes pois não era possível a criação de novos tipos de dados.
Obviamente, quanto mais simples for uma linguagem de programação na sua definição, mais fácil é a sua aprendizagem, essa facilidade é conjugada com uma maior flexibilidade dada ao utilizador no PASCAL. Tudo isto é obtido em tempo de compilação, i.e. sem qualquer influência na performance dos programas na linguagem. Assim, como o objectivo último das linguagens de programação é o de facilitar a vida ao utilizador, é claramente preferível a solução adoptada no PASCAL.

3º Problema (6 Valores)

Alínea a) 

Considerando a macro swap do enúnciado:

#define SWAP(X,Y,Z)	\
	Z=Y;			\
	Y=X;			\
	Y=Z;			

E:

	int v[]={5,2,1,0}, i=3;

a macro SWAP(i, v[i],aux) vai-se limitar a uma substituição literal dos seus argumentos. Assim será o mesmo que ter o código:

	aux=i;
	i=v[i];
	v[i]=aux;

Ou seja, aux recebe o valor inicial de i (3). De seguida coloca-se v[3] (i.e. 0) em i, e por fim o valor de aux (3) em v[i] (i.e. v[0]). Assim ficaremos com:

	i=0 ; v[]={3, 2, 1, 0}

3º Problema

Alínea b) 

Se utilizássemos passagem por referência e swap fosse um subprograma, os parâmetros iniciais seriam copiados para apontadores (os que entravam como parâmetros da função). Desta forma a troca seria feita, necessariamente com a posição 3 de v[] e não com a posição 0. Assim ficaríamos com:

i=v[3] = 0 (i.e. o valor de i mantinha-se)

e v[]={5,2,1,3} (i.e. a troca foi feita com a posição v[3] do vector e não com v[0]).

4º Problema (6 Valores)

Trata-se de um problema essencialmente interactivo com o utilizador. Essencialmente útil se o testarmos com auxilio de um computador.

EXERCICIO PRÁTICO UTILIZANDO O SEU PC: Vamos implementar o problema proposto assumindo que o aluno utiliza um PC-Windows, fez download do Borland C++ (grátis a partir do site http://community.borland.com/museum/) e o instalou seguindo as instruções. Quem preferir utilizar outro sistema (p.ex. Linux), é livre de o fazer, desde que este suporte C++ (standard) e que adapte os comandos dados ao seu caso concreto.

Aceda ao prompt do MS-DOS no seu computador (Programs/Accessories/MS-DOS Prompt). Crie uma pasta de trabalho no seu disco rígido, no exemplo lp_tf1:
	
	C:\WINDOWS> cd \
	C:\> mkdir lp_tf1
	C:\> cd lp_tf1

Pode testar se o seu compilador C++ está acessível, consultando a sua referência rápida:

 C:\lp_tf1>bcc32 |more

As linhas que se seguem especificam onde se encontram as bibliotecas do C++. Se não as executar na sua directoria de trabalho o seu computador dará diversos erros de compilação e não conseguirá compilar os seus programas.

 C:\lp_tf1>echo -I"c:\Borland\Bcc55\include" > bcc32.cfg
 C:\lp_tf1>echo -L"c:\Borland\Bcc55\lib" >> bcc32.cfg
 C:\lp_tf1>echo -L"c:\Borland\Bcc55\lib" > ilink32.cfg

É necessário agora introduzir o código do seu programa. Escreva:

	    C:\lp_tf1> notepad main.cpp

Após responder Sim/Yes à questão “Cannot find the main.cpp file. Do you want to create a new file?”, na janela de NOTEPAD que entretanto apareceu, tem finalmente o editor onde pode introduzir o seu programa. 

Comecemos por definir duas constantes, especificando o número máximo de palavras que podem ser contadas e a dimensão máxima de cada palavra:

#define MAX_STRING     80
#define MAX_WORDS      10    // Numero máximo de palavras a tratar.

De seguida necessitamos dum vector de strings para o subconjunto de palavras e um vector de inteiros para contar as palavras:

char word_v[MAX_WORDS][MAX_STRING];
unsigned word_c[MAX_WORDS];

Depois começamos por ler o nome do ficheiro, abrir o ficheiro e preencher a lista de palavras a entrar. Utilizaremos o filtro setw sobre o nome do ficheiro para garantir que este não exceda o comprimento de MAX_STRING.

cout<<"Indique o nome do ficheiro de texto:";
cin>>setw(MAX_STRING)>>fname;
cin.ignore(MAX_STRING, '\n'); // retira o '\n' do nome do ficheiro de cin
// …
cout<<"Indique a lista de palavras a contar (termine com [RETURN]):"<<endl;
do {
    char c;

    cout<<"Indique a palavra " << max_words+1 <<":";

    if((c=cin.get()) == '\n') {
      break; // Palavra iniciada por '\n': sai do ciclo
    }
    
    cin.putback(c);
    cin>> setw(MAX_STRING) >> word_v[max_words++];
    cin.ignore(MAX_STRING, '\n'); // retira o '\n' final do stdin  

} while(max_words<MAX_WORDS);

Note-se o tratamento do stream cin. Por um lado é necessário manter a stream limpa. A linha cin.ignore(MAX_STRING, '\n') garante isto ao retirar os \n do stream cin. Por outro lado a solução adoptada quis ler o conjunto de palavras terminadas por um simples ‘\n’. Acontece que quando inserimos apenas ‘\n’ numa leitura de string, tal é normalmente tratado como um caracter em branco. Assim foi necessário efectuar um get sobre o inicio da stream, para verificar se nenhum \n foi inserido. Caso não o tenha sido, o caracter lido tem de voltar à stream (utiliza-se o putback).

Após recebidos todos os dados do utilizador, o ciclo base é trivial:

while( !is.eof() ) {
    is >> tmp_word;
    for(i=0; i < max_words; i++) 
      if(!strcmp(word_v[i], tmp_word)) {
	word_c[i]++;
	break; // sair do for
      }
  } 

Eis o código completo:

#include <iostream.h>   //  Necessário devido a putback e get
#include <fstream.h> // Tratamento de streams,...
#include <iomanip.h> // Necessário devido a setw, ...
#include <string.h>  // strcmp()
#include <stdlib.h>  // exit()

#define MAX_STRING     80
#define MAX_WORDS      10    // Numero máximo de palavras a tratar.

char word_v[MAX_WORDS][MAX_STRING];
unsigned word_c[MAX_WORDS];

void main() {
  char fname[MAX_STRING];
  char tmp_word[MAX_STRING];
  int max_words=0;
  int i;

  cout<<"Indique o nome do ficheiro de texto:";
  cin>>setw(MAX_STRING)>>fname;
  cin.ignore(MAX_STRING, '\n'); // retira o '\n' do nome do ficheiro de cin

  ifstream is (fname);

  if(!is) {
    cout<<"O ficheiro fname gerou um erro. Terminando execução.\n";
    exit(1);
  }

  cout<<"Indique a lista de palavras a contar (termine com [RETURN]):"<<endl;
  do {
    char c;

    cout<<"Indique a palavra " << max_words+1 <<":";

    // Atendendo a que se deseja terminar a inserção da lista de palavras
    // a contar quando se iniciar uma palavra por '\n' vai ser necessario fazer
    // um "lookahead": get seguido de putback

    if((c=cin.get()) == '\n') {
      break; // Palavra iniciada por '\n': sai do ciclo
    }
    
    cin.putback(c);
    cin>> setw(MAX_STRING) >> word_v[max_words++];
    cin.ignore(MAX_STRING, '\n'); // retira o '\n' final do stdin  

  } while(max_words<MAX_WORDS);

  if(max_words>=MAX_WORDS) {
    cout << "Suporto um maximo de " << MAX_WORDS << " palavras, vou tentar continuar com as palavras que inseriu.\n";
  }

  for(i=0; i< max_words; i++) word_c[i] = 0; // Inicializar word_c
  while( !is.eof() ) {
    is >> tmp_word;
    for(i=0; i < max_words; i++) 
      if(!strcmp(word_v[i], tmp_word)) {
	word_c[i]++;
	break; // sair do for
      }
  } 

  cout<<"Resultados:\n";

  for(i=0; i< max_words; i++) {
    cout<<"A palavra "<<word_v[i];
    if(word_c[i] >0) {
      cout<<" ocorreu "<<word_c[i];
      cout<< ((word_c[i] > 1) ? " vezes"  : " vez")<<".\n";
    } else 
      cout<< " não ocorreu.\n";
  }
  // is.close(); implícito 
  
}

Insira este código no notepad. No fim pode compilar e executar o seu programa, na janela MS-DOS (as entradas do utilizador estão sublinhadas, por clareza):    

C:\lp_tf1> bcc32 main.cpp
Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland
main.cpp:
Turbo Incremental Link 5.00 Copyright (c) 1997, 2000 Borland

C:\lp_tf1>main
Indique o nome do ficheiro de texto: main.cpp
Indique a lista de palavras a contar (termine com [RETURN]):
Indique a palavra 1:void
Indique a palavra 2:int
Indique a palavra 3:cout
Indique a palavra 4:cint
Indique a palavra 5:cin
Indique a palavra 6:_
Resultados:
A palavra void ocorreu 1 vez.
A palavra int ocorreu 3 vezes.
A palavra cout ocorreu 1 vez.
A palavra cint não ocorreu.
A palavra cin ocorreu 1 vez.

Relatório  do 2º Teste Formativo

1º Problema (4 Valores)

     a)	Ao iniciar a execução, esta função cria uma variável local com o nome k. Caso haja outra variável k declarada, esta mantém-se em memória, embora o seu acesso, via a variável de nome k, seja ocultado. Ainda antes de executar a primeira instrução de código, esta variável recebe o valor resultante da avaliação do argumento com que a função foi invocada.
Assim, p.ex., se tivéssemos a chamada:

		xpto(5);

a variável k receberia o valor 5.

De seguida o código da função inicia a sua execução com o teste de (i==0). Como este é de facto o caso (pois i recebeu o valor 0 durante a sua inicialização), i recebe valor de k. O ramo else não é executado. No fim retorna-se um apontador para a posição do stack que a variável i referencia e liberta-se a memória das variáveis locais i e k, i.e. retorna-se um dangling pointer.
Caso exista, o valor de k anterior à chamada da função mantém-se. O nome k volta a dar acesso a essa variável previamente definida.

     b)	Caso i fosse declarada como variável local estática, a memória para esta variável seria reservada no heap e não seria libertada quando se saísse da função. Assim evitar-se-ia a situação de dangling pointer, retornando-se um apontador para uma posição de memória que usualmente seria apenas acessível pelo nome k, quando dentro da função xpto.

1º Problema 

     c)	 se viu na alínea a) a função apresentada no enunciado pode servir como primeiro exemplo de uma função retornando um dangling pointer. 
Um segundo exemplo pode ser a simples utilização de um apontador não instanciado. P.ex:

		char *a;

		*a=’b’;

Neste caso o apontador é criado mas não é inicializado. Assim o programa tenta colocar o caracter ‘b’ algures na memória, possivelmente danificando o código do sistema.

O 3º exemplo pode ser similar:

		char *a;

		a=malloc(size of char);
*a=’b’;
		free(a);
		*a=’c’;

Neste caso, reserva-se espaço para um caracter em memória e coloca-se a a apontar para essa posição de memória. Desta forma é possível efectuar a atribuição *a=’b’; sem qualquer erro. Infelizmente esse espaço é de seguida libertado com a instrução free: a voltou a conter um dangling pointer.

     d)	Uma função recursiva necessita de memorizar o valor das suas variáveis em cada iteração. Imagine-se o seguinte caso:

		foo(int n) {

			… Bloco Código 1…
			y=foo(x);
			… Bloco Código 2 dependente do valor de n e y…
		}
O valor de n de uma dada iteração têm de se manter constante após a chamada da função foo para a próxima iteração, pois caso contrário a sua utilização no bloco de código 2 não seria possível.

Acontece que com alocação estática de memória, um nome (i.e. a variável n) apenas pode denotar um mesmo endereço de memória. Assim, aquando da segunda iteração da função recursiva, seria atribuído um novo valor a n, sendo o valor inicial destruído. Desta forma seria impossível utilizar simultaneamente y e o n anterior no bloco de código 2.

2º Problema (8 Valores)

NOTA PRÉVIA: INDICAÇÕES PARA A UTILZAZAÇÃO DO BCC
 
EXERCICIO PRÁTICO UTILIZANDO O SEU PC: Vamos implementar as alterações propostas utilizando a classe IntArray, fornecida no CD-ROM que acompanha o manual. Mas antes disso, temos de preparar um pouco o ambiente de trabalho.

Nos próximos parágrafos, assume-se que o aluno utiliza um PC-Windows, fez download do Borland C++, o instalou seguindo as instruções fornecidas e tem o CD-ROM que acompanha o manual no leitor de CDs (drive E:). Quem preferir utilizar outro sistema (p.ex. Linux), é livre do fazer, tendo no entanto de adaptar os comandos dados ao seu caso concreto.

Aceda ao prompt do MS-DOS no seu computador (Programs/Accessories/MS-DOS Prompt). Crie uma pasta de trabalho no seu disco rígido, no exemplo lp_tf2 :
	
	C:\WINDOWS> cd \
	C:\> mkdir lp_tf2
	C:\> cd lp_tf2

De seguida copie os ficheiros C++ do CD para o seu disco rígido, copie a função ex25.cpp (que testará o seu código), compile e execute o programa:

	C:\lp2tf>copy e:\Cap5\ex24-5-6\intarray.h .
	        1 file(s) copied

	C:\lp2tf>copy e:\Cap5\ex24-5-6\intarray.cpp .
	        1 file(s) copied
	C:\lp2tf>copy e:\Cap5\ex24-5-6\intarray.cpp .
	C:\lp2tf>bcc32 |more

Note que esta linha apenas mostra como consultar a referencia rápida do compilador. As linhas que se seguem especificam onde se encontram as bibliotecas do C++. Se não as executar na sua directoria de trabalho o seu computador dará diversos erros de compilação.

	 C:\lp2tf>echo -I"c:\Borland\Bcc55\include" > bcc32.cfg
	 C:\lp2tf>echo -L"c:\Borland\Bcc55\lib" >> bcc32.cfg
	 C:\lp2tf>echo -L"c:\Borland\Bcc55\lib" > ilink32.cfg

Finalmente pode compilar o seu programa:    

C:\lp2tf> bcc32 ex25.cpp intarray.cpp
Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland
ex25.cpp:
Error E2209 IntArray.h 2: Unable to open include file 'bool.h'
*** 1 errors in Compile ***
intarray.cpp:
Error E2209 IntArray.h 2: Unable to open include file 'bool.h'
*** 1 errors in Compile ***

De facto… O programa do CD contém um erro!! Não desanimemos: vamos corrigir este erro.

	C:\lp2tf> notepad intarray.h

Na janela do notepad que entretanto abriu, comente a segunda linha (i.e. insira // antes de #include "bool.h"). Agora sim, o programa deverá compilar sem erros (telefone ao docente da cadeira se tal não acontecer!):

C:\lp2tf> bcc32 ex25.cpp intarray.cpp
C:\lp2tf>bcc32 ex25.cpp intarray.cpp
Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland
ex25.cpp:
intarray.cpp:
Turbo Incremental Link 5.00 Copyright (c) 1997, 2000 Borland

Resta executar o resultado de tanto esforço:

C:\lp2tf>ex25
Insira 10 inteiros -> 1 2 3 4 5 1 2 3 4 5

No intArray v1 foram inseridos 10 inteiros

Qual o indice que pretende ler? 4
O inteiro situado no indice 4 e' 5

Tudo funcionou bem! Imagino que neste momento esteja desejoso de alterar este programa, por isso voltemos ao teste formativo…

2º Problema

Alínea a)

A criação de um método display() é algo simultaneamente fácil, motivante e útil. Para quem estudou o manual e fez a cadeira de Programação da Universidade Aberta, a solução é linear:

Adiciona-se o código que se segue ao código da classe (i.e. ao ficheiro IntArray.cpp):

void IntArray:: display() {
	unsigned i;

	for(i=0; i< sz; i++) cout << v[i] << “ “;
	cout<<endl;
}

E, obviamente, adiciona-se a definição do método à definição da classe (i.e. ao ficheiro IntArray.h):

class IntArray {
	int* v;      // Apontador para array de inteiros.
	unsigned sz; // Espaço reservado para o array.

	// Inviabilizar a construção por cópia e a afectação.
	IntArray (const IntArray&){} //Construtor por cópia.
	// etc…
	unsigned size() const { return sz; }
	void display(void);
};

Nota: Para testar a função insira igualmente no fim da função main(), do ficheiro ex25.cpp, a linha:

	v1.display();

De seguida recompile o programa e verifique que funciona.

2º Problema 

Alínea b)

Atendendo a que podemos utilizar a função com o algoritmo de Quick Sort, incluída na biblioteca de sistema <stdlib.h>, código do método ordIntArray() resume-se à chamada desta função genérica. Para fazer tal, estudemos o protótipo desta função (extraído da página de manual do sistema Unix):

void qsort(void *base, size_t nmemb, size_t size,
              int (*compar)(const void *, const void *))

i.e. qsort recebe como primeiro argumento um apontador (para o vector a ordenar) de tipo genérico (i.e. um void *), seguido do número de elementos do vector e do tamanho de cada elemento (que é dado por sizeof(int)).  Por fim indica-se qual a função que especifica a ordem do vector. Esta função deve retornar -1 se o primeiro valor for menor que o segundo, +1 se for maior e zero se os valores forem iguais. Comecemos por criar esta função (página 217 do manual), que deve respeitar criteriosamente a especificação que o parâmetro apontador para função compar de qsort aguarda:

	int cmpInt( const void *a, const void *b) {
		return *(int *) a - *(int *)b;
	}

De seguida basta ter cuidado com os tipos dos parâmetros utilizados:

void IntArray:: ordIntArray() {
	qsort( (void *) v, (size_t) sz, sizeof(int), cmpInt);
}

Não esquecendo a sua definição na definição da classe:

class IntArray {
	// etc…
	void display(void);
	void ordIntArray(void);
};

Se testar ( inclua o comando v1.ordIntArray(); imediatamente antes de se perguntar qual o índice a obter, na função main() )deverá obter qualquer coisa como:

C:\lp2tf>ex25
Insira 10 inteiros -> 97 85 7 6 54 432 3 21 1 02

No intArray v1 foram inseridos 10 inteiros

Qual o indice que pretende ler? 4
O inteiro situado no indice 4 e' 7
1 2 3 6 7 21 54 85 97 432

2º Problema 

Alínea c)

Atendendo a que a lista está previamente ordenada basta comparar cada elemento com o anterior na lista. Quando se encontram dois números iguais, será necessário remover esse elemento, i.e. mover os elementos que se lhe seguem para a posição do elemento repetido. Desta forma bastaram dois índices: o índice anterior e o índice actual.  Quando os valores são iguais, apenas o índice actual deve avançar (pois vamos remover o actual). Quando os valores são diferentes ambos os índices avançam para a próxima posição, sendo feita a actualização do valor anterior (no caso de terem sido encontrados elementos iguais anteriormente). No fim o tamanho do vector terá de ser actualizado. Utilizaremos o método resize (que também serve para diminuir o tamanho do vector) para fazer isto. Utilizaremos a variável especial this, que aponta sempre para o objecto ao qual pertence o método, para actualizar o vector. Ou seja, no ficheiro IntArray.cpp adiciona-se:

void IntArray:: removeEqual() {
unsigned i,i_ant;

	i_ant = 0;
	for(i=1; i<sz; i++) {
		if(v[i] != v[i_ant]) {
			i_ant++;
			if(i_ant != i) {
				v[i_ant]=v[i];
			}
		} 

	}
	
	this->resize(i_ant,0);
}

Actualiza-se igualmente a definição no ficheiro IntArray.h:

class IntArray {
	// etc…
	void ordIntArray(void);
    void removeEqual(void);
};

Por fim acrescenta-se mais este método no código de teste. Eis a interacção com o programa de teste:

C:\lp2tf> ex25
Insira 10 inteiros -> 1 3 2 1 4 9 1 2 8 4
 
No intArray v1 foram inseridos 10 inteiros
 
Qual o indice que pretende ler? 1
O inteiro situado no indice 1 e' 2
1 2 3 4 8 9
C:\lp2tf> ex25
Insira 10 inteiros -> 1 3 2 1 4 9 1 2 8 0
 
No IntArray v1 foram inseridos 10 inteiros
 
Qual o indice que pretende ler? 1
O inteiro situado no indice 1 e' 1
0 1 2 3 4 8 9

2º Problema 

Alínea d) 

Nota: Mais uma vez, pode copiar a classe IntList do CD que acompanha o manual de C++, com o comando:

C:\lp2tf>copy e:\cap5\ex28-9\intlist.* .
e:\cap5\ex28-9\intlist.cpp
e:\cap5\ex28-9\intlist.h
        2 file(s) copied
C:\lp2tf>notepad intlist.h
C:\lp2tf>notepad intlist.cpp

De novo terá que remover a linha #include “bool.h”, no ficheiro IntList.h . Desta vez as alterações serão efectuadas sobre o código de IntList.

Para se construir a lista a partir do vector, bastará percorrer todo o vector, construindo a lista durante a passagem. A solução é assim:

IntList:: IntList(IntArray &v) {
unsigned sz=v.size();
unsigned i;
IntNode *next;

	ptList = new IntNode(v.at(0));
	next= ptList;

	for(i=1;i<sz; i++) {
                next->ptNext = new IntNode(v.at(i));
                next= next->ptNext;
	}
        next->ptNext=NULL;

}

A definição da classe IntList será:

#include <iostream.h>
#include "IntArray.h"

class IntList {

	struct IntNode {// Classe interna para os nós da lista.
		int data;
		IntNode* ptNext;
		IntNode(int n) { data = n; }// Construtor com int n.
	};

…

public:
	IntList() { ptList = NULL; } // Iniciar a lista.
      	  IntList(IntArray &v); // Construtor por copia de vector
	~IntList() { removeAll(); } // Destruir todos os nós.
…
};

Note-se que a definição da classe utiliza a classe IntArray donde é necessário a inclusão do ficheiro com a definição desta classe (#include “IntArray.h”).

O código de teste, poderá ser:

#include "IntList.h"

const int INITIAL_SIZE = 5, NUM_INT = 10;
void main() {	
	IntArray v1(INITIAL_SIZE); // v toma dimensão 5.
        IntList *l;

	// Escrever no objecto v1 10 inteiros lidos do cin.
	cout << "Insira " << NUM_INT << " inteiros -> ";
	int value, i; 
	for( i = 0 ; i < NUM_INT ; i++ ) {
		cin >> value;  
		v1.setAt(value, i);// se i>4 amplia espaço.
	} 
	cout << "\nNo intArray v1 foram inseridos "
	     << v1.size() << " inteiros" << endl;

	cout<<"Iniciando passagem para lista\n";
               l=new IntList(v1);
	cout<<"A lista:";

        l->display();
}

Note que para compilar este código deverá agora utilizar o comando:

		c:\lp2tf>bcc32 ex25.cpp IntArray.cpp IntList.cpp

Eis um exemplo de interacção com o programa gerado:

C:\lp2tf>ex25
Insira 10 inteiros -> 1 2 3 4 5 6 7 8 9 0

No intArray v1 foram inseridos 10 inteiros
Iniciando passagem para lista
A lista:1 2 3 4 5 6 7 8 9 0

3º Problema (6 Valores)

EXERCICIO PRÁTICO UTILIZANDO O SEU PC: Vamos testar o código proposto com um interpretador Prolog. Se consultar a FAQ de Prolog, verá que um dos interpretadores Prolog que há, gratuitos para MS-Windows, é o SWI-Prolog. Talvez não seja tão completo como outros (como por exemplo o XSB), mas para esta cadeira basta. Além disso como o tempo de download do seu ficheiro de instalação (2Mb) é aceitável e tem código (escrito em C!) livremente acessível optei por utilizar este sistema (versão 4.0.0). No entanto o que está escrito abaixo é genérico para qualquer interpretador Prolog minimamente standard.

Se também optar pelo SWI-Prolog, poderá efectuar o seu download directamente de: 

http://www.swi.psy.uva.nl/download.html

Alínea a)

O goal gosta(X, maria) irá unificar com todos os termos na base de dados que contenham o átomo maria como segundo argumento. Assim, consultando a base de dados de regras, as soluções serão:

X= joão ;
X= bernardo ;
X= jorge;

EXERCICIO PRÁTICO UTILIZANDO O SEU PC: Vamos confirmar estes resultados utilizando o computador. Após seleccionar um interpretador Prolog e o instalar, terá de executar este programa. Com o SWI-prolog (bem como com os restantes sistemas prolog para windows) bastará seleccionar o icon do programa. Aparecerá uma janela com o prompt Prolog:

Welcome to SWI-Prolog (Version 4.0.0)
Copyright (c) 1990-2000 University of Amsterdam. 
Copy policy: GPL-2 (see www.gnu.org)

For help, use ?- help(Topic). or ?- apropos(Word).

?-

O sistema está a aguardar uma query (ou goal).
Com o notepad crie, na directoria de trabalho um programa com o que está no enunciado:

gosta(joão, maria).
gosta(bernardo, maria).
gosta(jorge, maria).
gosta(maria, joão).
gosta(joana, joão).

nao_gosta(X,Y) :- gosta(X,Z), gosta(Y,Z).

Grave o seu programa com o nome “tf2_p4.pl”. De seguida tem de indicar ao Prolog para ler e interpretar o ficheiro (embora o SWI prolog indique a compilação do ficheiro, tal não é, por regra, o caso). Tal pode ser feito com o comando [NomeFicheiro] seguido de ‘.’ (tal como em lingua natural, todos os comandos Prolog terminam com ‘.’). Assim, escreva na prompt Prolog o que está sublinhado:

?- [tf2_p4].
% tf2_p4 compiled 0.00 sec, 3,136 bytes

Yes
?-

A resposta “Yes” indica que o comando foi executado com sucesso.

Para confirmar a resposta basta escrever:

gosta(X, maria).

A resposta é:

gosta(X,maria).

X = joão _

O cursor ‘_’ a piscar indica que esta é apenas uma solução. Entre ‘;’ para indicar que pretende obter outras soluções possíveis para a questão que colocou.

?- gosta(X,maria).

X = joão ;

X = bernardo ;

X = jorge ;

No
?-

Repare que desta vez a resposta é ‘No’. I.e. para além das três soluções apresentadas não há mais soluções.

3º Problema 

Alínea b)

Antes de mais tentemos interpretar o significado da regra:

nao_gosta(X,Y) :- gosta(X,Z), gosta(Y,Z).

O cabeçalho poderia ler-se: “(uma pessoa) X não gosta de (uma pessoa) Y se”. No corpo da regra vem o que se segue: “(essa pessoa ) X gosta (de outra pessoa) Z  e (a pessoa) Y (também) gosta (da pessoa) Z. I.e. uma pessoa não gosta de outra se ambas gostam da mesma pessoa: no mínimo redutor...

nao_gosta(joana,X) vai tentar ver primeiro de quem gosta a joana. Pela base de dados a joana gosta apenas do joao (i.e. a regra gosta(joana,joao)) , agora a questão será (i.e. com a variavel Z=joao)), se mais alguém gosta do joao. gosta(Y,joao) tem agora duas soluções: a maria e a própria joana. Assim, o Prolog deverá responder que:

?- nao_gosta(joana,X).

X = maria ;

X = joana ;

No

Com o bernardo o caso é semelhante… gosta(bernardo,X) tem a solução maria (i.e. o bernardo gosta da maria). Ora como gosta(Y,maria) tem as soluções joão,  bernardo e jorge, o bernardo não gosta das seguintes pessoas:

nao_gosta(bernardo,X).

X = joão ;

X = bernardo ;

X = jorge ;

No
?-

Já agora, com esta regra é fácil provar que todas as pessoas que gostam de alguém não gostam de si próprios (verifique quais as soluções da query nao_gosta(X,X)). De facto, nada nos diz que X e Y não podem ser a mesma pessoa. Para resolver seria necessário alterar a regra para nao gostar:

nao_gosta(X,Y) :- gosta(X,Z), gosta(Y,Z), \+ X=Y.

o operador \+ significa ‘negar o resultado’ e, obviamente X=Y significa X unifica com o Y, i.e. adicionamos a restrição de que X não pode ser a mesma pessoa que Y. Experimente esta alteração no seu programa, alterando o ficheiro no notepad, gravando e voltando a ler o programa para memória. Verifique que desta vez se obtém o comportamento pretendido. 

Quando quiser terminar a sessão, o comando ‘halt.’ termina a execução do Prolog.

3º Problema 

Alínea c)

A resposta a esta questão deve ficar clara após a resolução da alínea anterior: O Prolog é uma linguagem lógica. Tal como as linguagens funcionais, esta linguagem é orientada para problemas específicos que tenham a ver com questões lógicas. Assim, tendencialmente, no Prolog o utilizador apenas especifica factos e regras: a preocupação é (mais) com a especificação do problema e não (tanto) com o algoritmo.

FIM