Binærsøking med rekursjon litt problemer

[TeisL]

Hei!

 

Jeg driver å trener litt på å bruke binærsøking til å finne et tall (eller at det evt ikke finnes) fra en array. Tallene i arrayen er lest inn fra fil.

 

Her er koden og problemet er formulert ubder:

 

public class Tabell_mainpanel extends JPanel {

JLabel innTall_beskrivelse;

JLabel search_beskrivelse;

JTextField innTall_input;

JTextField search_result;

String line = "Tall";

int[] tabell = new int[100];

int nr = -1;

int forst = 0;

int sist;

int mid;

String resultat;

 

public Tabell_mainpanel(){

GridLayout gl = new GridLayout(3,2);

innTall_beskrivelse = new JLabel("Skriv inn et tall: ");

innTall_input = new JTextField("",20);

search_result = new JTextField(resultat,30);

search_beskrivelse = new JLabel("Søkeresultat: ");

search_result.enable(false);

sok();

this.setLayout(gl);

this.add(innTall_beskrivelse);

this.add(innTall_input);

this.add(search_beskrivelse);

this.add(search_result);

}

 

public void lastOpp(){

JFileChooser chooser = new JFileChooser();

chooser.setFileSelectionMode(JFileChooser.FILES_ONLY);

int result = chooser.showOpenDialog(null);

File fil = chooser.getSelectedFile();

String filnavn = fil.getAbsolutePath();

try{

File tallFil = new File(filnavn);

BufferedReader in = new BufferedReader(new FileReader(filnavn));

while(true){

if(line == null){

break;

}

else{

int teller = 0;

line = in.readLine();

int line_int = Integer.parseInt(line);

tabell[teller] = line_int;

}

}

in.close();

}

catch(Exception e){

 

}

 

public int binsok(int[] tabell, int sid, int forst, int sist){

if(forst <= sist){

int mid = (forst + sist)/2;

if(tabell[mid] > sid)

return binsok(tabell, sid, forst, mid -1);

else if(tabell[mid] < sid)

return binsok(tabell, sid, mid+1, sist);

else

return mid;

}

else

return -1;

 

}

public void sok(){

try{

int sid = Integer.parseInt(innTall_input.getText());

int nr = binsok(tabell, sid, 0, tabell.length-1);

if(nr >= 0)

search_result.setText(sid+" finnes i posisjon: "+nr);

else

search_result.setText(sid+" finnes ikke.");

}

catch(Exception ex){

search_result.setText("Skriv inn et tall.");

}

}

 

 

Prpblemet er at når jeg legger inn en .txt fil med en masse tall og skriver et tall jeg ønsker å søke etter i innTall_input så hopper metoden sok() rett ned i catch'en med en gang. Men jeg skjønner ikke hvorforfor ikke

int sid = Integer.parseInt(innTall_input.getText()); får gjort om innTall_input til int slik at sok() kan gå i try boksen.

 

Er det noen andre som ser hva jeg har gjort feil??

 

Takker på forhånd;)

[pgdx]

Legg ut kildekoden indentert inni code-blokk:

public class TableMainPanel extends JPanel {
  private JLabel inNumberDescription;
  private JLabel searchDescription;
  private JTextField inNumberInput;
  private JTextField searchResult;
  private String line = "Tall";
  private int[] table = new int[100];
  private int number = -1;
  private int first = 0;
  private int last;
  private int mid;
  private String result;

  // resten av koden

}

 

I tillegg må du lese opp på konvensjoner på variabel- og klassenavn slik at det blir enklere for andre Java-programmere å lese koden din. Og det er sterkt anbefalt å bruke engelske navn.

Endret 11. september 2008 av pgdx

[pgdx]

[...] hopper metoden sok() rett ned i catch'en [...]

Okey, er det noen grunn til at du catch-er Exception fremfor de mer spesifikke IO- og FileNotFoundException? Og hvorfor skriver du ikke ut unntaket?

   try {
  // filhåndtering ... 
  } catch (IOException ioe) {
  ioe.printStackTrace();
  } catch (FileNotFoundException fnfe) {
  fnfe.printStackTrace();
  }

 

Eventuelt NumberFormatException, hvis det er den som kastes.

Endret 11. september 2008 av pgdx

[TeisL]

Okei, har prøvd å gå igjennom å gjøre litt og legge koden i code block... Lagt på litt kommentarer også...

 

import java.awt.GridLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;

import javax.swing.JFileChooser;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JTextField;


public class Tabell_mainpanel extends JPanel {
//Initsialiseringer
JLabel innTall_beskrivelse;
JLabel search_beskrivelse;
JTextField innTall_input;
JTextField search_result;
String line = "Tall";
int[] tabell = new int[100];
int nr_int = -1;
int forst_int = 0;
int sist_int;
int mid_int;
String resultat_string;
//Konstruktør
public Tabell_mainpanel(){
	//Lager objekter
	GridLayout gl = new GridLayout(3,2);
	innTall_beskrivelse = new JLabel("Skriv inn et tall: ");
	innTall_input = new JTextField("",20);
	search_result = new JTextField(resultat_string,30);
	search_beskrivelse = new JLabel("Søkeresultat: ");
	//Engrer egenskaper til objektene
	search_result.enable(false);
	sok();
	//Legger til objekter
	this.setLayout(gl);
	this.add(innTall_beskrivelse);
	this.add(innTall_input);
	this.add(search_beskrivelse);
	this.add(search_result);
}//End konstruktør
//Innlesing fra fil
public void lastOpp(){
	JFileChooser chooser = new JFileChooser();
	chooser.setFileSelectionMode(JFileChooser.FILES_ONLY);
	int result = chooser.showOpenDialog(null);
	File fil = chooser.getSelectedFile();
	String filnavn = fil.getAbsolutePath();
	try{
		File tallFil = new File(filnavn);
		BufferedReader in = new BufferedReader(new FileReader(filnavn));
		while(true){
			if(line == null){
				break;
			}
			else{
				int teller = 0;
				line = in.readLine();
				int line_int = Integer.parseInt(line);
				tabell[teller] = line_int;
			}
		}
		in.close();
	}
	catch(Exception e){

	}
}//End innlesing
//binsok
public int binsok(int[] tabell, int sid, int forst, int sist){
	if(forst <= sist){
		int mid = (forst + sist)/2;
		if(tabell[mid] > sid)
			return binsok(tabell, sid, forst, mid -1);
		else if(tabell[mid] < sid)
			return binsok(tabell, sid, mid+1, sist);
		else
			return mid;
	}
	else
		return -1;

}//End binsok
public void sok(){//Setter igang å søke
	try{
		int sid = Integer.parseInt(innTall_input.getText());
		int nr = binsok(tabell, sid, 0, tabell.length-1);
		if(nr >= 0)
			search_result.setText(sid+" finnes i posisjon: "+nr);
		else
			search_result.setText(sid+" finnes ikke.");
	}
	catch(Exception ex){
		search_result.setText("Skriv inn et tall.");
	}
}
}//End class

 

Håper noen tar seg tid til å se igjennom...

 

På forhånd takk...

[pgdx]

Som sagt, printStackTrace() og post den her. Mest sannsynlig vil den hjelpe deg til å finne problemet, uansett.

[pgdx]

Dessuten benytter du både metoder som er deprecated og har en hel haug med uleste variabler. Leser du kompilatorens lament?

 

import java.awt.GridLayout;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

import javax.swing.JFileChooser;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JTextField;

public class TableMainPanel extends JPanel {
// Initsialiseringer
private JLabel inNumberDescription;

private JLabel searchDescription;

private JTextField inNumberInput;

private JTextField searchResult;

private int[] table = new int[100];

private String resultString;

// Konstruktør
public TableMainPanel() {
	// Lager objekter
	GridLayout gl = new GridLayout(3, 2);
	inNumberDescription = new JLabel("Skriv inn et tall: ");
	inNumberInput = new JTextField("", 20);
	searchResult = new JTextField(resultString, 30);
	searchDescription = new JLabel("Søkeresultat: ");
	// Engrer egenskaper til objektene
	searchResult.enable(false);
	sok();
	// Legger til objekter
	this.setLayout(gl);
	this.add(inNumberDescription);
	this.add(inNumberInput);
	this.add(searchDescription);
	this.add(searchResult);
}// End konstruktør

// Innlesing fra fil

public void lastOpp() {
	JFileChooser chooser = new JFileChooser();
	chooser.setFileSelectionMode(JFileChooser.FILES_ONLY);
	File fil = chooser.getSelectedFile();
	String filnavn = fil.getAbsolutePath();

	try {
		FileReader fr = new FileReader(filnavn);
		BufferedReader br = new BufferedReader(fr);
		String tmp = "";
		while ((tmp = br.readLine()) != null) {
			int teller = 0;
			int line_int = Integer.parseInt(tmp);
			table[teller] = line_int;
		}
		br.close();
		fr.close();
	} catch (NumberFormatException e) {
		e.printStackTrace();
	} catch (FileNotFoundException e) {
		e.printStackTrace();
	} catch (IOException e) {
		e.printStackTrace();
	}
}// End innlesing

// binsok

public int binsok(int[] tabell, int sid, int forst, int sist) {
	if (forst <= sist) {
		int mid = (forst + sist) / 2;
		if (tabell[mid] > sid) {
			return binsok(tabell, sid, forst, mid - 1);
		} else if (tabell[mid] < sid) {
			return binsok(tabell, sid, mid + 1, sist);
		} else {
			return mid;
		}
	} else {
		return -1;
	}

}// End binsok

public void sok() {// Setter igang å søke
	try {
		int sid = Integer.parseInt(inNumberInput.getText());
		int nr = binsok(table, sid, 0, table.length - 1);
		if (nr >= 0)
			searchResult.setText(sid + " finnes i posisjon: " + nr);
		else
			searchResult.setText(sid + " finnes ikke.");
	} catch (Exception ex) {
		ex.printStackTrace();
		searchResult.setText("Skriv inn et tall.");
	}
}
}// End class

Endret 11. september 2008 av pgdx

[nirolo]

Hei!

 

Jeg driver å trener litt på å bruke binærsøking til å finne et tall (eller at det evt ikke finnes) fra en array. Tallene i arrayen er lest inn fra fil.

 

Prpblemet er at når jeg legger inn en .txt fil med en masse tall og skriver et tall jeg ønsker å søke etter i innTall_input så hopper metoden sok() rett ned i catch'en med en gang. Men jeg skjønner ikke hvorforfor ikke

int sid = Integer.parseInt(innTall_input.getText()); får gjort om innTall_input til int slik at sok() kan gå i try boksen.

 

Er det noen andre som ser hva jeg har gjort feil??

 

Takker på forhånd;)

 

 

Hei!

 

Har testet programmet ditt litt og funnet ut noen ting.

 

Metodene dine sok() og binsok(), søker som de skal og finner tallet du vil ha i arrayen din. (Men det viste du antagelig.) Dette forutsetter dog at tallene i arrayen er sortert i stigende rekkefølge.

 

I lastOpp() manger du en aldri så liten chooser.showOpenDialog(null); eller tilsvarende. Ser du har kopiert koden fra javadoc'en til JFileChooser, men linjen du valgte å utelate er litt esensiell.

Du deklarerer også int teller = 0; inne i løkka. Dvs at den alltid blir satt til 0 for hver gang du går en runde i løkka. Den telles heller aldri opp, noe som også sørger for at den er 0.

Bortsett fra dette så fungerer denne metoden fint på en fil som har ett tall pr linje og nøyaktig 100 linjer... Kanskje du har lyst til å endre litt på dette med at filen må ha 100 linjer med tall?

Måtte forresten legge til et kall på lastOpp() også, men det er kanskje fjernet for å unngå Exception?

 

Konstruktøren din ser ut til å mangle en del før den fungerer som du vil at den skal. Har ikke prøvd å få den til å virke.

 

Anbefaler at du først lager programmet uten GUI, bare leser inn fra og skriver ut til kommandolinja. Når dette virker som det skal, kan du gjøre gui-bilten.

[pgdx]

Anbefaler at du først lager programmet uten GUI, bare leser inn fra og skriver ut til kommandolinja. Når dette virker som det skal, kan du gjøre gui-bilten.

En veldig god idé. Men aller først bør han lage en metode som tar inn en liste med tall, og søker gjennom den, og når den fungerer, så kan han gå videre. Og alltid skriv ut exceptions!