M04A18 – Busca Binária em Vetores – Módulo 04: Variáveis compostas

Home Fóruns Programação Básica M04A18 – Busca Binária em Vetores – Módulo 04: Variáveis compostas

Visualizando 9 respostas da discussão
  • Autor
    Posts
    • #64215
      Filipe Gaspar
      Participante

      Durante a aula M04A18 – Busca Binária em Vetores. É apresentada uma lógica que se no caso de a chave a ser pesquisada ser o ultimo item do vetor, esta vai retornar um erro que não foi encontrada.

      enquanto(ini < fim){
      
      Para solucionar este erro contrui a minha lógica da forma abaixo indicada
      
      
      
      programa
      {
      	inclua biblioteca Util
      	funcao inicio()
      	{
      	//A busca binária só funciona se o vetor estiver em ordem
      		
      		inteiro vet[10]
      		inteiro pos = 0
      		logico encontrado
      
      		//Ciclo para preeencher o vetor com números aleatórios
      		enquanto(pos < Util.numero_elementos(vet)){
      			vet[pos] = sorteia(1,20)
      			encontrado = falso //na primeira execução o valor não é repetido
      			para(inteiro i = 0; i < pos; i++){ // Ciclo vai da posição 0 até á ultima posição onde foi gerado um número
      				se(vet[pos] == vet[i]){ //Se o valor for igual vamos gerar um novo valor 
      					encontrado = verdadeiro //encontrou o valor impede o incremento da posição no vetor
      				}
      			}
      			se(nao encontrado){ //só incrementa a posição se o valor não for repetido ou seja não foi encontrado
      				pos++
      			}	
      		}
      
      		//ciclo para mostar o vetor gerado
      		escreva("-----------------------------------\n")
      		escreva("O vetor gerado foi: \n")		
      		para(inteiro p = 0; p < Util.numero_elementos(vet); p++){
      			Util.aguarde(300)
      			escreva(vet[p],"  ")
      		}
      		escreva("\n")
      
      		//Ordenando o vetor
      		inteiro aux = 0 //variavel auxiliar para a ordenação do vetor
      		escreva("\n======================================================== \n")
      		escreva(" Estou a colocar em ordem crescente! Por favor aguarde! \n")
      		Util.aguarde(1500)
      		
      		para(inteiro p = 0; p < (Util.numero_elementos(vet)-1); p++){ //Ciclo para o ponteiro principal que vai da posição 0 até á Penúltimo posição. Que ocorre imediatamente antes do último 
      			para(inteiro s = (p+1); s < Util.numero_elementos(vet); s++){ //Ciclo para o ponteiro secundário que vai da posição p + 1, posição seguinte ao p, até ao ultimo elemento do vetor
      				se(vet[p] > vet[s]){ //Na primeira execuçaõ verifica se vet[0] é menor que vet[1] se for faz a troca ou swap, e assim consecutivamente vet[1] é menor que vet[2] até terminar o ciclo
      					aux = vet[p]
      					vet[p] = vet[s]
      					vet[s] = aux			
      				}
      			}
      		}
      
      		//Mostra o vetor por ordem crescente
      		escreva("\n--------------------------------------- \n")
      		escreva("O vetor colocado em ordem Crescente: \n")		
      		para(inteiro p = 0; p < Util.numero_elementos(vet); p++){
      			Util.aguarde(300)
      			escreva(vet[p],"  ")
      		}
      		escreva("\n")
      
      		//Busca binária
      		//A busca binária só funciona se o vetor estiver em ordem crescente
      		inteiro chave
      		logico encontrouChave
      		escreva("\n------------------------------------- \n")
      		escreva("Qual número deseja perquisar: ")
      		leia(chave)
      		encontrouChave = falso //até agora ainda não encontrou a chave
      		inteiro ini = 0, fim = (Util.numero_elementos(vet)-1), meio = 0
      		
      		enquanto(ini <= fim){ //Alteração necessária para encontrar a chave no caso de esta estar no ultimo índice do vetor 
      			meio = (ini + fim) / 2//Calculo do meio do vetor
      			se(vet[meio] == chave){
      				encontrouChave = verdadeiro
      				pare//como encontrou a chave vai parar o ciclo
      			}senao{
      				se(chave > vet[meio]){ //se o valor da chave for maior que o valor no vetor na posição meio
      					ini = meio +1
      				}senao{ //se o valor da chave for menor que o valor no vetor na posição meio
      					fim = meio -1
      				}
      			}
      		}
      
      		se(encontrouChave){ //Verifica se encontrou a chave dentro do vetor
      			escreva("\n")
      			escreva("O valor ", chave, " foi encontrado na posição ", meio, "\n")
      		}senao{
      			escreva("\n")
      			escreva("Infelizmente o valor ", chave, " não foi encontrado no vetor! \n")
      		}
      		
      	}
      }
      
    • #64227
      IcaroFilho
      Moderador

      Bom dia. não entendi o que quis dizer.
      Esta falando que na resolução do exercício, o método proposto acarreta em falha caso o ultimo item seja a chave ?
      e que fez um outro código que corrige este fator ?

      Por favor, posta ele em formato de código. Pq desse modo ai da muito trabalho pra corrigir e por no portugol

    • #64229
      Filipe Gaspar
      Participante

      É isso mesmo na resolução do exercício, o método proposto acarreta em falha caso o ultimo item seja a chave .
      Peço desculpa não ter colocado com código. Fica então o código com o meu exemplo de lógica que já tem o problema corrigido.

      programa
      {
      	inclua biblioteca Util
      	funcao inicio()
      	{
      	//A busca binária só funciona se o vetor estiver em ordem crescente
      		
      		inteiro vet[10]
      		inteiro pos = 0
      		logico encontrado
      
      		//Ciclo para preeencher o vetor com números aleatórios
      		enquanto(pos < Util.numero_elementos(vet)){
      			vet[pos] = sorteia(1,20)
      			encontrado = falso //na primeira execução o valor não é repetido
      			para(inteiro i = 0; i < pos; i++){ // Ciclo vai da posição 0 até á ultima posição onde foi gerado um número
      				se(vet[pos] == vet[i]){ //Se o valor for igal vamos gerar um novo valor 
      					encontrado = verdadeiro //encoutrou o valor impede o incremento da posição no vetor
      				}
      			}
      			se(nao encontrado){ //só incrementa a posição se o valor não for repetido ou seja não foi encontrado
      				pos++
      			}	
      		}
      
      		//ciclo para mostar o vetor gerado
      		escreva("-----------------------------------\n")
      		escreva("O vetor gerado foi: \n")		
      		para(inteiro p = 0; p < Util.numero_elementos(vet); p++){
      			Util.aguarde(300)
      			escreva(vet[p],"  ")
      		}
      		escreva("\n")
      
      		//Ordenando o vetor
      		inteiro aux = 0 //variavel auxiliar para a ordenação do vetor
      		escreva("\n======================================================== \n")
      		escreva(" Estou a colocar em ordem crescente! Por favor aguarde! \n")
      		Util.aguarde(1500)
      		
      		para(inteiro p = 0; p < (Util.numero_elementos(vet)-1); p++){ //Ciclo para o ponteiro principal que vai da posição 0 até á Penúltimo posição. Que ocorre imediatamente antes do último 
      			para(inteiro s = (p+1); s < Util.numero_elementos(vet); s++){ //Ciclo para o ponteiro secundário que vai da posição p + 1, posição seguinte ao p, até ao ultimo elemento do vetor
      				se(vet[p] > vet[s]){ //Na primeira execuçaõ verifica se vet[0] é menor que vet[1] se for faz a troca ou swap, e assim consecutivamente vet[1] é menor que vet[2] até terminar o ciclo
      					aux = vet[p]
      					vet[p] = vet[s]
      					vet[s] = aux			
      				}
      			}
      		}
      
      		//Mostra o vetor por ordem crescente
      		escreva("\n--------------------------------------- \n")
      		escreva("O vetor colocado em ordem Crescente: \n")		
      		para(inteiro p = 0; p < Util.numero_elementos(vet); p++){
      			Util.aguarde(300)
      			escreva(vet[p],"  ")
      		}
      		escreva("\n")
      
      		//Busca binária
      		//A busca binária só funciona se o vetor estiver em ordem crescente
      		inteiro chave
      		logico encontrouChave
      		escreva("\n------------------------------------- \n")
      		escreva("Qual número deseja perquisar: ")
      		leia(chave)
      		encontrouChave = falso //até agora ainda não encontrou a chave
      		inteiro ini = 0, fim = (Util.numero_elementos(vet)-1), meio = 0
      		
      		enquanto(ini <= fim){
      			meio = (ini + fim) / 2//Calculo do meio do vetor
      			se(vet[meio] == chave){
      				encontrouChave = verdadeiro
      				pare//como encontrou a chave vai parar o ciclo
      			}senao{
      				se(chave > vet[meio]){ //se o valor da chave for maior que o valor no vetor na posição meio
      					ini = meio +1
      				}senao{ //se o valor da chave for menor que o valor no vetor na posição meio
      					fim = meio -1
      				}
      			}
      		}
      
      		se(encontrouChave){ //Verifica se encontrou a chave dentro do vetor
      			escreva("\n")
      			escreva("O valor ", chave, " foi encontrado na posição ", meio, "\n")
      		}senao{
      			escreva("\n")
      			escreva("Infelizmente o valor ", chave, " não foi encontrado no vetor! \n")
      		}
      		
      	}
      }
      

      Bons estudos.
      Peço desculpa ainda não tinha utilizado o fórum.

    • #64231
      Filipe Gaspar
      Participante

      Peço por favor que se possível seja removido o post anterior tentei colocar como código mas sem sucesso. peço desculpa pelo sucedido.

      É isso mesmo na resolução do exercício, o método proposto acarreta em falha caso o ultimo item seja a chave .
      Peço desculpa não ter colocado com código. Fica então o código com o meu exemplo de lógica que já tem o problema corrigido.

      programa
      {
      	inclua biblioteca Util
      	funcao inicio()
      	{
      	//A busca binária só funciona se o vetor estiver em ordem crescente
      		
      		inteiro vet[10]
      		inteiro pos = 0
      		logico encontrado
      
      		//Ciclo para preeencher o vetor com números aleatórios
      		enquanto(pos < Util.numero_elementos(vet)){
      			vet[pos] = sorteia(1,20)
      			encontrado = falso //na primeira execução o valor não é repetido
      			para(inteiro i = 0; i < pos; i++){ // Ciclo vai da posição 0 até á ultima posição onde foi gerado um número
      				se(vet[pos] == vet[i]){ //Se o valor for igal vamos gerar um novo valor 
      					encontrado = verdadeiro //encoutrou o valor impede o incremento da posição no vetor
      				}
      			}
      			se(nao encontrado){ //só incrementa a posição se o valor não for repetido ou seja não foi encontrado
      				pos++
      			}	
      		}
      
      		//ciclo para mostar o vetor gerado
      		escreva("-----------------------------------\n")
      		escreva("O vetor gerado foi: \n")		
      		para(inteiro p = 0; p < Util.numero_elementos(vet); p++){
      			Util.aguarde(300)
      			escreva(vet[p],"  ")
      		}
      		escreva("\n")
      
      		//Ordenando o vetor
      		inteiro aux = 0 //variavel auxiliar para a ordenação do vetor
      		escreva("\n======================================================== \n")
      		escreva(" Estou a colocar em ordem crescente! Por favor aguarde! \n")
      		Util.aguarde(1500)
      		
      		para(inteiro p = 0; p < (Util.numero_elementos(vet)-1); p++){ //Ciclo para o ponteiro principal que vai da posição 0 até á Penúltimo posição. Que ocorre imediatamente antes do último 
      			para(inteiro s = (p+1); s < Util.numero_elementos(vet); s++){ //Ciclo para o ponteiro secundário que vai da posição p + 1, posição seguinte ao p, até ao ultimo elemento do vetor
      				se(vet[p] > vet[s]){ //Na primeira execuçaõ verifica se vet[0] é menor que vet[1] se for faz a troca ou swap, e assim consecutivamente vet[1] é menor que vet[2] até terminar o ciclo
      					aux = vet[p]
      					vet[p] = vet[s]
      					vet[s] = aux			
      				}
      			}
      		}
      
      		//Mostra o vetor por ordem crescente
      		escreva("\n--------------------------------------- \n")
      		escreva("O vetor colocado em ordem Crescente: \n")		
      		para(inteiro p = 0; p < Util.numero_elementos(vet); p++){
      			Util.aguarde(300)
      			escreva(vet[p],"  ")
      		}
      		escreva("\n")
      
      		//Busca binária
      		//A busca binária só funciona se o vetor estiver em ordem crescente
      		inteiro chave
      		logico encontrouChave
      		escreva("\n------------------------------------- \n")
      		escreva("Qual número deseja perquisar: ")
      		leia(chave)
      		encontrouChave = falso //até agora ainda não encontrou a chave
      		inteiro ini = 0, fim = (Util.numero_elementos(vet)-1), meio = 0
      		
      		enquanto(ini <= fim){
      			meio = (ini + fim) / 2//Calculo do meio do vetor
      			se(vet[meio] == chave){
      				encontrouChave = verdadeiro
      				pare//como encontrou a chave vai parar o ciclo
      			}senao{
      				se(chave > vet[meio]){ //se o valor da chave for maior que o valor no vetor na posição meio
      					ini = meio +1
      				}senao{ //se o valor da chave for menor que o valor no vetor na posição meio
      					fim = meio -1
      				}
      			}
      		}
      
      		se(encontrouChave){ //Verifica se encontrou a chave dentro do vetor
      			escreva("\n")
      			escreva("O valor ", chave, " foi encontrado na posição ", meio, "\n")
      		}senao{
      			escreva("\n")
      			escreva("Infelizmente o valor ", chave, " não foi encontrado no vetor! \n")
      		}
      		
      	}
      }
      
    • #64233
      Filipe Gaspar
      Participante

      Peço desculpa pela falta de formatação do código tentei colocar como code mas não funcionou, peço desculpa por esse fato.
      Solicito que o post seja apagado do fórum, afim de evitar poluição visual do mesmo.
      Peço desculpa pelo sucedido mas não consigo editar o post afim de corrigir o problema.

      • #64253
        IcaroFilho
        Moderador

        Eu geralmente faço o seguinte.
        Copio o codigo normalmente do IDLE para o forum (ele vai vir com os espaços certinhos.
        seleciono todo o codigo e clico em CODE na aba de formatação.
        isso fara com que seja posto a abertura e fechamento da formatação de uma vez (serve para todos as formatações)

    • #64435
      Tutora Mayla
      Mestre

      Filipe, realmente há uma erro na resolução dessa questão. Na página da aula, acima do vídeo há uma aba Materiais onde há uma errata falando qual é o erro e a resposta certa.
      Sempre fiquem atentos a esta aba, há informações importantes lá como possíveis erratas e possíveis materiais para downloads.

      O erro se encontra nos minutos 10:50.
      O erro está na linha 47:
      Onde está enquanto(ini < fim) deveria ser enquanto(ini <= fim).

      Espero ter ajudado, quaisquer outras dúvidas estamos a disposição.

    • #71584
      Bernardo Costa
      Participante

      No final do exemplo quando eu vou testar a posição 0 e a 9 quando vou pedir para ele achar o valor da erro fala que o valor não se encontra mas ele esta ali pode me explicar porque nessas posições da ele não acha?

      • #71600
        Tutora Mayla
        Mestre

        Bernardo, mesclei o seu tópico com um já existente sobre o assunto, antes de criar um tópico sempre procure se já existe um tópico sobre o assunto.
        Veja a discussão que ocorreu neste tópico sobre essa aula, aqui informo que ouve um erro na aula e a errata se encontra na aba Materiais. Veja se isso resolve sua dúvida, caso ainda haja dúvidas volte a entrar em contato que lhe ajudaremos.

    • #109640
      Carol Protásio
      Participante

      Olá!!
      Na explicação da aula sobre busca binária(M04A18) prof. Gustavo demostrou como fazer essa busca, porém se procurarmos pela o valor da chave que esteja na posição: ini ou fim, dá erro(chave não encontra-se no vetor). Consegui resolver colocando:
      se(vet[meio] == chave ou chave == vet[ini] ou chave == vet[fim])
      porém, para mostrar o resultado da busca, estou tendo dificuldade de mostrar a posição da chave, já que não podemos escrever a variavel “meio”, já que por ex. a chave estava na posição ini(ou fim):
      se(encontrado){
      escreva(“\nO valor “+chave+” foi encontrado na posição “+meio+” do vetor”)
      }senao{
      escreva(“\nInfelizmente o valor “+chave+” não se encontra no vetor”)

      minha dúvida é: no escreva(no se(encontrado)) como coloco a posição, já que pode ser: meio, fim, ou ini?
      segue abaixo todo o cod:
      Obrigada!!!

      inteiro vet[10]
      inteiro p=0, aux, i
      logico encontrado

      enquanto(p < u.numero_elementos(vet)){
      vet[p] = sorteia(1,15)
      encontrado = falso
      para(aux=0; aux < p;aux++){
      se(vet[aux] == vet[p]){
      encontrado = verdadeiro
      pare
      }
      }
      se(nao encontrado){
      p++
      }
      }

      inteiro auxiliar = 0, pr, sec
      para(pr=0; pr < u.numero_elementos(vet);pr++){
      para(sec=pr+1;sec<u.numero_elementos(vet);sec++){
      se(vet[pr]>vet[sec]){
      auxiliar=vet[pr]
      vet[pr]=vet[sec]
      vet[sec]=auxiliar

      }
      }
      }

      para(i=0;i<u.numero_elementos(vet);i++){
      escreva(vet[i]+” “)
      u.aguarde(100)
      }

      //busca binaria
      inteiro chave
      inteiro ini=0, fim = u.numero_elementos(vet)-1, meio=0
      encontrado = falso
      escreva(“\nQuer achar que valor? “)
      leia(chave)

      enquanto(ini < fim){
      meio = (ini+fim)/2
      se(vet[meio] == chave ou chave == vet[ini] ou chave == vet[fim]){
      encontrado = verdadeiro
      pare
      }senao{
      se(chave > vet[meio]){
      ini = meio + 1
      }senao{
      fim = meio – 1
      }

      }
      }
      se(encontrado){
      escreva(“\nO valor “+chave+” foi encontrado na posição “+meio+” do vetor”)
      }senao{
      escreva(“\nInfelizmente o valor “+chave+” não se encontra no vetor”)
      }

    • #109644
      Tutora Jessica
      Moderador

      Ola Carol,
      Trouxe a sua dúvida para uma já existente no fórum, aqui contém algumas explicações que acredito que vá lhe ajudar.
      Peço para que sempre que for compartilhar sua dúvida , veja se já não há uma existente no fórum e também nos envie seu código identado, selecionando o mesmo por completo e clicando em CODE.

      • #109672
        Carol Protásio
        Participante

        Obrigada Jessica por essa correção na identação e post na area correta, realmente procurei e não achei.. facilitaria um campo de busca no forum 🙂
        De qualquer forma, vc entendeu minha dúvida? ainda não consegui resolver… agradeço sua atenção

    • #109680
      Tutora Jessica
      Moderador

      Ola Carol, você pode me explicar melhor ?
      Você chegou a ver o adendo de errata na aba materiais dessa aula ?

Visualizando 9 respostas da discussão
  • Você deve fazer login para responder a este tópico.