Rekursive Methoden

Status
Nicht offen für weitere Antworten.
K

KXHK

Gast
Hallo

Kann jemand mir sagen, was es hier schief läuft. Bei diesem Programm muss die Zahl rauskommen, die in einer sortierten Array fehlt. Ich hab das auch mit Breakpoints beobachtet, wird die Methode noch einpaarmal ausgeführt, obwohl ja kein Fall (if) mehr zugetroffen wird.. Schaut besser das Programm vll versteht Ihr davon was ich meine.

Code:
public class FindeZahl {
	
	static int suche(int[] arr, int a, int b){
		
		
		int m= (int) ((a+b)/2);
		
		if(arr[m]!=m){
			if(arr[m-1]==m-1 && arr[m]==m+1)
				return m;
			else{
				b=m;
				suche(arr,a,b);
			}
			
			
			
		} else if(arr[m]==m){
			a=m;
			suche(arr,a,b);
		}
		
		return m;
	}
	public static void main(String[] args){
		int[] arr={0,1,2,3,5,6,7,8,9,10};
		
		System.out.println(suche(arr,arr[0],arr[arr.length-1]));
	}

}

Danke im voraus
 
S

SlaterB

Gast
dein Programm gibt dir alle Infos die du brauchst, du muss sie nur lesen oder debuggen
Code:
public class FindeZahl
{

    static int k = 0;

    static int suche(int[] arr, int a, int b)
    {
        k++;

        int myK = k;
        int m = (int)((a + b) / 2);
        System.out.println("Aufruf " + myK + ": a und b: " + a + ", " + b + " -> m: " + m);

        if (arr[m] != m)
        {
            if (arr[m - 1] == m - 1 && arr[m] == m + 1)
            {
                System.out.println("gefunden im " + myK + "ten Aufruf: " + m);
                return m;
            }
            else
            {
                b = m;
                suche(arr, a, b);
            }
        }
        else if (arr[m] == m)
        {
            a = m;
            suche(arr, a, b);
        }
        System.out.println("gebe m vom " + myK + "ten Aufruf zurück, unabhängig davon ob es stimmt: " + m);

        return m;
    }

    public static void main(String[] args)
    {
        int[] arr =
            {0, 1, 2, 3, 5, 6, 7, 8, 9, 10};

        System.out.println(suche(arr, arr[0], arr[arr.length - 1]));
    }

}

---------


Aufruf 1: a und b: 0, 10 -> m: 5
Aufruf 2: a und b: 0, 5 -> m: 2
Aufruf 3: a und b: 2, 5 -> m: 3
Aufruf 4: a und b: 3, 5 -> m: 4
gefunden im 4ten Aufruf: 4
gebe m vom 3ten Aufruf zurück, unabhängig davon ob es stimmt: 3
gebe m vom 2ten Aufruf zurück, unabhängig davon ob es stimmt: 2
gebe m vom 1ten Aufruf zurück, unabhängig davon ob es stimmt: 5
Ende: 5
 
B

blackMamba

Mitglied
du hast irgendwo dein Rückgabewert m mit der 5 belegt, denn es kommt immer 5 raus, egal wie man dein array verändert. Zumindest bei den vier verschiedenen Versuchen die ich gemacht habe.
 
B

blackMamba

Mitglied
willst oder musst du das ganze rekursiv machen?
Den "Normal" ist das leichter, der Quellcode ist kürzer und da keine Rekursion vorhanden ist auch schonender für die Ressourcen des Computers.
Ich hab das mal jetzt ausführlich aufgeschrieben, wobei man bei mir bestimmt auch noch ein paar Schritte sparen könnte.
Code:
public class FindeZahl {

   public static void main(String[] args){
      int[] Array={0,1,2,3,4,6,7,8,9,10};
      int laenge = Array.length;
	   for (int i = 0;i<laenge-1;i++){
		   	int Zahl1 = Array[i];
		   	int Zahl2 = Array[i+1];
		   	if((Zahl1+1)!=(Zahl2)){
		   		System.out.println(Zahl2-1);
		   }
		   
	   }
   }

}
 
B

blackMamba

Mitglied
natürlich kannst du auch die Schleife durch eine Rekursion ersetzen....
 
G

Guest

Gast
SlaterB hat gesagt.:
dein Programm gibt dir alle Infos die du brauchst, du muss sie nur lesen oder debuggen
Code:
public class FindeZahl
{

    static int k = 0;

    static int suche(int[] arr, int a, int b)
    {
        k++;

        int myK = k;
        int m = (int)((a + b) / 2);
        System.out.println("Aufruf " + myK + ": a und b: " + a + ", " + b + " -> m: " + m);

        if (arr[m] != m)
        {
            if (arr[m - 1] == m - 1 && arr[m] == m + 1)
            {
                System.out.println("gefunden im " + myK + "ten Aufruf: " + m);
                return m;
            }
            else
            {
                b = m;
                suche(arr, a, b);
            }
        }
        else if (arr[m] == m)
        {
            a = m;
            suche(arr, a, b);
        }
        System.out.println("gebe m vom " + myK + "ten Aufruf zurück, unabhängig davon ob es stimmt: " + m);

        return m;
    }

    public static void main(String[] args)
    {
        int[] arr =
            {0, 1, 2, 3, 5, 6, 7, 8, 9, 10};

        System.out.println(suche(arr, arr[0], arr[arr.length - 1]));
    }

}

---------


Aufruf 1: a und b: 0, 10 -> m: 5
Aufruf 2: a und b: 0, 5 -> m: 2
Aufruf 3: a und b: 2, 5 -> m: 3
Aufruf 4: a und b: 3, 5 -> m: 4
gefunden im 4ten Aufruf: 4
gebe m vom 3ten Aufruf zurück, unabhängig davon ob es stimmt: 3
gebe m vom 2ten Aufruf zurück, unabhängig davon ob es stimmt: 2
gebe m vom 1ten Aufruf zurück, unabhängig davon ob es stimmt: 5
Ende: 5

vielen dank für die schnelle Antwort.

als ich dein Programm und die Ergebnisse sah, ist mir eingefallen dass rekursive Methoden werden noch mal zurückgeklappt werden. :)
 
G

Guest

Gast
blackMamba hat gesagt.:
willst oder musst du das ganze rekursiv machen?
Den "Normal" ist das leichter, der Quellcode ist kürzer und da keine Rekursion vorhanden ist auch schonender für die Ressourcen des Computers.
Ich hab das mal jetzt ausführlich aufgeschrieben, wobei man bei mir bestimmt auch noch ein paar Schritte sparen könnte.
Code:
public class FindeZahl {

   public static void main(String[] args){
      int[] Array={0,1,2,3,4,6,7,8,9,10};
      int laenge = Array.length;
	   for (int i = 0;i<laenge-1;i++){
		   	int Zahl1 = Array[i];
		   	int Zahl2 = Array[i+1];
		   	if((Zahl1+1)!=(Zahl2)){
		   		System.out.println(Zahl2-1);
		   }
		   
	   }
   }

}


Das könnte ich auch so machen, aber es geht um die O-Notation. Ich wollte es mit O(log(n)) schaffen.

Trotzdem danke für deine Antwort.
 
B

blackMamba

Mitglied
im worste case, muss dein Code aber auch das ganze array durchgehen. Vlt bricht deiner früher ab, aber ich könnte ja in meiner for-Schleife sowas wie ein break einfügen, dann wäre die Laufzeit im average Case auch noch kleiner.
Und bist du sicher, dass dein Code das in log(n) schafft? und nicht im worst case in O(n)?
 
S

SlaterB

Gast
WorstCase ist zwar relativ egal, hier aber auch log(n),
im ersten Schritt wird die Mitte geprüft, der Fehler kann nur links oder rechts davon sein
-> schon hat man die Hälte von n eingespart, in jedem Case

die for-Schleife ist also langsamer, aber ist doch kein Wettbewerb hier? ;)

die Intervall-Halbierung führt andererseits auch nicht unbedingt zur Rekursion,
genausogut kann man eine while-Schleife verwenden,
es gibt keine Verzeigung, es muss nur das Intervall immer weiter verkleinert werden
 
G

Guest

Gast
@SlaterB

> im ersten Schritt wird die Mitte geprüft, der Fehler kann nur links oder rechts davon sein
> -> schon hat man die Hälte von n eingespart, in jedem Case

und woher weiß man, auf welcher der beiden Seiten nun die Zahl fehlt? Wenn du Glück hast, dann erwischt du die richtige...aber die Chance liegt auch nur bei 50%...und wnen du die falsch erwischt, gehste trotzdem wieder ganz durch.

Also das der Code bei log(n) liegt, davon bin ich imme rnoch nicht so ganz überzeugt....

und klar sind wir hier im Wettbewerb, sonst wären ja Laufzeiten und so egal ;-)
 
B

blackMamba

Mitglied
ups, da hatte ich wohl vergessen mich einzuloggen :)



Anonymous hat gesagt.:
@SlaterB

> im ersten Schritt wird die Mitte geprüft, der Fehler kann nur links oder rechts davon sein
> -> schon hat man die Hälte von n eingespart, in jedem Case

und woher weiß man, auf welcher der beiden Seiten nun die Zahl fehlt? Wenn du Glück hast, dann erwischt du die richtige...aber die Chance liegt auch nur bei 50%...und wnen du die falsch erwischt, gehste trotzdem wieder ganz durch.

Also das der Code bei log(n) liegt, davon bin ich imme rnoch nicht so ganz überzeugt....

und klar sind wir hier im Wettbewerb, sonst wären ja Laufzeiten und so egal ;-)
 
S

SlaterB

Gast
> und woher weiß man, auf welcher der beiden Seiten nun die Zahl fehlt?
+
> wnen du die falsch erwischt, gehste trotzdem wieder ganz durch.

es ist ja gerade KEINE echte Rekursion mit Verzweigung und neuen Versuch a la 'erst linkes Teilfeld durchsuchen, wenn nicht gefunden dann rechtest Teilfeld',
sondern ein geradliniges Verkleinern des Suchraums

im Beispiel vom ersten Post:
arr[5] = 6, damit weiß man genau, dass die fehlende Zahl weiter links sein muss, bzw. evtl. genau ein Feld links, das muss man extra prüfen, dann wäre man fertig,

wenn dagegen arr[5] == 5 ist, dann ist links alles in Ordnung, dann wird die rechte Hälfte durchsucht
 
M

Marco13

Gesperrter Benutzer
Vielleicht sollte man erwähnen, dass die benötigte Laufzeit so gesehen davon abhängt, ob man davon ausgehen kann, dass die Zahlen kontinuierlich von 0 bis n (und genau in array[0] bis array[n]) liegen. Wenn dem so ist, kann man eine binäre Suche machen, und hat log(n) ... wenn dem NICHT so ist, müßte man genauer sagen, was eine "fehlende Zahl" sein soll...
 
B

blackMamba

Mitglied
@SlaterB:
> wenn dagegen arr[5] == 5 ist, dann ist links alles in Ordnung, dann wird die rechte Hälfte durchsucht

ok, so gesehen stimmt das schon, allerdings könnte man mit der Methode, so wie sie da steht und implementiert ist, nicht die Reihe 6,7,9,10,11,12,13,14,15 untersuchen....denn dann würde der ja sagen arr[0]=6, damit müsste der Fehler links liegen....nur links davon gibts nichts mehr...
 
B

blackMamba

Mitglied
oh, seh gerade, das Marco13 ja quasie das gleich geschrieben hat, nur viel besser formuliert :)
 
L

Leroy42

Top Contributor
Macht die Ursprungsmethode, bzw. eure Umkrempelungen, überhaupt einen Sinn! :shock:

Ich halte das ganze für ziemlich sinnbefreit!
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
veryck Methoden Rekursive Methoden mit Rückgabeparameter Java Basics - Anfänger-Themen 9
R Methoden rekursive Methoden Java Basics - Anfänger-Themen 6
B Methoden Rekursive Methoden Java Basics - Anfänger-Themen 2
D Methoden Rekursive Methoden Java Basics - Anfänger-Themen 13
M Stürzen alle Rekursive Methoden irgendwann ab? Java Basics - Anfänger-Themen 11
B OOP Einfach verkettete Liste - rekursive Methoden Java Basics - Anfänger-Themen 1
S rekursive methoden Java Basics - Anfänger-Themen 5
M Rekursive Java-Methode Java Basics - Anfänger-Themen 13
G Rekursive Methode liefert augenscheinlich keinen boolean-Wert zurück. Java Basics - Anfänger-Themen 4
macle Rekursive String Methode, Gerade Zahlen rausfiltern Java Basics - Anfänger-Themen 10
M Rekursive Prüfung ob ein Array sortiert ist... Java Basics - Anfänger-Themen 4
J Rekursive swapArray Methode Java Basics - Anfänger-Themen 69
D Rekursive Methode Java Basics - Anfänger-Themen 8
O Quersumme rekursive Methode Java Basics - Anfänger-Themen 3
B Treetable (rekursive Funktion) aufbauen von Datenbank Java Basics - Anfänger-Themen 4
M Rekursive Methode Programmieren Java Basics - Anfänger-Themen 3
J rekursive Methode Java Basics - Anfänger-Themen 26
M rekursive division/0 mit exception Java Basics - Anfänger-Themen 18
J Rekursive Methode - Ziffern einer Zahl ausgeben Java Basics - Anfänger-Themen 2
M Rekursive Dateiliste erstellen mit Dateiendung(en) ?? Java Basics - Anfänger-Themen 4
S Rekursive Methode Java Basics - Anfänger-Themen 8
O Rekursive Methode Java Basics - Anfänger-Themen 4
V Methoden Rekursive Methode mit String als Rückgabe Java Basics - Anfänger-Themen 7
K Rekursive Methode Java Basics - Anfänger-Themen 1
K Rekursive Methode für Fakultät mit BigInteger Java Basics - Anfänger-Themen 10
L Rekursive Methode a * b berechnen Java Basics - Anfänger-Themen 2
L Rekursive Methode zur Berechnung der Potenz q hoch p Java Basics - Anfänger-Themen 17
J Methoden Rekursive Return Methode Java Basics - Anfänger-Themen 2
G Harmonische Rekursive Folge Java Basics - Anfänger-Themen 3
T Stack Overflow - Rekursive Fibonacci Java Basics - Anfänger-Themen 10
B Datentypen Suchbaum - Rekursive Ausgabe Java Basics - Anfänger-Themen 1
P Methoden Rekursive Methode für Potenzen Java Basics - Anfänger-Themen 2
M Methoden Binäre Suche als rekursive Variante Java Basics - Anfänger-Themen 5
B Rekursive Algorithmus schreiben Java Basics - Anfänger-Themen 8
S Eine rekursive Lösung Java Basics - Anfänger-Themen 4
S Int zu Hexadezimal - Rekursive Methode Java Basics - Anfänger-Themen 2
M Rekursive Suche in einem Feld Java Basics - Anfänger-Themen 11
N Rekursive Addition mit Scanner Java Basics - Anfänger-Themen 12
shiroX OOP Rekursive und Iterative Definition Java Basics - Anfänger-Themen 2
T Iterative Pi Berechnung in Rekursive Java Basics - Anfänger-Themen 2
C rekursive methode Java Basics - Anfänger-Themen 2
R rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
D Primzahlen und Rekursive Liste Java Basics - Anfänger-Themen 29
R Rekursive Methode, Files finden Java Basics - Anfänger-Themen 2
S rekursive folge verbessern Java Basics - Anfänger-Themen 2
C rekursive Methode verstehe nicht! Java Basics - Anfänger-Themen 3
S Methoden rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
E Rekursive Methode Java Basics - Anfänger-Themen 3
N Methoden Rekursive Fibonaccizahlen mit Array Java Basics - Anfänger-Themen 2
R Rekursive Ausgabe eines Binärbaums Java Basics - Anfänger-Themen 4
J Methoden Rekursive Potenz ohne Math.Pow() Java Basics - Anfänger-Themen 9
A Rekursive Methode in Iterative umwandeln Java Basics - Anfänger-Themen 6
S Labyrith Rekursive Wegsuche Java Basics - Anfänger-Themen 4
C Rekursive Methode - Ziffern in Zahl Java Basics - Anfänger-Themen 33
U Dezimal zu Hexadezimal rekursive Funktion Java Basics - Anfänger-Themen 8
M rekursive Funktion zur Berechnung der Spiegelzahl Java Basics - Anfänger-Themen 7
L iterative und rekursive Folge Java Basics - Anfänger-Themen 20
G Rekursive Methode Java Basics - Anfänger-Themen 3
A rekursive Listen in Java? Java Basics - Anfänger-Themen 5
E Rekursive Methode mit Zufallsarray Java Basics - Anfänger-Themen 6
E Rekursive Methode Java Basics - Anfänger-Themen 18
U Rekursive lösung von pascal dreieck Java Basics - Anfänger-Themen 11
M Rekursive Methode - wo ist der Fehler? Java Basics - Anfänger-Themen 4
J rekursive methode Java Basics - Anfänger-Themen 6
H ScrollBar inaktiv / Rekursive Methode Java Basics - Anfänger-Themen 4
J Rekursive Methode Java Basics - Anfänger-Themen 11
G Rekursive Methode Java Basics - Anfänger-Themen 5
N Rekursive Berechnung der Höhe eines binären Baumes Java Basics - Anfänger-Themen 4
K Rekursive Funktion (Verständnissfrage) Java Basics - Anfänger-Themen 5
S Rekursive Bruch potenzierung Java Basics - Anfänger-Themen 2
D rekursive Summenberechnung Java Basics - Anfänger-Themen 8
J Rekursive Methode: Fakultaet berechnen Java Basics - Anfänger-Themen 5
E Rekursive definierten Folge Java Basics - Anfänger-Themen 10
A HILFE! Rekursive Funktion Java Basics - Anfänger-Themen 20
kulturfenster rekursive Binaere Suche Java Basics - Anfänger-Themen 12
F Rekursive Aufrufe, Parameterübergabe, call by reference Java Basics - Anfänger-Themen 3
G Rekursive Berechnung von n über k schlägt fehl Java Basics - Anfänger-Themen 5
B Rekursive & schreiben im ArrayList Java Basics - Anfänger-Themen 2
J Rekursive Fkt. Java Basics - Anfänger-Themen 2
A Rekursive Dateisuche Java Basics - Anfänger-Themen 12
K rekursive Funktion mit mehreren Parametern Java Basics - Anfänger-Themen 5
G rekursive Methode Java Basics - Anfänger-Themen 3
N rekursive Beispiele Java Basics - Anfänger-Themen 3
G rekursive u iterative Methode Java Basics - Anfänger-Themen 8
G Rekursive Methode Java Basics - Anfänger-Themen 7
ven000m Rekursive Funktionen - Frage Java Basics - Anfänger-Themen 16
D rekursive ausgabe einer zahl Java Basics - Anfänger-Themen 14
S Rekursive Funktionen in imperative Funktionen umwandeln Java Basics - Anfänger-Themen 2
M Rekursive Binärsuche Java Basics - Anfänger-Themen 6
M Bräuchte Hilfe bei diesen Methoden Java Basics - Anfänger-Themen 4
G Methoden Methoden mit versch. Datentypen Java Basics - Anfänger-Themen 1
T Ich habe eine Variabel die nicht Methoden übergreifend ist. Kann mir jemand Helfen :) Java Basics - Anfänger-Themen 5
Junger_Basileus Celsius -> Fahrenheit / Strukturierung in statischen Methoden Java Basics - Anfänger-Themen 7
J Verschachtelte Methoden Java Basics - Anfänger-Themen 9
H Methoden in anderen Methoden aufrufen Java Basics - Anfänger-Themen 6
Kawastori Hilfe bei Methoden Übung Java Basics - Anfänger-Themen 6
C Methoden können nicht auf Instanzvariable der Klasse zugreifen Java Basics - Anfänger-Themen 3
P Methoden aufrufen - Fehler Java Basics - Anfänger-Themen 20
M konzeptuelle Frage: In welcher Klasse definiert man am Besten Methoden, die die Kommunikation mit dem User regeln? Java Basics - Anfänger-Themen 8
C eigene Methoden erstellen (Instanzmethoden) Java Basics - Anfänger-Themen 7

Ähnliche Java Themen

Anzeige

Neue Themen


Oben