[Garfield]

Hallo zusammen, habe im Anhang eine Frage die von meiner Zulassung abhängt finde aber keinen Ansatz sie zu lösen. Vielleicht wißt ihr wie es gemacht werden soll.

[ph0x]

Naja, du fängst mit n=0 an und machst dann rekursiv weiter. Oder was fehlt dir?


greetz ph0x

[Garfield]

Kannst du mir den ersten Schritt n=0 zeigen bzw. erklären?

[ph0x]

Korrigiere, der erste Schritt ist bei n=1.
Du überlegst dir jetzt, wenn das angesprochene Feld genau "1" lang ist, wie oft die Funktion um ungünstigsten Fall sich selbst wieder aufrufen muss. Bei n=1 gibts da ja nicht so viele Möglichkeiten.
Darauf aufbauend kannst du dann rekursiv angeben, wie der Aufwand wächst und somit zum Schluss eine Klassifizierung in Landau-Notierung angeben.


greetz ph0x

[Garfield]

bei n=1 sind es 0 Vergleiche bei n=2 gibt es 1 Vergleich.

Aber n>= 2 ergibt doch immer nur ein Vergleich in Zeile 7,
max_r und max ist doch eine ganze Zahl .
Bedingung ist doch nur das l<r.

[ph0x]

Eh, bist du sicher, dass das dein Fach ist? *SCNR*
Am Anfang ist die linke Grenze die 0 und die rechte das Maximum a. Dann wird verglichen, ob die rechte Grenze noch größer als die linke ist und dann wird ein neues Maximum in diesem Intervall gesucht. Dazu wird wieder die Funktion "Maxsuche" aufgerufen. Also ein rekursiver Aufruf, der T(n) beeinflusst.


greetz ph0x

[Garfield]

Sagen wir mal wir haben n=3
Pos.0= 3
Pos.1=2
pos.2=1

1.Abfrage l=0, r=2 , m=1
max=Maxsuxhe(a,0,2)=max der beiden ist 3
max_r=Maxsuxhe(a,2,2)=max der beiden ist 3

if nicht erfüllt
else gibt a=3 wieder

somit gibt es doch eine Abrage in if(max_r>max)

[ph0x]

Bist du sicher, dass du verstanden hast, was der Algorithmus macht? Der Algorithmus teilt das zu durchsuchende Feld in der Mitte und sucht rekursiv das Maximum in den beiden Teilfeldern. Das geht so weiter, bis er das absolute Maximum gefunden hat.
Nun sollst du ermitteln, wie oft im ungünstigsten Fall die Funktion "Maxsuche" (= Anzahl der Vergleiche) aufgerufen wird.


greetz ph0x

[Garfield]

Jetzt bin ich ein Schritt weiter. Die Fragestellung verwirrt micht T(n) der Zeile 7 bestimmt werden soll

[ph0x]

Ob du nun die Anzahl der Aufrufe von Maxsuche() oder die Anzahl der Vergleiche bestimmst, das kommt auf das Gleiche raus. Schließlich wird der Vergleich auch bei jedem rekursiven Aufruf wieder durchgeführt.


greetz ph0x

[Garfield]

Also was ich jetzt mache ist:
5.und 6. Zeile zählen

für n=1
rufe ich Maxsuche(1.Zeile) auf (1.Abfrage)
Erhalte a sofort durch die else Schleife
Somit eine Abfrage.?

für n=2
rufe ich Maxsuche(1.Zeile) auf (1.Abfrage)
Erhalte a durch jeweils eine Abfrage in Zeile 5 und 6
Somit 3 Abfrage.?

für n=3
keine Änderung
?

[ph0x]

Wieso keine Änderung ab n=3?
Wenn du aus einem Feld mit 1000 Einträgen das Maximum in nur 3 Durchläufen findest, solltest du das Verfahren zum Patent anmelden.
Jedes Mal, wenn Maxsuche aufgerufen wird und das Feld in der Mitte geteilt werden kann, wird Maxsuche noch einmal aufgerufen und so weiter und so fort.
Rekursion halt. Da ist es mit 3 Durchläufen nicht getan.


greetz ph0x

[Garfield]

So versuche nun was konkretes:
n=3 somit Maxsuche(a,0,2)

Somit ist das Feld ={a[0],a[1],a[2]}

1.Durchlauf l=0 und r = 2 m=1
da l<r
m=1
a=a[0] oder a[1]

a=a[2] oder a[2],

sagen wir a[0]=2,a[1]=1,a[2]=4,

so erhalten wir max=4

Was passiert nun?
Hier steckt glaub ich mein Fehler da ich denke maxima gefunden ,fertig.

[ph0x]

Mit n=3 ist die Sache witzlos, da sie nach höchstens 2 Durchläufen beendet ist. Stell dir ein Feld a[0..9] mit den natürlichen Zahlen 0 bis 10 vor.

1. Durchlauf:

Maxsuche(a, 0, 9) {
 if (0 < 9) {

 ist der Fall, also m:=9/2; (=4)

 max:=Maxsuche(a,0,4);     } HIER IST DER 
 max_r:=Maxsuche(a,5,9);   } KNACKPUNKT!

  if (max_r > max) {
   max:=max_r;
  }

 return (max);

 else {
  return (a[l]);  /* Maximum am Punkt l gefunden
 }
}

Da wo ich oben Knackpunkt geschrieben habe, ist dein Denkfehler. Hier springst du erneut in die Funktion Maxsuche, d.h. du fängst mit den neuen Werten ganz oben in der Funktion wieder an. Die if-Abfrage kommt erst, wenn die Rekursion ganz "nach unten" gelaufen ist und a[l] zurückgegeben hat.
Dann läuft die Rekursion wieder "nach oben" und liefert jedes Mal das Teilfeld, in dem sich das Maximum befindet, zurück. Als Ergebnis bekommst zu somit das Maximum, das "ganz unten" in der Rekursion ermittelt wird.


greetz ph0x

[Garfield]

Das Stimmt.
Mir müßte jetzt klar sein.
Danke für die geduld.

Nach meinen Standpunkt wird bei deinem Beispiel für 10 Positionen
Maxsuche 8 mal Aufgerufen

Maxsuche(a,0,9) zu Begin

Maxsuche(a,0,4)
Maxsuche(a,5,9)

Maxsuche(a,0,2)
Maxsuche(a,8,9)

Maxsuche(a,0,1)
Maxsuche(a,9,9)

Maxsuche(a,0,0)

und wenn ich das nun z.B. für 20 Positionen und 30 Positionen mache, dann kann ich T(n) herleiten?


.