Busca Linear com Recursividade

9 respostas
A

Bom dia galera!! Estou comecando a programar em Java e to com uma duvida em recursividade.

estou tentando fazer uma busca linear usando um metodo recursivo, mas sempre q eu rodo o programa ele informa q nao encontrou o nº mesmo tendo o nº no vetor. estou enviando o codigo do programa para que vcs possam me ajudar indicando o erro.

valeu

import javax.swing.*;
public class Ex32rec

{

public static void main(String[] args) 

{
	//declaracao de variaveis
	String snum, sout = "O nº foi encontrado no índice: ";
	int ivet[] = new int[15];
	int ivc, ibusca, iresp;
	
	//preenchimento do vetor
	for(ivc=0; ivc<=14; ivc++)
	{
		snum = JOptionPane.showInputDialog("Digite um nº");
		ivet[ivc]= Integer.parseInt(snum);
	}
	
	//solicita um nº a ser buscado no vetor		
	snum = JOptionPane.showInputDialog("Digite um nº a ser buscado");
	ibusca= Integer.parseInt(snum);
	
	
	//preenche a saida
	sout+= ""+ buscaLinearrec(ivet, ibusca, ivc);
	
	JOptionPane.showMessageDialog(null, sout);
	System.exit(0);
}


//metodo que localiza o nº no vetor de forma RECURSIVA
public static int buscaLinearrec(int ivetp[], int iproc, int iind)
{
	
	if (iind >= ivetp.length)
		return -1;
	
	if(ivetp[iind] == iproc)
		return buscaLinearrec(ivetp,iproc,iind+1);
	return iind;
		
										
}

}

9 Respostas

P

Onde:

"andrerios":
//preenche a saida
sout+= ""+ buscaLinearrec(ivet, ibusca, ivc);

Coloque:
//preenche a saida
sout+= ""+ buscaLinearrec(ivet, ibusca, 0);

Para fazer a busca a partir da primeira posição do vetor, pois vc está incrementando o índice do vetor na chamada recursiva

"andrerios":
return buscaLinearrec(ivetp,iproc,iind+1);

Outra coisa, o código estava fazendo a chamada recusiva quando encontrava o valor procurado... deveria ser o contrário, como segue:
//metodo que localiza o nº no vetor de forma RECURSIVA 
public static int buscaLinearrec(int ivetp[], int iproc, int iind) 
{ 

if (iind >= ivetp.length) 
return -1; 
System.out.println(" A:ivetp["+iind+"] = "+ivetp[iind]+" - "+iproc);
if(ivetp[iind] == iproc) 
return iind; 
else
return buscaLinearrec(ivetp,iproc,iind+1); 


}
Tente usar o System.out.println pra ver exatamente o q o código tah fazendo... fica bem mais fácil... :grin:

Abs

A

Valeu Patty!!!

A

Patty ( ou quem puder ajudar) e no caso de haver numeros repeitods e eu quiser mostrar os indices do vetor q eles estao. ex:

indice: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
valor: 1 2 3 4 5 6 7 8 9 10 1 12 1 14 1

se o nº buscado for 1
a resposta deve conter os indices 0, 10, 12 e 14

valeu galera!!!

P

Ao invés de chamar a buscaLinearrec, chama essa função no main...

//metodo que localiza o nº no vetor de forma RECURSIVA 
public static int[] buscaLinearrecVector(int ivetp[], int iproc, int ind) 
{ 
	int[] resp = new int[ivetp.length];//tamanho máximo da resposta
	int cont=0;
	while(ind < ivetp.length){
		resp[cont] = buscaLinearrec(ivetp, iproc, ind);
		if(resp[cont] == -1)//naum encontrou mais registros
			return resp;
		
		ind = resp[cont]+1;//faz com que a próxima busca parta da posição em que foi
		//encontrado da última vez, uma posição à frente
		
		System.out.println(" resp["+cont+"] = "+resp[cont]);
		
		cont++;
	}		
	return resp;
}

Tem como melhorar e muito essa função, tipo: fazendo alocação dinâmica no vetor resp pra naum ocupar memória sem necessidade... Mas funciona... :O)

Qualquer dúvida q tiver, eh soh dizer... terei prazer em esclarecer... :grin:

A

Valeu denovo Patty!!! estou começando agora, mas espero em breve poder colaborar aki no portal java tb hehehe

abraco

A

Patty, esse metodo q vc me enviou nao esta funcionando :sad: está dando problema na hora q ele chama o metodo dentro do metodo.

estou procurando mais artigos sobre esse problema mas nao estou conseguindo encontrar. desculpa o incomodo hhehe

abraco

A

Alguem me ajuda por favor!!! hehehehe galera tenho prova desse assunto segunda feira e preciso rachar a cuca no fim de semana estudando… alguem tem ou sabe aonde tem material sobre recursividade em java??

valeu!!

P

naum desespera... recursao naum eh coisa pra entender, e sim pra aceitar... hehehe

abaixo a mutação:

import javax.swing.*; 
public class PJ1 

{ 

public static void main(String[] args) 

{ 
//declaracao de variaveis 
String snum, sout = "O  foi encontrado no índice: "; 
int ivet[] = new int[5]; 
int ivc, ibusca, iresp; 

//preenchimento do vetor 
for(ivc=0; ivc<5; ivc++) 
{ 
snum = JOptionPane.showInputDialog("Digite um "); 
ivet[ivc]= Integer.parseInt(snum); 
} 

//solicita um nº a ser buscado no vetor 
snum = JOptionPane.showInputDialog("Digite um  a ser buscado"); 
ibusca= Integer.parseInt(snum); 


//preenche a saida 
int[] indices = buscaLinearrecVector(ivet, ibusca, 0);
sout+= ""+conversorString(indices);

JOptionPane.showMessageDialog(null, sout); 
System.exit(0); 
} 

public static String conversorString(int[] array){
 StringBuffer str = new StringBuffer();
 int size = array.length;
 for(int i=0; i<size; i++){
 	str.append(String.valueOf(array[i])).append(",");
 }
 return str.toString();
}

//metodo que localiza o nº no vetor de forma RECURSIVA 
public static int buscaLinearrec(int ivetp[], int iproc, int iind) 
{ 

if (iind >= ivetp.length) 
return -1; 
System.out.println(" A:ivetp["+iind+"] = "+ivetp[iind]+" - "+iproc);
if(ivetp[iind] == iproc) 
return iind; 
else
return buscaLinearrec(ivetp,iproc,iind+1); 


} 


//metodo que localiza o nº no vetor de forma RECURSIVA 
public static int[] buscaLinearrecVector(int ivetp[], int iproc, int ind) 
{ 
	int[] resp = new int[ivetp.length];//tamanho máximo da resposta
	int cont=0;
	while(ind < ivetp.length){
		resp[cont] = buscaLinearrec(ivetp, iproc, ind);
		if(resp[cont] == -1){//naum encontrou mais registros
		  int[] respFinal = new int[cont];
		  System.out.println("Terminou");
		  for(int i=0; i<cont; i++){
		  	System.out.println("#"+resp[i]);
		  	 respFinal[i] = resp[i];}
			return respFinal;
		}
		
		ind = resp[cont]+1;//faz com que a próxima busca parta da posição em que foi
		//encontrado da última vez, uma posição à frente
		
		System.out.println(" resp["+cont+"] = "+resp[cont]);
		
		cont++;
	}		
	int[] respFinal = new int[cont];
	System.out.println("Terminou");
	for(int i=0; i<cont; i++){
		System.out.println("#"+resp[i]);
		respFinal[i] = resp[i];}
	return respFinal;
} 

}
A

Patty mais uma vez muito obrigado!!! só nao entendi muito bem esse conversor de String mas vou dar uma pesquisada.
valeu

Criado 28 de março de 2005
Ultima resposta 1 de abr. de 2005
Respostas 9
Participantes 2