Μετρώντας τα Αστέρια - stars [25 Μονάδες]
Είμαστε στην διαδικασία προγραμματισμού του καινούριου διαστημοπλοίου του DI και για την λειτουργία του είναι απαραίτητο ένα υποσύστημα που να υπολογίζει το σύνολο των αστεριών σε ένα τμήμα του ορίζοντα. Το Σχήμα 1 δείχνει ένα παράδειγμα:
| 0 | 3 | 0 | 1 | 0 |
| 0 | 0 | 0 | 8 | 0 |
| 0 | 42 | 0 | 0 | 0 |
| 7 | 1 | 0 | 5 | 4 |
| 0 | 2 | 0 | 0 | 0 |
Σχήμα 1: Μετρώντας τα αστέρια σε μια υποπεριοχή του ορίζοντα (πλέγμα 5x5). Ο ακέραιος στο κάθε κελί υποδεικνύει έναν αριθμό αστεριών. Στο παράδειγμα επιλέξαμε ένα παραλληλόγραμμο με συντεταγμένες από το (2, 1) (άνω αριστερό άκρο) έως και το (3, 3) (κάτω δεξί άκρο). Στην επιλεγμένη περιοχή (με έντονα) το σύνολο των αστεριών είναι 42 + 1 + 5 = 48.
Θεωρούμε πως ο ορίζοντας είναι ένα τετραγωνικό πλέγμα και πως σε κάθε κελί του υπάρχει ένας ακέραιος αριθμός από αστέρια. Οι περιοχές που μπορεί να επιλέξει ο χρήστης είναι αποκλειστικά παραλληλόγραμμα σε σχήμα, τα οποία προσδιορίζονται από τις συντεταγμένες της άνω αριστερής και κάτω δεξιάς γωνίας τους.
Γράψτε ένα πρόγραμμα το οποίο παίρνει ως όρισμα το όνομα αρχείου που περιέχει την διάσταση του πλέγματος καθώς και τους αριθμούς των αστεριών ανά κελί. Στην συνέχεια, το πρόγραμμά σας πρέπει να διαβάζει από την πρότυπη είσοδο (stdin) τις συντεταγμένες του χρήστη και να υπολογίζει τον αριθμό αστεριών αποδοτικά για κάθε περιοχή που θα ζητηθεί. Το πρόγραμμά σας πρέπει να είναι σε θέση να απαντάει σε επαναλαμβανόμενες ερωτήσεις από τον χρήση μέχρι να λάβει EOF. Αν η διάσταση του πλέγματος είναι Ν και ο αριθμός των ερωτήσεων του χρήστη είναι Q, ποια η χρονική και χωρική πολυπλοκότητα της λύσης σας (8/25 της βαθμολογίας); Παράδειγμα εκτέλεσης ακολουθεί:
$ cat horizon.txt
5
0 3 0 1 0
0 0 0 8 0
0 42 0 0 0
7 1 0 5 4
0 2 0 0 0
$ ./stars horizon.txt
Provide top-left x, y coordinates: 2 1
Provide bottom-right x, y coordinates: 3 3
Total number of stars in region (2, 1) - (3, 3) is 48
Provide top-left x, y coordinates: 0 0
Provide bottom-right x, y coordinates: 4 4
Total number of stars in region (0, 0) - (4, 4) is 73
Provide top-left x, y coordinates: 3 0
Provide bottom-right x, y coordinates: 3 0
Total number of stars in region (3, 0) - (3, 0) is 7
Provide top-left x, y coordinates: Terminating
Από το παράδειγμα, η πρώτη συντεταγμένη είναι η γραμμή και η δεύτερη η στήλη. Αν
αθροίζετε κάθε περιοχή κελί προς κελί, κάθε ερώτηση κοστίζει O(N²): σκεφτείτε ποια
πληροφορία μπορείτε να προϋπολογίσετε μία φορά μετά το διάβασμα του αρχείου ώστε κάθε
ερώτηση να απαντιέται με λίγες πράξεις (χρόνος έναντι μνήμης). Δεσμεύστε το πλέγμα
δυναμικά αφού διαβάσετε το N, και χρησιμοποιήστε την τιμή επιστροφής της scanf για
να σταματήσετε στο EOF.
Αριθμός στον οδηγό: Α16.26
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: exam-2025-jan-q6 ·
Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2025-jan-q6.html ·
Markdown (GitHub)