Aula nº 15
Aula de Revisões para o teste
Resolução do exercicio nº 1 do exame de 26/06/2000
O objectivo deste exercício é de localizar uma palavra numa frase. O tipo das frases e das palavras é lista de caracteres.
a - Escrever o procedimento que verifica se uma frase contem uma palava dada.
b - Escrever o procedimento que devolve o número das ocorrências duma palavra numa frase.
a)
Procedimento palavra ( existe : boolean , apt p : lista , apt f : lista , pg : lista )
1: Se evaz ( p )
2: Então existe ï Verdadeiro
3: Senão Se evaz ( f )
4: Então existe ï Falso
5: Senão Se cabeça ( f ) = cabeça ( p )
6: Então palavra ( existe , apt cauda ( p ) , apt cauda ( f ) , pg )
7: Senão palavra ( existe , apt pg , apt cauda ( f ) , pg )
Exemplo :
Execução do procedimento :
1 - Confere se a palavra está vazia, não está, então vai para a instrucção nº 3
2 - Confere se a frase está vazia, não está, então vai para a instrução nº 5
3 - Verifica se a letra para a qual f e p apontam são iguais, neste caso "a" é diferente de "e" então vai para a instrução nº 7
4 - Esta instrução chama outra vez a função com f a apontar para "b" e p a apontar para o inicio da palavra ("e")
5 - A função vai executando este algoritmo até chegar ao momento em que f está a apontar para "e"
6 - Neste caso a cabeça de f é igual a cabeça de p e vai correr a instrução nº 6
7 - A funçao é chamada com os apontadores f e p avançados para a próxima caixa mas pg fica no inicio da palavra.
8 - Neste caso ele vai continuar até ao momento em que compara "h" com "z" , como estas duas são diferentes ele vai para a instrução nº 7
9 - Esta vai voltar a chamar a função mas nesta vez a instrução nº 3 é verdadeira e a função vai devolver Falso, ou seja , a palavra não existe na frase
Nota : O pg é uma cópia de p e é utilizado para voltar a apontar para o inicio da palavra no caso de p avançar e a palavra não se verificar.
b )
Procedimento n_ocorrencias ( n : inteiro , apt p : lista , apt f : lista )
boolean existe
1: Se evaz ( f )
2: Então "nada"
3: Senão palavra ( existe , apt p , apt f , p )
4: Se existe
5: Então n_ocorrencias ( n+1 , apt p , apt cauda ( f ) )
Nota: A variável n vai ficar com o número das ocorrências da palavra na frase.
A execução do procedimento n_ocorrencias dá-se como mostra no desenho abaixo. A cada chamada do procedimento palavra em que a variável "existe" devolve verdadeiro, ele vai incrementar na pilha de execução o valor 1, quando a frase for vazia ele soma zero e põe fim à recusividade. Depois soma todos os valores e obtemos n.
Execução do procedimento :
1 - Confere se a frase está vazia, se não estiver vai para a instrucção nº 3
2 - Nesta instrução ele vai correr o procedimento anterior e depois vai para a instrução nº 4
3 - Se esta devolver verdadeiro, i e, se a palavra existir, vai para a instrução nº 5
4 - Nesta altura chama o procedimento de novo com o n incrementado e continua a verificar se existem palavras no resto da frase
5 - Quando a frase estiver vazia o procedimento vai para a instrucção nº 2 e termina a recursividade
Mas estes dois procedimentos ainda não estão correctos, porque não funcionam correctamente por exemplo para o caso seguinte :
Figura 1
Neste caso com esta palavra e esta frase, na execução do procedimento palavra a variável "existe" iria devolver verdadeiro. Mas quando o procedimento n_ocorrencias se chama outra vez o apontador vem como mostra na figura 1 e vai contar mais palavras do que as que existem.
Para superar este "Bug" acrescentou-se um apontador para referenciar o inicio da próxima palavra que o n_ocorrencias tem que verificar, como mostra na figura 2.
Figura 2
Deste modo sabemos onde ficou o apontador na frase e continuamos a verificar se existem mais palavras a seguir. Sendo assim em vez de obtermos três ocorrências da palavra na frase iremos obter apenas duas, que é o valor correcto.
Os procedimentos ficam :
Procedimento palavra ( apt x : lista , existe : boolean , apt p : lista , apt f : lista , pg : lista )
1: Se evaz ( p )
2: Então existe ï Verdadeiro
3: x ï apt f
4: Senão Se evaz ( f )
5: Então existe ï Falso
6: Senão Se cabeça ( f ) = cabeça ( p )
7: Então palavra ( x , existe , apt cauda ( p ) , apt cauda ( f ) , pg )
8: Senão palavra ( x , existe , apt pg , apt cauda ( f ) , pg )
Procedimento n_ocorrencias ( n : inteiro , apt p : lista , apt f : lista )
boolean existe ï declaração de variaveis
lista x
1: Se evaz ( f )
2: Então " nada "
3: Senão palavra ( x , existe , apt p , apt f , p )
4: Se existe
5: Então n_ocorrencias ( n+1 , apt p , apt cauda ( x ) )
Resolução do exercício nº 1 do exame de recurso de algoritmos de 1999.
Os conjuntos de elementos de tipo E. O objectivo deste exercício é de manipular os conjuntos. Cada conjunto é representado por uma lista de conjuntos do tipo E.
1 - Escrever uma função que verifica se y pertence a X onde y é um elemento de E e X é um conjunto.
2 - Escrever uma função que verifica a inclusão: X contido em Y (conjunto).
3 - Escrever uma função que devolve Y intersecção com X.
4 - Escrever uma função que devolve Y união com X.
Um conjunto pode ser implementado como uma lista, porque esta executa todas as condições de um conjunto.
1 -
Função Pertence ( a : elemento , L : lista ) : Boolean
1: Se evaz ( L )
2: Então devolve Falso
3: Senão Se a = cabeça ( L )
4: Então devolver Verdadeiro
5: Senão devolver Pertence ( a , cauda ( L ) )
Exemplo de execução :
1 - Na 1º instrução a função verifica se a lista está vazia, neste exemplo, como o apontador aponta para uma posição que contêm valores, então não está vazia e passa para a instrução nº 3
2 - Nesta instrução ele compara o valor que se encontra na cabeça da lista com o seu elemento, como não são iguais passa para a instrução nº 5
3 - Nesta instrução ele volta a chamar a função, mas o apontador que estava na cabeça fica a apontar para o seguinte elemento, ou seja, a cauda.
4-
A função volta a testar a instrução nº1 , como esta é falsa vai para a
instrução nº 3, e volta a verificar se a cabeça é idêntica ao valor, como
não acontece, executa de novo o ciclo.
5 - Chega um momento em que na instrução nº 3 o valor que esta a ser apontador é igual ao elemento , ou seja, esta instrução é valida, logo a função vai devolver verdadeiro, sendo assim, o elemento pertence à lista.
Nota : O valor que se encontra a seguir ao último valor da lista é NULL, ou seja, vazio.
2 -
Verifica se L1 esta contido em L2.
Função Contido ( L1 : lista , L2 : lista ) : Boolean
1: Se evaz ( L1 )
2: Então devolver Verdadeiro
3: Senão Se Pertence ( cabeça ( L1 ) , L2 )
4: Então Contido ( cauda ( L1 ) , L2 )
5: Senão devolver Falso
Exemplo de execução :
1
- A 1º instrução como não é valida, a função vai executar a instrução
nº 3.
2 - A função Pertence é a que que está definida acima, neste caso, vamos verificar se o primeiro elemento de L1 existe em L2 , nesta função pertence , ela iria devolver verdadeiro logo após a primeira comparação.
3 - Após ser valida a instrução nº3, na instrução nº 4 a função irá ser chamada outra vez mas com o apontador de L1 na próxima posição de memória.
4 - Como a instrução nº 1 não era outra vez valida, voltou-se a tentar verificar a instrução nº3 , em que irá testar se F existe em L2, como isto não é valido ele vai para a instrução nº 5 que vai devolver falso, ou seja, L1 não está contido em L2.
3 -
Esta função vai fazer a intersecção de duas listas, ou seja, vai verificar os elementos em comum entre elas, e vai fazer uma nova lista com esses elementos
Função Inter ( L1 : lista , L2 : lista ) : Lista
1: Se evaz ( L1 )
2: Então devolver NULL
3: Senão Se Pertence ( cabeça ( L1 ) , L2 )
4: Então devolver Criar ( cabeça ( L1 ) , Inter ( cauda ( L1 ) , L2 ) )
5: Senão devolver Inter ( cauda ( L1 ) , L2 )
Exemplo de execução :
1 - Como a 1º instrução não é valida, a função vai para a instrução nº 3.
2 - Verifica se o valor que está a ser apontado em L1, em que neste caso é "D" pertence a L2, como isto é válido, irá criar uma nova lista com esse valor e irá correr outra vez a função mas apontando para o próximo valor de L1, para verificar se este existe em L2.
3 - Depois de testar a instrução nº 1 , na instrução nº 3 a função vai verificar que "F" não pertence a L2, logo vai para a instrução nº 5.
4 - Vai executar novamente a função movendo o apontador para a seguinte posição de L1 , mas sem criar a nova caixa na lista.
5 - Como L1 não está vazia, a instrução nº 3 vai ser verificada, e como "C" pertence a L2, então este valor vai ser criado na lista a seguir a "D". Após isto, vai-se voltar a correr a função com o apontador para a próxima caixa de L1.
6 - Como na 1º instrução a lista L1 se encontra vazia, então a função vai devolver NULL, ou seja, vai fechar a lista criado com os valores de intersecção.
4 -
Vai devolver uma lista contendo os todos os elementos diferentes de dois conjuntos.
Função uniao ( L1 : lista , L2 : lista ) : Lista
Se evaz ( L1 )
Então devolver L2
Senão Se pertence ( cabeça ( L1 ) , L2 )
Então devolver uniao ( cauda ( L1 ) , L2 )
Senão devolver criar ( cabeça ( L1 ) , uniao ( cauda ( L1 ) , L2 )
Exemplo de execução :
O processo de execução desta função é muito semelhante ao da função anterior. Só que neste caso, ele em vez de criar um valor numa nova lista quando esse valor pertence ás duas listas, ele aqui só cria quando o valor existe na lista L1 e não existe na lista L2. Deste modo ficaremos com os elementos diferentes na lista nova, e os elementos comuns às duas ficam "esquecidos" porque nao serão necessários.
Quando a lista L1 fica vazia, então não vale a pena continuar a comparar e faz-se uma conexão da nova lista de valores com a lista L2.
Em suma o que esta função faz é pegar nos elementos que estão em L1 e não estão em L2 e juntá-los a L2
