Rekursive Methoden

[KXHK]

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.

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

 

[SlaterB]

dein Programm gibt dir alle Infos die du brauchst, du muss sie nur lesen oder debuggen

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

 

[blackMamba]

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.

 

[blackMamba]

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.

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);
		   }
		   
	   }
   }

}

 

[blackMamba]

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

 

[Guest]

dein Programm gibt dir alle Infos die du brauchst, du muss sie nur lesen oder debuggen

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.

 

[Guest]

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.

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.

 

[blackMamba]

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)?

 

[SlaterB]

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

 

[Guest]

@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 ;-)

 

[blackMamba]

ups, da hatte ich wohl vergessen mich einzuloggen

@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 ;-)

 

[SlaterB]

> 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

 

[Marco13]

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...

 

[blackMamba]

@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...

 

[blackMamba]

oh, seh gerade, das Marco13 ja quasie das gleich geschrieben hat, nur viel besser formuliert

 

[Leroy42]

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

Ich halte das ganze für ziemlich sinnbefreit!