• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Thorondor

Pesquisa binária com ciclo For

11 mensagens neste tópico

Oi pessoal, estou programando em MATLAB, mais propriamente num Bloco da System generator que usa MATLAB, mas as funções são limitadas, e queria fazer uma pesquisa binária de um vector, com as seguintes condicionantes impostas pelo próprio bloco:

- Apenas posso usar fors e ifs;

- No ciclo for, a variavel que é incrementada (por exemplo o i de "for i=1:x", não pode ser mudada dentro do ciclo;

- Apenas posso dividir por números de base 2;

- Existem mais, mas não m lembro de mais nenhuma relevante.

Obrigado desde já pela vossa atenção e tempo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu nunca trabalhei com matlab, mas posso tentar ajudar com a lógica.

Suponho que saibas o que é uma pesquisa binária?

Não podes ter outra variável além da variável do ciclo e poder interromper o ciclo quando terminas a pesquisa? É que só com uma variável incrementada 1 a 1, não creio que se possa fazer uma pesquisa binária.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Continuo sem saber se sabes como se faz uma pesquisa binária, é que se sim, o que vou dizer não deve servir de nada pois não podes implementar devido às restrições a que estás sujeito.

Assumindo que tens um vector V com N elementos já ordenados de forma crescente e pretendes saber se um valor X se encontra no vector, são necessárias mais 3 variáveis: left , right e mid.

Não sei se os indices começam em 0 ou 1, assumindo que começam em 0:

left = 0 , right = N-1;

for i=1:N  // não podem existir N iterações na pesquisa binária, é apenas para termos um ciclo
     mid = (left + right) / 2 ; // 2 é potência de 2, não tens problema
     if ( V[mid] < X )
             right = mid-1 ;  // resposta encontra-se no intervalo [ left , mid [
     else if ( V[mid] > X )
             left = mid+1 ;  // resposta encontra-se no intervalo ] mid , right ]
     else 
             quebra o ciclo pois encontramos o valor na posição mid

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O problema disso é que o mid vai acabar por ter um valor decimal, e não consegues obter uma célula dum vector com casa decimal

Por isso tenho de verificar se o mid é par ou impar pelo caminho, e não tenho nenhuma função especifica para isso :S

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Função que verifica se 'mid' é par ou ímpar com ciclo for:

par=1;
for i=1:mid
    par=1-par;
end

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Engraçada essa, hehehe.

Mas já resolvi o problema, verificando o último bit s é 0 ou 1, mas obrigado fica guardada ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Agora o problema reside em descobrir qts vezes eu tenho d correr o ciclo, d maneira a conseguir poupar o máximo instruções :S

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu pensei que tinhas a divisao inteira disponivel, daí não haver problemas com casas decimais.

O ciclo corre em O( log N ). O ideal era parar o ciclo como eu disse, não podes fazer isso em matlab? É que senão vais estar quase sempre a fazer iterações a mais..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Espera lá... Mas tu não podes criar uma função e chamá-la recursivamente porquê?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Porque só posso usar uma função, q é a q o bloco vai chamar, é mt limitada a programaçã neste bloco :S

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora