1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen

Unimodale Sequenzen (++)

Dieses Thema im Forum "Algorithmen und Datenstrukturen" wurde erstellt von noobthefirst, 14. Juni 2017.

  1. noobthefirst

    noobthefirst New Member

    Hallo liebes Forum [​IMG] ! 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);
  2. asc

    asc Active Member c-b Experte

    Zeig doch mal was du bisher programmiert hast.
    Woran scheitert es?
  3. noobthefirst

    noobthefirst New Member

    Hallo asc,
    vielen Dank für deine schnelle Antwort [​IMG] !!! 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 :-(
  4. asc

    asc Active Member c-b Experte

    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.