Logo Hardware.com.br
klaus_wild
klaus_wild Novo Membro Registrado
24 Mensagens 1 Curtida

Duvida em exercicio de busca

#1 Por klaus_wild 30/11/2019 - 16:04
Boa tarde! Venho aqui hoje com mais uma duvida, dessa vez em métodos de busca.
Bem, estou tentando fazer uma busca ponderada/interpolada e testei vários algorítimos que a gente acha por ai e não estou tendo sucesso.
Meu código:
"codigo"

void busca_ponderada(int *vetA, int *vetB)

{

int inicio,fim,pos,i,cont=0;



for(i=0;i<=tamanhoA;++i)

{



inicio = 0;

fim=tamanhoB;



while(inicio <= fim && vetA[i] >= vetB[inicio] && vetA[i] <= vetB[fim])

{



pos = inicio + (vetA[i] - vetB[inicio]) * ((fim - inicio) / (vetB[fim] - vetB[inicio]));





if (vetB[pos] < vetA[i])

inicio = pos + 1;



else

fim = pos - 1;



}



if (vetB[pos] == vetA[i])

cont++;

}


printf("existem %d elementos do vetor A presentes no vetor B\n",cont);



//tamanhaA=2000;
//tamanhoB=200000;
}


O problema seria que ele esta achando apenas 1 resultado na busca, quando era pra achar um pouco mais de 4.000 resultados (testei com outros métodos de busca, com a mesma seed, e todos tem o mesmo valor). Nao sei se o problema esta na equação ou no while. Ja tentei muda o valor do inicio, do fim e etc, mas ainda nada.
Alguma ideia?
esquiloesperto
esquiloesper... Cyber Highlander Moderador
7.1K Mensagens 2.2K Curtidas
#2 Por esquiloesper...
01/12/2019 - 04:10
Este algoritmo somente encontra algum resultado quando tudo estiver ordenado.
Assim, provavelmente a causa do problema encontrado é devido às listas (vetores) se encontrarem desordenadas.

E mesmo ordenadas, ele falha terrivelmente nas projeções.
Minha sugestão é que parta para algo mais simples, porque problemas dessa ordem atrasam bastante o seu aprendizado.

E a falha mais grosseira está o trecho corrigido a seguir, porque como estava lixo era coletado na memória (out-of-bounds):
[code=c]fim = tamanhoB-1;
while ((inicio < fim)...
[/code]
Só é difícil enquanto estiver oculto! cool.png
Use a pesquisa


rolleyes.png  Navegar é preciso, viver... também.  smile.png
klaus_wild
klaus_wild Novo Membro Registrado
24 Mensagens 1 Curtida
#3 Por klaus_wild
01/12/2019 - 10:51
esquiloesperto disse:
Este algoritmo somente encontra algum resultado quando tudo estiver ordenado.
Assim, provavelmente a causa do problema encontrado é devido às listas (vetores) se encontrarem desordenadas.

E mesmo ordenadas, ele falha terrivelmente nas projeções.
Minha sugestão é que parta para algo mais simples, porque problemas dessa ordem atrasam bastante o seu aprendizado.

E a falha mais grosseira está o trecho corrigido a seguir, porque como estava lixo era coletado na memória (out-of-bounds):
[code=c]fim = tamanhoB-1;
while ((inicio < fim)...
[/code]


Quanto a escolha do metodo de busca...bem, nao tenho muita liberdade, pois foi o que o professor passou kkkk
Ah, e o vetor esta ordenado, eu esqueci de falar, erro meu aqui eek.png
Vou corrigir da maneira q vc falou e dar umas testadas. Muito obrigado!
© 1999-2024 Hardware.com.br. Todos os direitos reservados.
Imagem do Modal