Elmo darf sich zum Geburtstag eine beliebige Aktie zu einem beliebigen Zeitpunkt kaufen. Glücklicherweise hat er eine Maschine der Firma Flow, die in der Lage ist, die Aktienkursänderungen einer bestimmten Aktie in den nächsten Monaten vorherzusagen. Diese Maschine produziert eine Folge von Werten, von denen einer jeweils der Änderung des Aktienindexes der Aktie an einem Tag entspricht. Natürlich möchte Elmo seinen Gewinn optimieren.
Schreibe ein Programm, das die Gewinne bzw. Verluste einer Aktie von bis zu 1000000 aufeinanderfolgenden Tagen aus der Datei aktie.in einliest und anschließend herausfindet, in welchem Zeitraum der maximale Gewinn mit dieser Aktie erzielt werden kann. Dieser Zeitraum soll in der Datei aktie.out ausgegeben werden.
| eine ganze Zahl N mit 1 < N ≤ 1000000 | |
| Jeweils eine Dezimalzahl d mit bis zu zwei Nachkommastellen, die der Kursänderung der Aktie entspricht (-100.0 ≤ d ≤ 100.0) |
| Zeile 1: | A, die Nummer des Tages, an dessen Morgen die Aktie am besten gekauft werden sollte |
| Zeile 2: | L, die Länge der Zeitspanne in Tagen, die die Aktie behalten werden sollte |
10
|
|
2 5 |
Der Maximale Gewinn kann erzielt werden, indem die Aktie am Morgen des zweiten Tages gekauft und vor dem starken Verlust am 7. Tag wieder verkauft wird. Die Summe der Kursänderungen entspricht in diesem Zeitraum +8.39 und ist maximal.
Die Punkte des Inhaltsverzeichnisses sollten am besten der Reihe nach gelesen werden. Wer lieber von Papier liest kann sich natürlich auch gerne die Druckversion ausdrucken. Auf jeden Fall solltest du zuerst versuchen, dir selber zu überlegen, wie du die Aufgabe lösen könntest. Die Analyse, die du hier zu dieser Musteraufgabe findest ist sehr viel mehr, als du dir während des Contests überlegen solltest, allerdings werden viele Zwischenergebnisse nach etwas Training auch ziemlich offensichtlich, z.B. was die Abschätzung der Laufzeit deines Programms angeht. Du solltest jeden Teil der Analyse so oft lesen, bis du ihn verstanden hast.
Um auf die tatsächliche Musterlösung zu kommen, braucht man schon ein wenig Erfahrung und es wird nicht ganz leicht sein, nachzuvollziehen, warum die Lösung richtig ist. Davon solltest du dich allerdings nicht entmutigen lassen, denn die Aufgaben im Online-Contest werden wohl nicht so trickreiche Lösungen haben.
Es gibt viele verschiedene Methoden, um an solche Aufgaben heranzugehen. Letztendlich ist es unheimlich schwierig, einzelne Herangehensweisen zu vermitteln und vermutlich findet jeder nach einer Weile seine eigenen Strategien. Auf jeden Fall sollte an dieser Stelle gesagt werden, dass das Lösen sehr vieler Aufgaben das beste Training ist. Meistens kommen einem dann die Problemstellungen schon bekannt vor, oder man hat wenigstens Teilproblemstellungen schon häufig gelöst.
Oft hilft es, zumindest die Beispielfälle und evtl. auch selbstausgedachte Testfälle erstmal per Hand zu lösen. Die Testfälle können erstens später zum Verifizieren des endgültigen Algorithmus verwendet werden und helfen außerdem dabei, Muster im Lösungsverfahren und Spezialfälle zu erkennen. Wenn man in diesem Fall einfach alle Möglichkeiten durchzuprobiert, was dem ersten Lösungsansatz der Musteraufgabe entspricht, wird man relativ schnell merken, dass man nicht jedesmal wieder alle Zahlen aufaddieren muss und endet so zumindest bei dem zweiten Algorithmus.
Um auf den dritten Lösungsansatz zu kommen, muss man schon einiges an Erfahrung haben und evtl. den Trick auch schonmal gesehen haben. Es gibt auch verschiedene Programmierkonzepte, wie z.B. die dynamische Programmierung, Flood-Fill-Algorithmen, Tiefen- und Breitensuche in Graphen, etc. Viele dieser Konzepte sind in den Büchern, die auf der Ressourcenseite empfohlen sind, erklärt.
Anhand der Eingabegrößen kann man die geforderte Laufzeitkomplexität abschätzen. In diesem Beispiel ist mit der Beschränkung N≤1000000 ein deutlicher Hinweis darauf gegeben, dass ein Algorithmus mit linearer Zeitkomplexität gesucht ist. Für Eingabegrößen bis zu 5000 existieren normalerweise Algorithmen mit quadratischer Laufzeit und für Eingabegrößen bis etwa 300 lassen sich Algorithmen mit kubischer Laufzeit finden. Ist die Eingabegröße auf etwa 25 beschrängt, ist das Problem wohl nur durch Durchprobieren aller Kombinationen lösbar.
Kennt man einmal die ungefähre Zeitkomplexität, fallen einem normalerweise einige nützliche Algorithmen und ähnliche Probleme ein.
Ganz wichtig ist, dass man sein Programm testet, bevor man es einschickt. Am besten machst du dir zu Beginn ein paar eigene Testfälle, die du später immer wieder verwendest, um dein Programm zu testen.
Selbst wenn deine Lösung nicht für den schlimmsten Fall der Eingabedaten ausreicht, solltest du sie auf jeden Fall einschicken — wenn sie korrekt ist, gibt es auf jeden Fall trotzdem ein paar Punkte. Im Normalfall kann man gut die Hälfte der Punkte mit einer nicht ganz optimalen Lösung, so wie im zweiten Lösungsansatz, erzielen.
Das Programm probiert von jeder Startposition aus jede Länge durch und merkt sich das Maximum.
#include <cstdio>
using namespace std;
float values [1000000];
int N;
int main ()
{
FILE *fin = fopen ("aktie.in", "r"),
*fout = fopen ("aktie.out", "w");
fscanf (fin, "%d", &N);
for (int n = 0; n < N; n++)
fscanf (fin, "%f", &values [n]);
int maxStart = 1, maxLen = 0;
float maxValue = 0;
for (int start = 0; start < N; start++) { // für jede Startposition
for (int len = 1; start + len <= N; len++) { // für jede Länge
float summe = 0;
for (int pos = start; pos < start + len; pos++) {// aufsummieren
summe += values [pos];
}
if (summe > maxValue) {
maxValue = summe;
maxStart = start;
maxLen = len;
}
}
}
fprintf (fout, "%d\n%d\n", maxStart, maxLen);
fclose (fin); fclose (fout);
return 0;
}
Wenn man sich den Programmablauf überlegt, stellt man schnell fest, dass die Zeile summe += values [pos]; am häufigsten aufgerufen wird. Um herauszufinden, wie gut oder schlecht das Programm hinsichtlich seiner Laufzeit ist, kann man versuchen zu berechnen, wie häufig diese Zeile ausgeführt werden muss, bevor das Programm beendet wird. Betrachten wir zunächst die Beispieleingabe mit N=10. Die ganz äußere Schleife
for (int start = 0; start < N; start++) {
...
}
wird genau 10 mal, also N Mal, ausgeführt.
Etwas komplizierter sieht es mit der zweiten Schleife aus: die Anzahl ihrer Durchläufe ist abhängig vom Wert "start" aus der äußeren Schleife. Zunächst hat diese Schleife 10 Durchläufe, wenn sie das nächste Mal ausgeführt wird noch 9, dann 8 usw. Insgesamt wird der Code in der Schleife für die Beispieleingabe also 10+9+8+...+2+1 = 55 Mal ausgeführt. Allgemein kann man sagen, dass der Code N+ (N-1)+ (N-2)+...+2+1 Mal ausgeführt wird. Der Wert dieser Summe lässt sich mit der Formel (N+1) * N / 2 berechnen.
Noch komplizierter wird es dann mit der ganz inneren Schleife, also der Anweisung, an der wir eigentlich interessiert sind. Sie wird immer genau "len" mal ausgeführt. Für unser Beispiel bedeutet das (10+9+...+2+1) + (9+8+...+2+1) + ... + (1) = 10 * 11 / 2 + 9 * 10 / 2 +...+ 1 * 2 / 2 = 220 Mal. Die allgemeine Formel für diese Zahl lautet übrigens N * (N+1) * (N + 2) / 6. Das Erfreuliche ist allerdings, dass es eigentlich unnötig ist, die Formel so genau zu kennen. Es reicht völlig aus, das ungefähre Verhalten für große N zu kennen. Man kann beispielsweise vereinfachend sagen, dass alle Schleifen auf jedenfall "N mal oder weniger" ausgeführt werden. Damit würde dann die innerste Anweisung N^ 3 Mal ausgeführt. Da die genaue Formel auch ein Polynom dritten Grades ist, wird sie sich vom Verlauf her mit steigendem N auch ähnlich verhalten und praktisch nur um einen etwa konstanten Faktor abweichen:
| N | Abschätzung | Genaue Formel | Faktor |
| 10 | 1000 | 220 | 4.55 |
| 100 | 1000000 | 171700 | 5.82 |
| 390 | 59319000 | 9962680 | 5.95 |
| 1000 | 1000000000 | 167167000 | 5.98 |
| 5000 | 125000000000 | 20845835000 | 6.00 |
Wie man leicht beobachten kann, nähert sich dieser Faktor mit steigendem N scheinbar beliebig nahe an 6 an. Um die Anzahl der Ausführungen der innersten Anweisung jetzt in eine konkrete Laufzeit in Sekunden umzurechnen, muss man diese Anzahl noch mit einem konstanten Zeitfaktor multiplizieren. Moderne Rechner sollten im Moment etwa 10000000 solcher Anweisungen (summe += values [pos];) in einer Sekunde ausführen können. Das wiederum bedeutet, dass das obige Programm mit bis zu etwa 390 Kursänderungen klarkommt, wenn es nur eine Sekunde laufen darf. Es ist also zu langsam, um mit bis zu 1000000 Werten umzugehen. Auch der konstante Faktor 6 ändert an dieser Tatsache nichts, denn selbst wenn der Rechner 60000000 Anweisungen pro Sekunde verarbeiten könnte, würde das Programm nur mit bis zu 710 Werten zurecht kommen. Zulässige Werte steigen also längst nicht so schnell wie die Anzahl der Anweisungen, die pro Sekunde ausgeführt werden.
Da die Programmschritte mit der Funktion N^3 abgeschätzt werden können, sagt man, dass Programm hat "kubische Laufzeit". Man schreibt dafür O(N^3) [sprich "O von N hoch drei", Big-O-Notation genannt]. Dies bedeutet, dass wir eine obere Grenze für die Laufzeit unseres Programms in Programmschritten angeben können, nämlich a * N^3. Die Laufzeit ist nicht von den konkreten Eingabewerten, abgesehen von N, abhängig.
Die gleiche Analyse wie mit der Laufzeit lässt sich natürlich auch mit der Arbeitsspeicherverwendung durchführen, denn auch der Arbeitsspeicher ist meist mit 16 oder 32 Megabytes begrenzt. Im Beispielprogramm wird mit dem Feld "values" mit Abstand am meisten Speicher belegt. Da N begrenzt ist, kann die Größe statisch auf das Maximum festgelegt werden. Eigentlich ist die Größe aber von N abhängig, nämlich linear. Von der Speicherkomplexität her ist das Programm also ausreichend effizient, denn 1000000 floats entsprechen bei 4 Bytes pro float etwa 4 Megabytes.
Im Normalfall kommen folgende Laufzeitkomplexitäten vor:
| Konstante Laufzeit, d.h. die Laufzeit ist komplett unabhängig von den Eingabedaten (Beispiel: Berechnung der Fläche eines Rechtecks). | |
| Die Laufzeit steigt proportional zum Logarithmus von N. Dies ist meist bei etwas komplizierteren Algorithmen der Fall, so zum Beispiel bei der "binären Suche". | |
| Die Laufzeit steigt proportional zur Eingabegröße. Verdoppelt sich die Eingabegröße, verdoppelt sich die Laufzeit. Dies ist z.B. der Fall bei der Suche des Maximums von N verschiedenen, unsortierten Werten. | |
| Die Laufzeit steigt proportional zur Funktion N*log N. Hier handelt es sich wieder um Algorithmen, deren Laufzeit etwas schwieriger zu bestimmen ist, so z.B. das Sortieren einer Liste von Zahlen mit dem Mergesort Algorithmus. | |
| Die Laufzeit steigt mit dem Quadrat der Eingabegröße. Verdoppelt sich die Eingabe, vervierfacht sich die Laufzeit. Wir werden weiter unten einen Algorithmus mit quadratischer Laufzeit kennenlernen. | |
| Die Laufzeit steigt mit der Funktion N^3, so wie bei dem oben aufgelisteten Programm. |
Wieder wird von jeder Position aus die Länge hochgezählt. Wir müssen allerdings nicht jedesmal alle Werte neu aufaddieren, denn wenn die Länge um 1 erhöht wird, muss zum vorher ermittelten Wert ja nur ein weiterer hinzuaddiert werden.
#include <cstdio>
using namespace std;
float values [1000000];
int N;
int main ()
{
FILE *fin = fopen ("aktie.in", "r"),
*fout = fopen ("aktie.out", "w");
fscanf (fin, "%d", &N);
for (int n = 0; n < N; n++)
fscanf (fin, "%f", &values [n]);
int maxStart = 1, maxLen = 0;
float maxValue = 0;
for (int start = 0; start < N; start++) {
float summe = 0;
for (int len = 1; start + len <= N; len++) {
summe += values [start + len - 1];
if (summe > maxValue) {
maxValue = summe;
maxStart = start;
maxLen = len;
}
}
}
fprintf (fout, "%d\n%d\n", maxStart, maxLen);
fclose (fin); fclose (fout);
return 0;
}
Analysiert man dieses Programm nach derselben Methode wie zuvor, stellt man leicht fest, dass die Laufzeitkomplexität durch O(N^2) und die Speicherkomplexität nach wie vor durch O(N) begrenzt ist. Auch dieser Ansatz ist noch zu langsam, da er nur mit etwa 5000 Werten schnell genug ist.
Im Normalfall kann man von der Eingabegröße einer Aufgabe auf die erwartete Laufzeitkomplexität schließen. Ein Algorithmus mit linearer Laufzeit, also O(N), schafft es ziemlich gut, innerhalb einer Sekunde 1000000 Werte zu verarbeiten.
Angenommen, man betrachtet die Aktienkursänderung an einem bestimmten Tag p und kennt das Maximum m(p-1) aller Summen der Kursänderungen von einem Tag a mit a<p bis zum Tag p-1. Dann ist das Maximum m(p) aller Summen der Kursänderungen von einem Tag a mit a≤p bis zum Tag p entweder m (p-1) + value [p] oder 0, falls dieser Wert kleiner als 0 ist.
Das gesuchte Maximum ist dann das Maximum aller m (p) für 1≤p≤N. Man kann nun natürlich alle m(p) nacheinander erzeugen und jeweils überprüfen, ob ein neuer Maximalwert ermittelt wurde. Sollte das der Fall sein, muss man noch die zugehörige Startposition und Länge speichern. Das ganze benötigt nicht einmal mehr das value Feld, denn es wird ja auf die Werte in der gleichen Reihenfolge zugegriffen, in der sie in der Eingabedatei stehen.
#include <cstdio>
using namespace std;
int N;
int main ()
{
FILE *fin = fopen ("aktie.in", "r"),
*fout = fopen ("aktie.out", "w");
fscanf (fin, "%d", &N);
int maxStart = 1, maxLen = 0, curStart = 1, len = 0;
float maxValue = 0, summe = 0;
for (int pos = 0; pos < N; pos++) {
float value;
fscanf (fin, "%f", &value);
summe += value;
len++;
if (summe > maxValue) { // neues Maximum
maxValue = summe;
maxStart = curStart;
maxLen = len;
}
if (summe < 0) { // alles zurücksetzen
curStart = pos+2;
len = 0;
summe = 0;
}
}
fprintf (fout, "%d\n%d\n", maxStart, maxLen);
fclose (fin); fclose (fout);
return 0;
}
Wie bereits erwähnt, liegt die Laufzeitkomplexität bei O(N), denn die einzige Schleife des Programms wird für jede Kursänderung einmal durchlaufen. Sogar die Speicherkomplexität wurde verbessert, sie ist jetzt unabhängig von N, nämlich konstant, also O(1).