3. Spekulation ? ( Algorithmus )

Spekulation ? ( Algorithmus )

  • L

    Ein Wirtschaftsmagazin besitzt für jede Aktie eine Zahlenfolge, in der die erste Zahl der Kurs der Aktie am ersten Börsentag und jede folgende Zahl die absolute Kursveränderung gegenüber dem Vortag angibt, in der Reihenfolge der Börsentage. Der Kurs, der sich für einen gewissen Tag ergibt, gilt für alle Käufr und Verkäufe dieses Tages.

    Geben Sie einen möglichst guten Algorithmus an, der für eine Aktie aus der gegebenen Zahlenfolge nachträglich einen besten Einkaufstag, einen besten Verkaufstag und den dabei höchsten erzielbaren Gewinn ( in Prozent vom eingesetzten Betrag ) ermittelt.

    Hat einer von euch da eine Idee ?

    0
  • S

    Wo hängst du denn genau?

    Im Prinzip musst du doch nur die Ausgangszahl + Kursveränderungen rechnen...

    0
  • L

    Also man muß doch eigentlich alle Möglichkeiten durchgehen damit man die Aufgabe überhaupt lösen kann. Und das sind jede Menge Möglichkeiten. Er soll ja am ende das Paar ausgeben, dass den prozentual höchsten Gewinn abwirft.

    0
  • S

    und?
    es rechnet doch eh der PC - dir kann das ja egal sein 🙂

    Einfach ne Schleife bauen, die zu jedem Tag den Kurs ausrechnet und den höchsten Kurs merken...

    0
  • L

    HAbe gerade übrigens gesehen das das eine Aufgabe des Bundeswettbewerbs für Informatik aus dem Jahre 1985 ist :).
    Finde ich ja toll das wir so etwas als ganz normale Übungsuafgabe machen müssen :).
    Naja ich versuch mein Glück mal aber sollte jemande vielleicht so etwas schon mal gemacht haben, wäre es super denn ich bin für jeden Tipp dankbar.

    0
  • S

    du kannst gerne fragen.
    Den Ansatz habe ich dir ja schon gesagt - wenn ich mehr sage, wird es langweilig 🙂

    0
  • M

    Absolute Kursverändungen?
    Dann würden da ja direkt die neuen Zahlen stehen...

    0
  • J

    @Shade: Dein Ansatz ist zu teuer finde ich...

    Im Prinzip muß man ja nur die Zahlenfolge mit der größten Summe finden. Das geht meines wissens in O(n)...
    Für jeden Tag einzeln rechnen wäre aber O(n²)... was nicht so schön ist.
    Soweit ich mich erinnere gab's in Bentley's Programming Pearls ne recht schöne Lösung.

    MfG Jester

    0
  • S

    Jester schrieb:

    Für jeden Tag einzeln rechnen wäre aber O(n²)... was nicht so schön ist.

    Warum?
    Bei
    Startwert: 10
    Kursänderungen: +2 +3 -1 -5

    Hätte ich folgendes:
    1. Tag: 10
    2. Tag: 10 + 2 == 12
    3. Tag: 12 + 3 == 15
    4. Tag: 15 - 1 == 14
    5. Tag: 14 - 5 == 9

    Oder rechne ich irgendwie falsch? Für mich sieht es wie O(n) aus.
    Ich rechne ja nicht für jeden Tag einzeln, sondern basierend auf den Vortag.

    0
  • J

    Ja, aber Du mußt das für jeden Tag machen, damit Du den besten Starttag rauskriegst.

    Also O(n²)

    Deutlich effizienter ist folgendes:

    int maxsofar = 0;
int maxendinghere = 0;
for(int i=0; i<n; ++i)
{
  maxendinghere = max(maxendinghere+feld[i], 0);
  maxsofar = max(maxendinghere, maxsofar);
}

    Das liefert natürlich nur den höchsten Wert. Aber die Modifikation zum Speichern von Beginn und Ende ist unproblematisch.

    MfG Jester

    0
Anmelden zum Antworten