desafio tema 3 4

Prévia do material em texto

<p>Uma solução eficiente para esse problema é:</p><p>1. Inicialize duas variáveis de ponteiro para encontrar os elementos candidatos na lista</p><p>duplamente vinculada classificada. Inicialize primeiro com o início da lista duplamente vinculada,</p><p>exemplo: primeiro = cabeça, e inicialize em segundo com o último nó da lista duplamente</p><p>vinculada, exemplo: segundo = ultimo nó.</p><p>2. Inicialize o primeiro e o segundo ponteiros como primeiro e último nós. Aqui não há acesso</p><p>aleatório, portanto, para encontrar o segundo ponteiro, percorre-se a lista para inicializar o</p><p>segundo.</p><p>3. Se a soma atual do primeiro e do segundo for menor que 7, então move-se o primeiro na</p><p>direção para frente. Se a soma atual do primeiro e do elemento for maior que 7, então move-se</p><p>o segundo na direção inversa. Se a soma do primeiro e do segundo for igual a 7, então os</p><p>exames são encontrados. Os valores dos exames são salvos e a busca continua até que não</p><p>haja mais nenhum exame a ser checado.</p><p>4. O loop termina quando um dos dois ponteiros retornar NULL, ou eles se cruzam (segundo -></p><p>próximo = primeiro), ou se tornam iguais (primeiro == segundo).</p><p>A implementação em Python fica assim:</p><p>class No:</p><p>def __init__(self,preco):</p><p>self.preco = preco;</p><p>self.ant = None;</p><p>self.prox = None;</p><p>class DoublyLinkedList:</p><p>def __init__(self):</p><p>self.head = None;</p><p>self.tail = None;</p><p>def addNo(self, preco):</p><p>novoNo = No(preco);</p><p>if(self.head == None):</p><p>self.head = self.tail = novoNo;</p><p>self.head.ant = None;</p><p>self.tail.prox = None;</p><p>else:</p><p>self.tail.prox = novoNo;</p><p>novoNo.ant = self.tail;</p><p>self.tail = novoNo;</p><p>self.tail.prox = None;</p><p>def soma(self):</p><p>primeiro = self.head;</p><p>segundo = self.head;</p><p>print(segundo.prox);</p><p>while (segundo.prox != None):</p><p>segundo = segundo.prox;</p><p>encontrado = False;</p><p>while (primeiro != None and segundo != None and primeiro != segundo and</p><p>segundo.prox</p><p>!= primeiro):</p><p>if ((primeiro.preco + segundo.preco) == 7):</p><p>encontrado = True;</p><p>print(primeiro.preco,"---",segundo.preco);</p><p>if primeiro.preco > segundo.preco:</p><p>print("O maior preço é", primero.preco)</p><p>else:</p><p>print("O maior preço é", segundo.preco)</p><p>primeiro = primeiro.prox;</p><p>segundo = segundo.ant;</p><p>else:</p><p>if ((primeiro.preco + segundo.preco)</p>