Sol_Alg21071_t590

Prévia do material em texto

Paulo Rech Wagner 1 Gabarito Prova P1 
 
 
PUCRS - FACULDADE DE INFORMÁTICA 
ENGENHARIA DE COMPUTAÇÃO 
Algoritmos e Estrutura de Dados II - Turma 590 
Prof. Paulo Rech Wagner 
PROVA P1 Data: 20/04/07 
 
 
Questão 1) 
Escrever um algoritmo (algoritmo principal) para armazenar objetos (bolas com os 
atributos número e cor) em uma pilha estática de capacidade para 50 elementos até que 
ela fique cheia ou até que o usuário decida parar (crie uma condição qualquer). A seguir, 
criar uma lista estática com todos os objetos da pilha (esvaziar a pilha) de tal forma que 
no final os objetos contendo o atributo cor azul fiquem no início e os objetos de cor 
vermelha fiquem no final (a única regra é que as bolas azuis fiquem antes das bolas 
vermelhas). (3.0 pontos) 
 
Classe Bola → atributos: numero, cor 
 
Algoritmo Principal 
 inicio 
 PilhaEstatica pilha 
 ListaEstatica lista 
 Bola bol 
 literal resp, cor 
 inteiro numero 
 
 pilha ← novo PilhaEstatica( ) 
 resp ← “s” 
 enquanto ( (não pilha.cheia( )) e (resp = “s”) ) faça 
 inicio 
 escreva(“informe os dados da bola”) 
 leia (numero, cor) 
 bol ← novo Bola(numero,cor) 
 pilha.empilhar(bol) 
 escreva(“deseja empilhar outra bola? (s/n)”) 
 leia (resp) 
 fim 
 lista ← novo ListaEstatica( ) 
 enquanto ( não pilha.vazia( ) ) faça 
 inicio 
 bol ← pilha.desempilhar( ) 
 se ( bol.get_cor( ) = “azul” ) 
 então lista.incluir_inicio(bol) 
 senão lista.incluir_final(bol) 
 fim 
 fim 
Paulo Rech Wagner 2 Gabarito Prova P1 
 
 
Questão 2) 
Escrever um novo método na classe ListaLSE chamado “incluir_mover”. Este método 
recebe um objeto qualquer e realiza uma pesquisa na lista encadeada. Se o objeto 
pesquisado estiver presente na lista, então ele deve ser movido para o início. Caso 
contrário, se ele não estiver presente, ele deve ser incluído no final da lista. (3.0 pontos) 
 
 
/* versão 1 – realizando o encadeamento do nodo localizado */ 
Algoritmo incluir_mover (objeto obj) 
 inicio 
 NodoLSE paux , pant 
 
 paux ← pesquisar(obj) 
 se ( paux = nulo ) 
 então incluir_final(obj) 
 senão se ( paux ≠ prim ) 
 então inicio 
 pant ← anterior(paux) 
 se ( paux = ult ) 
 então ult ← pant 
 pant.set_prox(paux.get_prox( )) 
 paux.set_prox(prim) 
 prim ← paux 
 fim 
 fim 
 
 
/* versão 2 – realizando a exclusão e inclusão início do nodo localizado */ 
Algoritmo incluir_mover (objeto obj) 
 inicio 
 NodoLSE paux 
 
 paux ← pesquisar(obj) 
 se ( paux = nulo ) 
 então incluir_final(obj) 
 senão se ( paux ≠ prim ) 
 então inicio 
 obj ← paux.get_info( ) 
 remover(paux) 
 incluir_inicio(obj) 
 fim 
 fim 
 
Paulo Rech Wagner 3 Gabarito Prova P1 
 
 
Questão 3) 
Um supermercado resolveu cadastrar seus produtos oferecidos. Para isto, foi 
implementada uma lista encadeada contendo cada produto com os seguintes atributos: 
nome, código, categoria e estoque. Considerando que esta lista já possui todos os 
produtos armazenados, fazer: (4.0 pontos) 
a) Informar as classes que devem ser utilizadas nesta questão com seus respectivos 
atributos; 
b) O supermercado adquire novos produtos somente quando o estoque deste produto 
estiver abaixo de um valor limite. Escrever um método que receba este valor limite e 
retorne uma lista encadeada contendo todos os produtos que necessitam ser 
adquiridos; 
c) Escrever um método que retorne a quantidade de categorias que são vendidas no 
supermercado. Como exemplo, na lista abaixo existem 5 letras distintas: 
 
C G P G F X P C G F P X 
 
 
Classes utilizadas: 
Classe ListaLSE 
Classe NodoLSE 
Classe Produto 
Classe ListaProduto subclasse de ListaLSE 
 
Classe Produto 
 inicio 
 literal nome, categoria 
 inteiro código, estoque 
 ... 
 fim 
 
Classe ListaProduto subclasse de ListaLSE 
 inicio 
 ... 
 ListaLSE produtos_adquiridos(inteiro limite) 
 inteiro qtde_categorias( ) 
 ... 
 fim 
 
 
Algoritmo produtos_adquiridos(inteiro limite) 
 inicio 
 NodoLSE paux 
 ListaLSE lprod 
 
 lprod ← novo ListaLSE( ) 
 paux ← prim 
 enquanto ( paux ≠ nulo ) faça 
 inicio 
 se (paux.get_info( ).get_estoque( ) < limite) 
Paulo Rech Wagner 4 Gabarito Prova P1 
 
 então lprod.incluir_final(paux.get_info( )) 
 paux ← paux.get_prox( ) 
 fim 
 retorna lprod 
 fim 
 
 
/* versão 1 – criar uma lista auxiliar e incluir somente os valores distintos da lista */ 
Algoritmo qtde_categorias( ) 
 inicio 
 ListaLSE laux 
 NodoLSE patual, no 
 
 laux ← novo ListaLSE( ) 
 patual ← prim 
 enquanto ( patual ≠ nulo ) faça 
 inicio 
 no ← laux.pesquisar(patual.get_info( ).get_categoria( )) 
 se ( no = nulo ) 
 então inicio 
 no ← novo NodoLSE(patual.get_info( )) 
 laux.incluir_final(no) 
 fim 
 fim 
 patual ← patual.get_prox( ) 
 fim 
 retorna laux.tamanho( ) 
 fim 
 
/* versão 2 – contar quantas ocorrências do valor. Se cont=1 então é distinto */ 
Algoritmo qtde_categorias( ) 
 inicio 
 NodoLSE patual, paux 
 inteiro cont, distinto 
 
 distinto ← 0 
 patual ← prim 
 enquanto ( patual ≠ nulo ) faça 
 inicio 
 cont ← 1 
 paux ← patual.get_prox( ) 
 enquanto ( paux ≠ nulo ) faça 
 inicio 
 se ( paux.get_info( ).get_categoria( ) = patual.get_info( ).get_categoria( ) ) 
 então cont = cont + 1 
 paux ← paux.get_prox( ) 
 fim 
 se ( cont = 1 ) 
 então distinto = distinto + 1 
Paulo Rech Wagner 5 Gabarito Prova P1 
 
 patual ← patual.get_prox( ) 
 fim 
 retorna distinto 
 fim 
 
 
/* versão 3 – pesquisar as categorias na própria lista. Se for o mesmo nodo, então conta, 
pois é a primeira ocorrência dele na lista. */ 
Algoritmo qtde_categorias ( ) 
 inicio 
 NodoLSE paux, no 
 inteiro cont 
 
 cont ← 0 
 paux ← prim 
 enquanto ( paux ≠ nulo ) faça 
 inicio 
 no ← pesquisar(paux.get_info( ).get_categoria( )) 
 se ( no = paux ) 
 então cont ← cont + 1 
 paux ← paux.get_prox( ) 
 fim 
 retorna cont 
 fim 
 
/* versão 4 – remover o repetido e retornar o tamanho*/ 
Algoritmo qtde_categorias( ) 
 inicio 
 NodoLSE patual, paux, no 
 
 patual ← prim 
 enquanto ( patual ≠ nulo ) faça 
 inicio 
 paux ← patual.get_prox( ) 
 enquanto ( paux ≠ nulo ) faça 
 inicio 
 se ( paux.get_info( ).get_categoria( )= patual.get_info( ).get_categoria( ) ) 
 então inicio 
 no ← paux 
 paux ← paux.get_prox( ) 
 excluir_nodo(no) 
 fim 
 senão paux ← paux.get_prox( ) 
 fim 
 patual ← patual.get_prox( ) 
 fim 
 retorna tamanho( ) 
 fim