Erste Schritte "return" Problem bei Rekursion

[kritrat]

Hallo zusammen,

ich versuche mich nun seit ein paar Wochen in Java.
Nun versuche ich aus einer gegebenen Liste das k-t größte Element zu finden, OHNE diese vorher zu sortieren...

Mein Denkansatz war das:

	public static int select( int [] A, int k, int index, int zaehler) {  //beim Aufruf muss index = A.length und zaehler = 0 sein.
		if ( k > A.length)
			return;									//an dieser Stelle soll das Programm abbrechen...?
		if (k > 0){
			int n = A.length;
			int [] TMP = new int [n-1];
			int ind = 0;
			int max = A[ind];
			k--;					// k wird bei jedem jekursiven Aufruf verkleinert. Ist k = 0, so habe ich das k-t größte Element gefunden.
			for (int i = 1; i < n; i++) {
				if (A[i] > max) {
					max = A[i];
					ind = i;
				}			
			}
			for (int x = 0; x < ind; x++)		// hier wird die alte Liste in eine neue kopiert, das bisher größte Element wird dabei ausgelassen
				TMP[x] = A[x];
			for (ind++; ind < n; ind++)
				TMP[ind] = A[ind];
			if (ind < index)
				select(TMP, k, ind, zaehler);
			else {
				zaehler++;				// zaehler soll sicherstellen, dass der Index nicht durch den rekursiven aufruf verfälscht wird
				select(TMP, k, ind+zaehler, zaehler);
			}			
		}
		else 
			return index;
	
	}

Meine Probleme:
a) soll das Programm beim ersten If abbrechen, ich weiß allerdings nicht wie. (return geht nicht, da ein Int zurückgegeben werden muss)

b) wenn ich (testweise) oben return 0; eingebe, dann sagt mit Eclipse, dass ich ein Int zurückgeben muss. Also dass die Möglichkeit besteht, dass ich niemals auf ein return treffe... aber warum?

c) funktioniert der Code so überhaupt? :bahnhof:


Vielen Dank schonmal :toll:

 

[SilverClaw]

public static int select( int [] A, int k, int index, int zaehler) { //beim Aufruf muss index = A.length und zaehler = 0 sein.

Dann lass nur den Array übergeben und lege k und index in der Methode fest. o.ô
Also

public static int select(int[] A, int k) {
int zaehler = A.length;
int index = 0;
}

if ( k > A.length)
return; //an dieser Stelle soll das Programm abbrechen...?

Dann gib entweder einen nicht-normalen Wert zurück...z.B. -1, falls sonst nur positive Zahlen kommen sollten. Oder mach es richtig und wirf eine Exception, z.B. throw new IllegalArgumentException("k muss kleiner sein.);

 

[Thallius]

Also Rekursion sehe ich in der Aufgabenstellung eigentlich keine.

Ohne es jetzt ausprobiert zu haben einfach mal so hingeschrieben:

public class main 
{
	int[] buffer;
	
	public void main(String[] args)
	{
		int k=5;
		int max=Integer.MAX_VALUE;
		
		for(int i=0;i<k;i++)
		{
			max=getMax(buffer, max);
		}
		System.out.println(k+"te Maximum = "+max);
	}
	
	private int getMax(int[] buffer, int max)
	{
		int newMax=0;
		for(int i=0;i<buffer.length;i++)
		{
			if(buffer[i]>newMax && buffer[i]<max)
			{
				newMax=buffer[i];
			}
		}
		return newMax;
	}
}

Gruß

Claus

 

[kritrat]

Ok, return -1 ist in dem Fall möglich..

Zaehler und Index IN der Funktion zu deklarieren geht nicht, da sie sonst bei jedem rekursiven Aufruf, diese wieder und wieder auf den gleichen Wert gesetzt werden.

Nur beim erstmaligen Aufruf müssen sie diese Werte haben.


@Thallius

Prinzipiell funktioniert der Code so, allerdings geht es auch darum, das mit einer "größer gleich" Ordnung zu machen.

Wenn also 10 das größte Element ist, 10 allerdings 2 mal vorkommt, dann wäre 9 das drittgrößte Element.

Enstprechend habe ich versucht, das gefundene Element bei jedem neuen Aufruf zu isolieren.

 

[jstei001]

Ich weiß nicht was du mit k-t element meinst. Soll die Aufgabe jetzt sein das größte Element innerhalb eines Arrays zu finden? Oder den Array zu sortieren?

Suchst du jetzt explizit nach einer rekursiven Lösung oder geht auch eine Iterative?

 

[kritrat]

Ich weiß nicht was du mit k-t element meinst. Soll die Aufgabe jetzt sein das größte Element innerhalb eines Arrays zu finden? Oder den Array zu sortieren?

Suchst du jetzt explizit nach einer rekursiven Lösung oder geht auch eine Iterative?

k-t größtes Element bedeutet, wenn k=3 ist soll das drittgrößte Element ausgegeben werden (bzw dessen Index). k=5 das fünftgrößte.. usw

Die Lösung muss nicht rekursiv sein, ich gehe nur davon aus, dass es ohne Rekursion nur schwer möglich ist...

 

[kritrat]

Ok, ich bin jetzt auf die Lösung gekommen.
Der Code an sich funktioniert so, allerdings muss ich den Index vernachlässigen und den "max" Wert zurückgeben.

Habe hier leider keine Möglichkeit den Code nochmal zu schreiben, werde ihn dann aber schnellstmöglich posten und das Thema (sofern er wirklich läuft) als erledigt melden.

Danke für die Hilfe

 

[jstei001]

Das ist auch ohne Rekursion möglich, hängt auch immer ein bisschen davon ab wie groß dein Array ist.

Meiner Meinung nach wäre die sauberste Lösung, wenn du den Array erst sortierst und dann einfach auf das gewünschte Element zugreifst. Z.b. index=3 ist dann das 4. größte Element usw.

Zum sortieren gibt es ja einen haufen Algorithmen (BubbleSort, MergeSort etc.) Dann sieht dein Quellcode so aus:

public static int select(int[] a, int k){

doSort(a); //Die Methode doSort implementiert einen Sortieralgorithmus

if(k>a.length){
  return -1
}

return a[k-1];

}

 

[fischefr]

Was ist denn eigentlich der Zweck dieser Übung? Performance kann nicht der Grund für die Vermeidung einer Sortierung sein, die ist bei dieser Lösung sicherlich schlechter.

Ich erinnere mich aus dem Studium, dass es eine Datenstruktur gab, die jeweils das größte Element bereit hielt, ohne zuvor die komplette Datenmenge zu sortieren. Stattdessen rutscht nach Entnahme des größten Elements das nächstkleinere nach. Hab eben mal etwas recherchiert und ich glaube, das Ding hies "heap". Mit PriorityQueue, die einen (priority)heap verwendet kommst du am besten hin, was performance betrifft (denke ich zumindest). Insbesondere wenn du das zweit- oder drittgrößte Element suchst (also das k-t-größte Element, wobei k klein ist).

..ist nur ein Hinweis, wenns nur einfach eine x-beliebige Übung zum Programmieren ist oder für Rekursion ist deine Lösung natürlich auch ok. Dann wärs natürlich interessant, deinen und meinen Ansatz mal gegeneinander laufen zu lassen und die Zeit zu vergleichen ;-)