Autor Beitrag
Noobthefirst
Hält's aus hier
Beiträge: 4



BeitragVerfasst: Mi 14.06.17 06:26 
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);
Christian S.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Chefentwickler
Beiträge: 20052
Erhaltene Danke: 1877

Win 10
C# (VS 2015)
BeitragVerfasst: Mi 14.06.17 09:29 
Und auch hier nochmal (Inter-EE-Crosspost)

Hallo und :welcome:!

Bei uns gilt generell, dass wir Dir gerne helfen, selber die Lösung zu finden. Aber Du musst schon Eigeninitiative zeigen. Das heißt insbesondere, dass Du zumindest mal sagen musst, was Du bisher versucht hast, welche Ansätze Du verfolgt hast, wo Du nicht weiter kommst, was konkret Du nicht verstehst, etc. ...

Viele Grüße
Christian

_________________
Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".
Symbroson
ontopic starontopic starontopic starhalf ontopic starofftopic starofftopic starofftopic starofftopic star
Beiträge: 32
Erhaltene Danke: 2

Linux Raspbian, Win10
C, C++, Python, JavaScript, Delphi, Casio Basic, Basic Stamp
BeitragVerfasst: Mo 25.09.17 22:10 
Ich würde sowas wie eine binäre Suche machen.

Du fängst in der Mitte an (i = len div 2) und schaust dir die Vorgänger und Nachfolger an. Wenn gilt a[i-1] < a[i] > a[i+1] bist du fertig, sonst musst du abhängig davon ob a[i-1] > a[i] bzw. a[i] < a[i+1] von der linken bzw rechten hälfte zur hälfte springen.

Allerdings ist die binäre Suche nicht rekursiv - aber vielleicht ein Ansatz ;)


Zuletzt bearbeitet von Symbroson am Mo 25.09.17 22:23, insgesamt 1-mal bearbeitet
Narses
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Administrator
Beiträge: 9613
Erhaltene Danke: 902

W2k .. W7pro
TP3 .. D7pro .. D10.1
BeitragVerfasst: Mo 25.09.17 22:18 
Moin!

user profile iconSymbroson hat folgendes geschrieben Zum zitierten Posting springen:
Allerdings ist die binäre Suche nicht rekursiv - aber vielleicht ein Ansatz ;)
Das ist definitiv der richtige Ansatz. ;) Man kann jeden iterativen Algorithmus auch rekursiv (und umgekehrt) formulieren, das ist lediglich eine Frage des "Layouts". :idea: :D

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.