Το νερό είναι πολύτιμο και είναι σημαντικό να γνωρίζουμε ποια είναι τα διαθέσιμα αποθέματά μας. Δοθέντος του υψομετρικού χάρτη μιας περιοχής, θέλουμε να μπορούμε να υπολογίζουμε την μέγιστη ποσότητα νερού της βροχής που μπορεί να διατηρηθεί μέσα στις φυσικές δεξαμενές που σχηματίζονται από την διαμόρφωση του εδάφους. Για απλοποίηση, θεωρούμε ότι ο υψομετρικός χάρτης είναι μονοδιάστατος και μας δίνεται ως μια σειρά θετικών ακεραίων (μονάδες ύψους με πλάτος 1) και η ποσότητα νερού μετριέται επίσης στις ίδιες μονάδες ύψους. Το Σχήμα 1 δείχνει ένα παράδειγμα.
| Θέση | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Γη (ύψος) | 0 | 1 | 0 | 2 | 1 | 0 | 1 | 3 | 2 | 1 | 2 | 1 |
| Νερό | 0 | 0 | 1 | 0 | 1 | 2 | 1 | 0 | 0 | 1 | 0 | 0 |
Σχήμα 1: Οπτικοποίηση της ποσότητας νερού που θα “παγιδευτεί” μετά την βροχή για έναν ενδεικτικό υψομετρικό χάρτη. Στο παράδειγμα, μέχρι 6 μονάδες νερού μπορούν να συγκρατηθούν από αυτόν τον χάρτη (1 μονάδα στην 3η θέση, 1 στην 5η θέση, 2 στην 6η θέση, 1 στην 7η θέση και 1 στην 10η θέση).
Σημείωση: στο πρωτότυπο το Σχήμα 1 είναι ραβδόγραμμα (καφέ η γη, μπλε το νερό)· εδώ δίνεται ως πίνακας με τα ίδια δεδομένα.
Γράψτε ένα πρόγραμμα C που διαβάζει τον πίνακα των υψών του υψομετρικού χάρτη και επιστρέφει την μέγιστη ποσότητα του νερού της βροχής που μπορεί να συγκρατηθεί από αυτόν. Το πρόγραμμά σας πρέπει να έχει χρονική πολυπλοκότητα καλύτερη από (n^2)$, όπου $ ο αριθμός των δοθέντων υψών και την ελάχιστη δυνατή χρήση μνήμης. Αφού γράψετε το πρόγραμμά σας, καταγράψτε και εξηγήστε την πολυπλοκότητά του ως προς τον χρόνο και τον χώρο μνήμης που απαιτεί. Ακολουθούν ενδεικτικές εκτελέσεις:
$ ./water
Provide the number of heights: 12
Provide the heights: 0 1 0 2 1 0 1 3 2 1 2 1
Up to 6 units of water can be trapped
$ ./water
Provide the number of heights: 12
Provide the heights: 4 1 0 2 1 0 1 3 2 3 2 1
Up to 14 units of water can be trapped
./water
Provide the number of heights: 20
Provide the heights: 0 2 3 1 4 4 4 4 3 8 9 3 9 0 6 4 6 0 9 5
Up to 38 units of water can be trapped
Το νερό πάνω από τη θέση $ ορίζεται από το μικρότερο από τα δύο ψηλότερα «τοιχώματα» αριστερά και δεξιά της, μείον το ύψος της θέσης. Με δύο προ-υπολογισμένους πίνακες μεγίστων παίρνετε (n)$ χρόνο αλλά (n)$ επιπλέον μνήμη· για ελάχιστη μνήμη σκεφτείτε δύο δείκτες που κινούνται από τα άκρα προς το κέντρο κρατώντας μόνο τα τρέχοντα μέγιστα. Δεσμεύστε τον πίνακα των υψών δυναμικά αφού διαβάσετε το $.
Αριθμός στον οδηγό: Α25.9
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: exam-2023-dec-q4 ·
Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2023-dec-q4.html ·
Markdown (GitHub)