Unimodale Sequenzen (++)

#1
Hallo liebes Forum! Dies hier ist mein erster Beitrag hier und ich bin gerade sehr sehr verzweifelt. Es geht um die Lösung einer Aufgabe, bei der ich gerade vor einer sprichwörtlichen Wand stehe. Wenn ihr mir dabei irgendwie helfen könntet wäre ich extrem dankbar.

Die Aufgabe lautet wie folgt:

Sei int a[] ein Array der Länge n, dessen Werte eine unimodale Sequenz sind. D.h. es gibt einen Index p, so dass a[0] < a[1] < ...< a[p] > a[p+1] > ...> a[l-2] > a[l-2] gilt.
Bis zum Index p steigen die Werte an, danach fallen sie wieder ab.
Entwerfen Sie einen (rekursiven) Algorithmus, der den Peak-Index p in Zeit O(log(n)) ndet. Weisen Sie nach, dass Ihr Algorithmus die geforderte Laufzeit hat.
Verwenden Sie die zur Verfügung gestellten Zeilen, um den Algorithmus darzustellen.
Geben Sie die Lösung durch jeweils ein Leerzeichen getrennt ein (Lösung unter Angabe der Zahlen/Buchstabenangabe die jeweils vor den Zeilen unten stehen). Verwenden Sie nur Grossbuchstaben und ergänzen Sie geschweifte schliessende und öffnende Klammmern, wo sie nach den üblichen Regeln benötigt werden.

Zur Verfügung gestellte Zeilen:
1A return unimodal(a,start,mitte);
1B return unimodal(a,start,mitte+1)
2A mitte = (start+ende)/2;
2B mitte = start + ende/2;
3A if ( a[mitte] > a[mitte+1])
3B if ( a[mitte] < a[mitte+1])
4 else
5A return start;
5B return ende;
6 else
7 int unimodal (int a[], int start, int ende)
8A if (ende == start+1)
8B if (ende == start)
9A return unimodal(a,mitte,ende);
9B return unimodal(a,mitte+1,ende);
 
#3
Hallo asc,
vielen Dank für deine schnelle Antwort !!! Mein Problem ist das mir der Einstieg in die Lösung fehlt bzw. wie die rekursive Funktion aufgebaut sein muss damit diese dementsprechend so oft wiederholt wird, dass am Ende die Lösung vorhanden ist. Mir fehlt die zündende Idee für die Architektur, da ich leider Probleme habe die genaue Aufgabenstellung zu verstehen. Ganz zu schweigen vom Nachweis über die Laufzeit.....ich stehe echt vor der oben erwähnten sprichwörtlichen Wand :-(
 

asc

Well-Known Member
c-b Experte
#4
Also, zuerst solltest du dir mal in Stichpunkten herausschreiben was für eine Ausgangssituation du hast.

Du weißt, dass du eine Liste mit Zahlen hast die zuerst aufsteigend sortiert ist, dann ab dem gesuchten Punkt absteigend sortiert ist.
In der Aufgabenstellung ist auch gegeben, dass in der Liste keine gleichen Zahlen aufeinander folgen.

Die Liste könnte wie folgt aussehen: 1,2,3,4,3

In den Code-Blocken ist schon ersichtlich, dass sich der Algorithmus von der Mitte aus annähern wird.
D.h. im ersten Durchlauf muss geprüft werden ob die Mitte der Liste größer oder kleiner ist als die Zahl an der Stelle "Mitte + 1".

Die Mitte wird errechnet mit 2A oder 2B (finde selbst heraus welche Formel die richtige ist).
Das Ergebnis wäre in meinem Fall bei 5 Zahlen (start = 0, ende = 4) der Index 2, also die Zahl 3.

Mit den Abfragen bei 3A und 3B wird nun geprüft ob die Zahl größer oder kleiner ist.

Angenommen sie wäre kleiner
(3 < 4):
Die Liste wird am Mittelpunkt noch größer, es ist aber nicht bekannnt ob hier bereits der Gipfel erreicht wurde. Der Gipfel muss sich im Bereich "mitte" und "ende" befinden. (9A oder 9B).

Angenommen sie wäre größer (3 > 4):
Die Liste wird am Mittelpunkt bereits kleiner, es ist aber noch nicht bekannnt ob hier bereits der Gipfel erreicht wurde. Der Gipfel muss sich im Bereich "start" bis "mitte" befinden (1A oder 1B).

Mit diesem Vorgehen wird der Bereich "start" und "ende" immer weiter eingrenzt bis mit 8A oder 8B das Ganze mit 5A oder 5B beendet wird.
 
Oben