30

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

ALUNOS QUE TAMBÉM VISUALIZARAM

  • +6.581

Passo 1 de 4keyboard_arrow_downkeyboard_arrow_up

Nesse exercício o professor Williams propõe um esquema que permite que o algoritmo de pares mais próximos verifique somente cinco pontos que vêm depois de cada ponto no arranjo Y’. No esquema do professor a ideia é sempre colocar pontos sobre a reta I no conjunto P. Então não pode haver pares de pontos coincidentes sobre a reta I com um ponto em . Assim, no máximo seis pontos podem residir no retângulo . Devemos mostrar qual a falha no esquema do professor.

Passo 2 de 4keyboard_arrow_downkeyboard_arrow_up

O algoritmo de pares mais próximos é usado para encontrar o comprimento entre dois pontos, tal que o comprimento medido é o comprimento mínimo. Nesse algoritmo a abordagem de “dividir e conquistar” funciona no conjunto P de pontos, divididos em duas partes, , em uma linha vertical formada pelas coordenadas x e y de pontos armazenados em matrizes x e y ordenadas.

As coordenadas x e y de pontos do lado esquerdo ou direito da linha são armazenadas em . Do lado esquerdo para o direito a distância entre dois pontos é . A menor distância entre eles é considerada e é representada por .

Passo 3 de 4keyboard_arrow_downkeyboard_arrow_up

Agora, só temos que checar se existe algum par de pontos com comprimento menor do que entre eles e se um ponto está do lado direito e o outro do lado esquerdo da linha. Para isso, uma matriz Y’ é criada para armazenar pontos que estão a uma distância menor que , no qual no máximo oito pontos podem estar no retângulo . Por isso para cada ponto p, no mínimo sete pontos são checados para uma distância mínima.

O professor Williams fez um esquema que checa apenas cinco pontos. No esquema do professor a ideia é sempre colocar pontos sobre a reta I no conjunto P. Então não pode haver pares de pontos coincidentes sobre a reta I com um ponto em . Assim, no máximo seis pontos podem residir no retângulo .

Passo 4 de 4keyboard_arrow_downkeyboard_arrow_up

Portanto, o esquema do professor Williams de checar apenas cinco pontos ao invés de sete na matriz Y’ funciona o suficiente para o problema dos pares mais próximos, porém para uma certeza absoluta, checar todos os pontos seria o mais correto.

Navegar por capítulo

Depoimentos de estudantes que já assinaram o Exercícios Resolvidos

Nathalia Nascimento fez um comentárioCEFET/RJ • Engenharia
Foi um apoio àquelas aulas que não acabam totalmente com as dúvidas ou mesmo naquele momento de aprender o conteúdo sozinha. Além disso, dispensou a necessidade de um orientador e por isso, permitiu que eu estudasse em qualquer local e hora.
Valdivam Cardozo fez um comentárioUFRB • Engenharia
Tive uma sensação maior de autonomia nos estudos, as vezes era frustante não conseguir resolver uma determinada questão e nem sempre os professores corrigem as listas que passam.