Επενδύσεις στο Χρηματιστήριο (45 Μονάδες)
Σε μια στιγμή αυθορμητισμού, αποφασίσαμε να μπούμε ενεργά στον χώρο του χρηματιστηρίου και των μετοχών. Κάνοντας αυτήν την κίνηση, μάθαμε πως το πρώτο πρόβλημα που πρέπει να λύσουμε είναι το πότε πρέπει να πουλήσεις και πότε να αγοράσεις μια μετοχή. Αυτό θα είναι και το πρόβλημα που θα μας απασχολήσει σε αυτό το θέμα.
Γράψτε ένα πρόγραμμα το οποίο θα διαβάζει από την πρότυπη είσοδο τις τιμές που λαμβάνει
μια μετοχή σε διαδοχικές μέρες και τυπώνει: (1) την ελάχιστη τιμή της μετοχής και (2) την
μέγιστη τιμή της μετοχής. Επιπλέον, όταν δοθεί το όρισμα --optimal θέλουμε να τυπώνει
στην πρότυπη έξοδο και τον βέλτιστο συνδυασμό πότε έπρεπε να αγοράσει κανείς την μετοχή,
πότε να την πουλήσει καθώς και το αναμενόμενο κέρδος (17/45 της βαθμολογίας).
Περιγράψτε την χρονική και χωρική πολυπλοκότητα του αλγορίθμου σας ως προς τον αριθμό N των ακεραίων και εξηγήστε αν είναι η βέλτιστη (8/45 της βαθμολογίας).
Παραδείγματα εκτέλεσης ακολουθούν:
$ ./stonks
Give me the number of days: 10
Give me 10 stock values for each day: 7 1 5 3 6 4 9 2 8 3
Minimum: 1
Maximum: 9
$ ./stonks --optimal
Give me the number of days: 8
Give me 8 stock values for each day: 10 9 8 7 1 3 5 6
Minimum: 1
Maximum: 10
Optimal strategy to buy on day 5 and sell on day 8 for profit 5.
Παρατηρήστε στο δεύτερο παράδειγμα ότι η αγορά πρέπει να γίνει πριν την πώληση, άρα
το κέρδος δεν είναι απλώς μέγιστο μείον ελάχιστο. Η απλή λύση δοκιμάζει κάθε ζεύγος
ημερών σε O(N²)· σκεφτείτε όμως τι αρκεί να θυμάστε από τις προηγούμενες μέρες όταν
εξετάζετε την πώληση σε μια συγκεκριμένη μέρα, ώστε να αρκεί ένα πέρασμα. Προσέξτε ότι
οι μέρες μετρούν από το 1 και ελέγξτε το argv με strcmp.
Αριθμός στον οδηγό: Α25.8
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: exam-2026-jun-q3 ·
Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2026-jun-q3.html ·
Markdown (GitHub)